常用的排序算法(Java版)

---

前言

排序算法有许多，这里列出最常用的一些，如选择排序、插入、冒泡等。
稳定性：待排序数据中有相同的数，排序之后相同的数与排序前的前后位置关系稳定，则成为稳定排序算法。
好比我们有一组数据2,9,3,4,8,3;按照巨细排序之后就是2,3,3,4,8,9;两个3的前后顺序在排序前后保持稳定，即稳定。

---

一、选择排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(N^2)O(N^2)O(N^2)不稳定O(1) 代码：

1.   public void selectSort(int[] arr) {
2.         for (int i = 0; i < arr.length - 1; i++) {
3.             int min = i;
4.             for (int j = i + 1; j < arr.length; j++) {
5.                 if (arr[min] > arr[j]) {
6.                     min = j;
7.                 }
8.             }
9.             if (min != i) {
10.                 swap(arr, i, min);
11.             }
12.         }
13.     }
14.     private void swap(int[] arr, int i, int j) {
15.         int temp = arr[i];
16.         arr[i] = arr[j];
17.         arr[j] = temp;
18.     }

复制代码

二、插入排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(N)O(N^2)O(N^2)稳定O(1) 代码：

1.     public void insertSort(int[] arr) {
2.         for (int i = 1; i < arr.length; i++) {
3.             int insertNote = arr[i];
4.             int j = i - 1;//前一个元素的下标
5.             while (j >= 0 && insertNote < arr[j]) {
6.                 arr[j + 1] = arr[j];
7.                 j--;
8.             }
9.             arr[j + 1] = insertNote;
10.         }
11.     }

复制代码

三、冒泡排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(N)O(N^2)O(N^2)稳定O(1) 代码：

1.     public void bubbleSort(int[] arr) {
2.         for (int i = 0; i < arr.length - 1; i++) {
3.             boolean swapped = false;
4.             for (int j = 0; j < arr.length - 1 - i; j++) {
5.                 if (arr[j] > arr[j + 1]) {
6.                     swap(arr, j, j + 1);
7.                     swapped = true;
8.                 }
9.             }
10.             if (!swapped) {
11.                 break;
12.             }
13.         }
14.     }
15.     private void swap(int[] arr, int i, int j) {
16.         int temp = arr[i];
17.         arr[i] = arr[j];
18.         arr[j] = temp;
19.     }

复制代码

四、快速排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(NlogN)O(NlogN)O(N^2)不稳定O(logN) 代码：

1.   public void quickSort(int[] arr) {
2.         quick(arr, 0, arr.length - 1);
3.     }
5.     private void quick(int[] arr, int low, int high) {
6.         if (low < high) {
7.             int pivot = arr[high];
8.             int pivotIndex = low;
9.             for (int j = low; j < high; j++) {
10.                 if (arr[j] < pivot) {
11.                     swap(arr, pivotIndex++, j);
12.                 }
13.             }
14.             swap(arr, pivotIndex, high);
15.             quick(arr, low, pivotIndex - 1);
16.             quick(arr, pivotIndex + 1, high);
17.         }
18.     }
19.     private void swap(int[] arr, int i, int j) {
20.         int temp = arr[i];
21.         arr[i] = arr[j];
22.         arr[j] = temp;
23.     }

复制代码

五、归并排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(NlogN)O(NlogN)O(NlogN)稳定O(N) 代码：

2.   public void mergeSort(int[] arr) {
3.         mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
4.     }
6.     private void mergeSort(int[] array, int lo, int hi, int[] aux) {
7.         if (lo < hi) {
8.             int mid = lo + (hi - lo) / 2;
9.             mergeSort(array, lo, mid, aux);
10.             mergeSort(array, mid + 1, hi, aux);
11.             merge(array, lo, mid, hi, aux);
12.         }
13.     }
15.     private void merge(int[] arr, int lo, int mid, int hi, int[] aux) {
16.         if (hi - lo + 1 >= 0) {
17.             System.arraycopy(arr, lo, aux, lo, hi - lo + 1);
18.         }
19.         int leftStartIndex = lo;
20.         int rightStartIndex = mid + 1;
21.         for (int k = lo; k <= hi; k++) {
22.             if (leftStartIndex > mid) {//如果左边元素没了， 直接将右边的剩余元素都合并到到原数组中
23.                 arr[k] = aux[rightStartIndex++];
24.             } else if (rightStartIndex > hi) {//如果右边元素没有了，直接将所有左边剩余元素都合并到原数组中
25.                 arr[k] = aux[leftStartIndex++];
26.             } else if (aux[leftStartIndex] < aux[rightStartIndex]) {//如果左边比右边小，则将左边的元素拷贝到原数组中
27.                 arr[k] = aux[leftStartIndex++];
28.             } else {
29.                 arr[k] = aux[rightStartIndex++];
30.             }
31.         }
32.     }

复制代码

六、希尔排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度O(N)O(N^(3/2))O(N^S)（1<S<2）不稳定O(1) 代码：

2.   public void shellSort(int[] arr) {
3.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
4.             for (int i = gap; i < arr.length; i++) {
5.                 int insertNote = arr[i];
6.                 int j = i;
7.                 while (j >= gap && insertNote < arr[j - gap]) {
8.                     arr[j] = arr[j - gap];
9.                     j -= gap;
10.                 }
11.                 arr[j] = insertNote;
12.             }
13.         }
14.     }

复制代码

七、堆排序

最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度堆排序O(NlogN)O(NlogN)O(NlogN)不稳定 代码：

1.   public void heapSort(int[] arr) {
2.         log.info("TopMax = {}", top(arr, 5, true));
3.         log.info("TopMin = {}", top(arr, 5, false));
4.     }
6.     private int[] top(int[] input, int topN, boolean topMax) {
7.         int[] result = Arrays.copyOf(input, topN);
9.         for (int i = 0; i < topN; i++) {
10.             int currentIndex = i;
11.             while (currentIndex != 0 && topMax ? result[parentIndex(currentIndex)] > result[currentIndex] : result[parentIndex(currentIndex)] < result[currentIndex]) {
12.                 swap(result, currentIndex, currentIndex = parentIndex(currentIndex));
13.             }
14.         }
16.         for (int i = topN; i < input.length; i++) {
17.             if (topMax) {//大顶堆
18.                 if (input[i] > result[0]) {
19.                     result[0] = input[i];
20.                     int from = 0;
21.                     while ((leftIndex(from) < topN && result[from] > result[leftIndex(from)])
22.                             || (rightIndex(from) < topN && result[from] > result[rightIndex(from)])) {
23.                         if (rightIndex(from) < topN && result[leftIndex(from)] > result[rightIndex(from)]) {
24.                             swap(result, from, from = rightIndex(from));
25.                         } else {
26.                             swap(result, from, from = leftIndex(from));
27.                         }
28.                     }
29.                 }
30.             } else {//小顶堆
31.                 if (input[i] < result[0]) {
32.                     result[0] = input[i];
33.                     int from = 0;
34.                     while ((leftIndex(from) < topN && result[from] < result[leftIndex(from)])
35.                             || (rightIndex(from) < topN && result[from] < result[rightIndex(from)])) {
36.                         if (rightIndex(from) < topN && result[leftIndex(from)] < result[rightIndex(from)]) {
37.                             swap(result, from, from = rightIndex(from));
38.                         } else {
39.                             swap(result, from, from = leftIndex(from));
40.                         }
41.                     }
42.                 }
43.             }
45.         }
46.         return result;
47.     }
49.     private static int parentIndex(int i) {
50.         return (i - 1) / 2;
51.     }
53.     private static int leftIndex(int i) {
54.         return 2 * i + 1;
55.     }
57.     private static int rightIndex(int i) {
58.         return 2 * i + 2;
59.     }
60.    
61.     private void swap(int[] arr, int i, int j) {
62.         int temp = arr[i];
63.         arr[i] = arr[j];
64.         arr[j] = temp;
65.     }

复制代码

总结

排序算法最佳时间复杂度平均时间复杂度最坏时间复杂度稳定性空间复杂度选择排序O(N^2)O(N^2)O(N^2)不稳定O(1)插入排序O(N)O(N^2)O(N^2)稳定O(1)冒泡排序O(N)O(N^2)O(N^2)稳定O(1)快速排序O(NlogN)O(NlogN)O(N^2)不稳定O(logN)归并排序O(NlogN)O(NlogN)O(NlogN)稳定O(N)希尔排序O(N)O(N^(3/2))O(N^S)（1<S<2）不稳定O(1)堆排序O(NlogN)O(NlogN)O(NlogN)不稳定O(1)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。