(Java)冒泡、选择、插入、归并排序

排序

以下排序代码中的 swap 方法为该方法，

// 将下标为i ,i+1 位置的值进行互换
public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

1. 冒泡排序（可以稳定）

• 1).原理
  • a. 比较相邻的元素，如果第一个比第二个大，就交换他们两个；
  • b. 对每一对相邻的元素做同样的工作，从开始到最后的一对，最后一个元素为最大的数；
  • c. 除去最后一个元素，针对所有元素重复以上步骤；
  • d. 持续对每次越来越少的元素重复上面的步骤，直达没有一对数字需要比较。
    
• 2). code

for(int i = arr.length - 1;i > 0; i--){
   for(int j = 0;j < i;j++){
       if(arr[i] > arr[i+1}){
           swap(arr,i.i+1)
       }
   } 
}

• 3). 时间复杂度
  • 平均时间复杂度：O(n²)

2. 选择排序（不稳定）

• 1). 原理
  • a. 从第二个元素开始，后一个元素和前一个元素进行对比，后面的小，则交换；
  • b. 对每一对相邻的元素做同样的工作，这样一轮之后，最小的元素在第一个；
  • c. 除去第一个，进行第二轮，将最小的元素下标与最小元素的下一个进行交换；
  • d. 持续对每次越来越少的元素重复上面的步骤，直达没有一对数字需要比较。
    
• 2). code

for(int i = 0; i < arr.length - 1;i++){
    int minIndex = i;
    for(int j = i + 1;j < arr.length;j++){
        //每次与找到的最小值比较，如果找到更小的，最小值下标交换
        minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    }
    //将最小值换到i 位置
    swap(arr,i,minIndex);
}

• 3). 时间复杂度
  • 平均时间复杂度：O(n²)

3.插入排序（可以稳定）

• 1). 原理
  • a. 要排序的值向有序的序列中插值
  • b. 与排好序的最后一个值进行比较，如果当前值比较小，交换，
  • c. 再与交换后的前一个值比较，如果小交换，否则不交换，排序成功
    
• 2). code

for(int i = 1;i < arr.length - 1;i++){
   for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j--){
        swap(arr,j,j+1);
    }
}

• 3). 时间复杂度
  • 最坏情况O(n²)
  • 最好情况O(n)

4. 归并排序（稳定）

• 1). 原理
  • a. 让左右两部分的元素先有序，然后将两个有序的部分合并成一个有序的数组
  • b. 继续把左边的部分分为两部分，让左边的部分的两部分有序
  • c. 继续把右边的部分分为两部分，让右边的部分的两部分有序
    
    -2). code

	 public static void mergeSort(int[] arr) {
	      if (arr == null || arr.length < 2) {
	          return;
	      }
	      mergeSort(arr, 0, arr.length - 1);
      }
      
      public static void mergeSort(int[] arr, int l, int r) {
          if (l == r) {
              return;
          }
          int mid = l + ((r - l) >> 1);
          mergeSort(arr, l, mid);
          mergeSort(arr, mid + 1, r);
          /*让左右两部分的元素先有序，然后将两个有序的部分合并成一个有序的数组
             那怎么让左边的部分和右边的部分有序？
             继续把左边的部分分为两部分，让左边的部分的两部分有序
             继续把右边的部分分为两部分，让右边的部分的两部分有序
           */
          merge(arr, l, mid, r);
      }
      
      public static void merge(int[] arr, int l, int m, int r) {
          int[] help = new int[r - l + 1];
          int i = 0;
          int p1 = l;
          int p2 = m + 1;
          //比较左右两部分的元素，哪个小，把那个元素填入help中
          while (p1 <= m && p2 <= r) {
              help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
          }
          //上面的循环退出后，把剩余的元素依次填入到help中
          //以下两个while只有一个会执行
          while (p1 <= m) {
              help[i++] = arr[p1++];
          }
          while (p2 <= r) {
              help[i++] = arr[p2++];
          }
          //把最终的结果复制给原数组
          for (i = 0; i < help.length; i++) {
              arr[l + i] = help[i];
          }
      }