下面是自己实现的不同排序算法，仅做随时复习观看用

一、排序算法比较

排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性 复杂性
冒泡排序 O(N2) O(N2) O(N) O(1) 稳定 简单
选择排序 O(N2) O(N2) O(N2) O(1) 不稳定 简单
插入排序 O(N2) O(N2) O(N) O(1) 稳定 简单
希尔排序 O(N1.3) O(n(logN)^2) O(N) O(1) 不稳定 较复杂
归并排序 O(NlogN) O(NlogN) O(NlogN) O(N) 稳定 较复杂
快速排序 O(NlogN) O(N2) O(NlogN) O(logN) 不稳定 较复杂
堆排序 O(NlogN) O(NlogN) O(NlogN) O(1) 不稳定 较复杂

二、算法实现

1.前置方法，用于交换

1
2
3
4
5
6
private static void swap(int[] arr, int j, int i) {
    if (i == j) return;
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

2.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 冒泡排序
private static void bubbleSort(int[] arr){
    // 依次比较两个数大小，每次确定末尾一个数是多少
    int len = arr.length;
    for(int i=1;i<len;i++){
        for(int j=0;j<len-i;j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
    System.out.println("bubbleSort:"+Arrays.toString(arr));
}

3.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 选择排序
private static void selectSort(int[] arr){
    // 每次找到最大的值是多少，然后按顺序插入
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int temp = i;
        for (int j = i+1; j < len; j++) {
            if(arr[j] < arr[temp]){
                temp = j;
            }
        }
        swap(arr,temp,i);
    }
    System.out.println("selectSort:"+Arrays.toString(arr));
}

4.插入排序

1
2
3
4
5
6
7
8
9
10
11
12
// 插入排序
private static void insertSort(int[] arr){
    // 每次找到排序的位置
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        while (i > 0 && arr[i] < arr[i-1]){
            swap(arr,i,i-1);
            i--;
        }
    }
    System.out.println("insertSort:"+Arrays.toString(arr));
}

5.希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 希尔排序
private static void shellSort(int[] arr){
    // 增量缩小+插入排序
    int len = arr.length;
    int gap = len / 2;
    while(gap != 0){
        for (int i = gap; i < len; i++) {
            while (i - gap >= 0 && arr[i] < arr[i-gap]){
                swap(arr,i,i-gap);
                i -= gap;
            }
        }
        gap /= 2;
    }
    System.out.println("shellSort:"+Arrays.toString(arr));
}

6.归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 归并排序
private static int[] mergeSort(int[] arr){
    int len = arr.length;
    if (len <= 1) return arr;
    int mid = len / 2;
    int[] left = Arrays.copyOfRange(arr,0,mid);
    int[] right = Arrays.copyOfRange(arr,mid,len);
    return merge(mergeSort(left),mergeSort(right));
}

private static int[] merge(int[] left, int[] right) {
    int lLen = left.length;
    int rLen = right.length;

    int[] arr = new int[lLen+rLen];
    int p = 0;
    int q = 0;
    int i = 0;
    while(p < lLen && q < rLen) {
        if(left[p] < right[q]){
            arr[i++] = left[p++];
        }else {
            arr[i++] = right[q++];
        }
    }
    while (p < lLen) arr[i++] = left[p++];
    while (q < rLen) arr[i++] = right[q++];

    return arr;
}

7.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 快速排序
  private static void fastSort(int[] arr, int start, int end){
      if (end <= start) return;
      int pivot = partition(arr,start,end);
      fastSort(arr,start,pivot-1);
      fastSort(arr,pivot+1,end);
  }

  private static int partition(int[] arr, int start, int end) {
      Random random = new Random();
      int p = random.nextInt(end-start)+start;
      swap(arr,start,p);
      int temp = arr[start];
      while (start < end){
          while (start < end && arr[end] >= temp) end--;
          arr[start] = arr[end];
          while (start < end && arr[start] < temp) start++;
          arr[end] = arr[start];
      }
      arr[start] = temp;
      return start;
  }


8.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 堆排序
  private static void heapSort(int[] arr){
      int len = arr.length;
      // 建堆 大根堆
      for(int i=len-1;i>=0;i--){
          heapInsert(arr,i);
      }
      // 调整，排序
      int heapSize = len;
      while (heapSize > 0){
          swap(arr,0,heapSize-1);
          heapify(arr,heapSize-1);
          heapSize--;
      }
      System.out.println("heapSort:"+Arrays.toString(arr));
  }

  // 调整0——heapSize-1
  private static void heapify(int[] arr, int heapSize) {
      int p = 0;
      while (p < heapSize){
          int left = p * 2 + 1;
          int right = left + 1;
          if (left >= heapSize) return;
          if(right < heapSize && arr[right] > arr[left]) left = right;
          if(arr[left] > arr[p]) {
              swap(arr,p,left);
              p = left;
          }else {
              return;
          }
      }

  }

  private static void heapInsert(int[] arr, int i) {
      while(i > 0){
          int f = i/2;
          if(arr[f] <= arr[i]) {
              swap(arr,f,i);
          }else {
              return;
          }
          i /= 2;
      }
  }

三、Arrays.sort()

Java 中的 Arrays.sort() 方法可能会使用多种排序算法，包括：

  1. 快速排序（Quick Sort）：快速排序是一种基于比较的排序算法，它的时间复杂度为 O(n log n)。当数组大小大于阈值（通常为 286）时，Java 会优先选择快速排序。快速排序在大多数情况下都是非常高效的。
  2. 归并排序（Merge Sort）：归并排序是一种基于比较的排序算法，它的时间复杂度为 O(n log n)。当数组大小小于等于阈值（通常为 286）时，Java 可能会选择归并排序或插入排序。此外，当数组中有大量重复元素时，Java 也可能会选择归并排序。
  3. 插入排序（Insertion Sort）：插入排序是一种简单的排序算法，它的时间复杂度为 O(n^2)。当数组大小小于等于阈值（通常为 47）时，Java 可能会选择插入排序。对于小型数组，插入排序是一种非常高效的排序算法。
  4. TimSort：TimSort 是一种混合排序算法，它结合了归并排序和插入排序的优点。它的时间复杂度为 O(n log n)，并且在处理包含大量重复元素的数组时非常高效。当 Java 检测到数组已经被分割为足够小的块，但每个块本身并不有序时，它可能会使用 TimSort。
  5. 双轴快速排序（Dual-Pivot Quick Sort）：双轴快速排序是一种快速排序的变种，它的时间复杂度为 O(n log n)。当数组大小小于等于阈值（通常为 286）时，Java 可能会选择双轴快速排序或插入排序。双轴快速排序比传统的快速排序更适合处理包含大量重复元素的数组。
  6. 堆排序（Heap Sort）：堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为 O(n log n)。当 Java 检测到数组已经被分割为足够小的块，但每个块本身并不有序时，它可能会使用堆排序。

需要注意的是，以上列出的排序算法不是 Java 所有可能使用的排序算法，具体实现会根据不同的 JVM 实现和其他因素而有所不同。但是，对于绝大多数情况来说，Java 的 Arrays.sort() 方法会选择最合适的排序算法以达到最优的性能。

四、Collections.sort()

Collections.sort() 是 Java 中用于对集合进行排序的方法，它也可能会使用多种排序算法，包括：

  1. 归并排序（Merge Sort）：归并排序是一种基于比较的排序算法，它的时间复杂度为 O(n log n)。在对集合进行排序时，Java 通常会选择归并排序。归并排序在大多数情况下都是非常高效的。
  2. TimSort：TimSort 是一种混合排序算法，它结合了归并排序和插入排序的优点。它的时间复杂度为 O(n log n)，并且在处理包含大量重复元素的集合时非常高效。当 Java 检测到集合已经被分割为足够小的块，但每个块本身并不有序时，它可能会使用 TimSort。

需要注意的是，Collections.sort() 方法默认使用自然排序（natural ordering），即根据元素自身的比较方法进行排序。如果集合中的元素没有实现 Comparable 接口或者希望按照其他方式进行排序，则需要使用重载的 sort() 方法，并提供自定义的比较器（Comparator）。

需要注意的是，以上列出的排序算法不是 Java 所有可能使用的排序算法，具体实现会根据不同的 JVM 实现和其他因素而有所不同。但是，对于绝大多数情况来说，Java 的 Collections.sort() 方法会选择最合适的排序算法以达到最优的性能