内部排序
以下为基于比较的排序。
一、插入排序
直接插入排序
- 基本思想：
将元素插入到已经排好序的序列中。第一个元素已经是有序序列，然后比较外围的元素和序列的最后一个元素，判断是否需要插入，如果小，则插入。
- 时间复杂度：最优 O(n) 最差 O(n^2)
- 是否稳定：是
public void insertSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) for (int j = i - 1; j >= 0; j--) if (arr[j + 1] < arr[j]) swap(arr, j + 1, j); } 改进后的插入排序
比如，用二分查找优化插入排序，因为是要插入到已经排好序的序列当中，所以在查找插入位置这个地方可以用二分查找来优化。
public int binarySearch(int[] arr, int low, int high, int key) { while (low <= high) { int mid = low + (high - low) / 2; if (key < arr[mid]) high = mid - 1; else low = mid + 1; } return low; } public void insertSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) // determine whether to insert if (arr[i] < arr[i - 1]) { // record the element to insert int key = arr[i]; // find insert index int indexInsert = binarySearch(arr, 0, i - 1, arr[i]); // move elements for (int j = i - 1; j >= indexInsert; j--) arr[j + 1] = arr[j]; // insert the key arr[indexInsert] = key; } } 二、选择排序
1. 简单选择排序
- 基本思想：
选出后面最小的元素和前面的交换
- 时间复杂度： 最优 O(n^2) 最差 O(n^2)
- 是否稳定：否
public void selectSort(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { int minIndex = i; // find the min index for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) minIndex = j; } if (minIndex != i) swap(arr, i, minIndex); } } 改进后的选择排序
之前的选择排序是一趟只找到最小的，如果一趟可以把最大最小都找出来，就可以将循环的次数减半。
不过在交换时需要注意一种情况，就是第一个元素就已经是最大元素的情况，因为前面已经交换过 i 和 min，所以再交换时就是交换的 n - i - 1 和 min，而不是 max。
public void selectSort(int[] arr) { int n = arr.length; for (int i = 0; i < n / 2; i++) { int min = i; int max = i; for (int j = i + 1; j < n - i; j++) { // find the min element if (arr[j] < arr[min]) { min = j; continue; } // find the max element if (arr[j] > arr[max]) max = j; } swap(arr, i, min); if (max != i) swap(arr, n - i - 1, max); else // the first element is the max element swap(arr, n - i - 1, min); } } 2. 堆排序
- 基本思想：
堆排序也是一种直接选择排序，因为它也是将排好序的大根堆 or 小根堆的顶部元素逐个和尾部元素交换，也是一种选择。
- 时间复杂度： 最优 O(nlgn) 最差 O(nlgn) 是一个很优秀的排序算法
- 是否稳定：否
public void adjustHeap(int[] arr, int i, int len) { int parent = arr[i]; // start from left child for (int k = 2 * i + 1; k < len; k = 2 * k + 1) { // find max child (left or right) if (k + 1 < len && arr[k + 1] > arr[k]) k++; // compare the parent and its child, but don't swap if (arr[k] > arr[i]) { arr[i] = arr[k]; i = k; } else break; } // insert the original parent on index i arr[i] = parent; } public void heapSort(int[] arr) { int len = arr.length; // adjust heap from the last none-leaf node // from bottom to up; from right to left for (int i = len / 2 - 1; i >= 0; i--) adjustHeap(arr, i, len); // swap the top element and the last element for (int i = len - 1; i >= 0; i--) { swap(arr, i, 0); adjustHeap(arr, 0, i); } } 三、归并排序
- 基本思想：分治。将两个有序序列合并成一个有序序列，递归进行。需要辅助数组。
- 时间复杂度： 最优 O(nlgn) 最差 O(nlgn)
- 空间复杂度
O(n)
- 是否稳定：是
/* create an array in advance to avoid creating arrays frequently */ private void sort(int[] arr) { int n = arr.length; int[] temp_arr = new int[n]; mergeSort(arr, 0, n - 1, temp_arr); } public void mergeSort(int[] arr, int left, int right, int[] temp_arr) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid, temp_arr); mergeSort(arr, mid + 1, right, temp_arr); merge(arr, left, mid, right, temp_arr); } } public void merge(int[] arr, int left, int mid, int right, int[] temp_arr) { int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right) { if (arr[i] < arr[j]) { temp_arr[t++] = arr[i]; i++; } else { temp_arr[t++] = arr[j]; j++; } } // insert the remaining elements while (i <= mid) temp_arr[t++] = arr[i++]; while (j <= right) temp_arr[t++] = arr[j++]; t = 0; // copy elements into array while (left <= right) arr[left++] = temp_arr[t++]; } 四、交换排序
1. 冒泡排序
- 基本思想：
总共有 n 个元素，就比较 n - 1 趟，每一趟比较都会将相邻元素进行比较，然后将较大的元素向后放，就像大数沉底，小数像上冒一样。冒泡排序的交换次数等于原始序列的逆序数。
- 时间复杂度： 最优 O(n) 最差也是平均 O(n^2)
- 是否稳定：是
public void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) swap(arr, j, j + 1); } } } 改进后的冒泡排序一
交换过后，会有部分元素是已经排好序了，这一部分再进行比较是没有意义的，可以从这个地方入手改进冒泡排序。
用一个标志位记录最后一次进行交换的位置，这个位置后面的元素是没有进行交换的，说明是已经排好序的，所以不需要再比较。
public void bubbleSort(int[] arr) { int n = arr.length; int i = n - 1; int pos = 0; while (i > 0) { for (int j = 0; j < i; j++) { pos = 0; if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); pos = j; } } i = pos; } } 改进后的冒泡排序二
双向冒泡（正反两个方向同时排序），使排序次数几乎减少一半
public void bubbleSort(int[] arr) { int n = arr.length; int left = 0; int right = n - 1; while (left < right) { for (int i = left; i < right; i++) { if (arr[i] > arr[i + 1]) swap(arr, i, i + 1); } right--; for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) swap(arr, i, i - 1); } left++; } } 2. 快速排序
- 基本思想：
根据选择的基准元素进行划分，然后两边都进行排序，再递归进行。需要注意的是，遍历需要从选择的基准元素的反方向开始。
- 时间复杂度： 最优也是平均 O(nlgn) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
- 是否稳定：否
public void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotLoc = partition(arr, low, high); quickSort(arr, low, pivotLoc - 1); quickSort(arr, pivotLoc + 1, high); } } public int partition(int[] arr, int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; swap(arr, low, high); while (low < high && arr[low] <= pivot) low++; swap(arr, low, high); } return low; } 外部排序
非基于比较的排序，时间复杂度可以达到 O(n)，其实是用空间换时间。
下面列举的都是线性时间排序法
1. 计数排序（Counting Sort）
- 基本思想：
利用数组下标来排序。但只适合有限数值的数字，序列的数字最大值 k 如果太大，那么开的辅助数组 C[] 就会很大，占用太多空间。
这种思路经常被用到。- 时间复杂度： 最优也是平均 O(n + k) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
- 是否稳定：是
public int[] countingSort(int[] A, int k) { int n = A.length; int[] C = new int[k + 1]; // counting the number of times each element appears in A for (int i = 0; i < n; i++) { C[A[i]]++; } // counting elements less than or equal to C[i] for (int i = 1; i <= k; i++) { C[i] = C[i] + C[i - 1]; } // insert into result array int[] B = new int[n]; for (int i = n - 1; i >= 0; i--) { B[C[A[i]] - 1] = A[i]; C[A[i]]--; } return B; } 2. 桶排序（Bucket Sort）
- 基本思想：
把数组中数据放到有限个桶中，在每个桶中分别进行排序（可以采用任意排序方法）。
模拟画图 ≡ω≡
input:[12,22,2,13,23,3] | | | | | | | 2,3 | |12,13| |22,23| |_____| |_____| |_____| bucket1 bucket2 bucket3 (1-10) (11-20) (21-30) output:[2,3,12,13,22,23]
- 时间复杂度： 最优近似 O(n) 最差 O(n^2) 即每次选的基准元素都是最大（小）值
- 是否稳定：是
public void bucketSort(int[] arr){ int n = arr.length; int max = arr[0]; int min = arr[0]; for (int num : arr) { if (num < min) min = num; if (num > max) max = num; } // create bucket int bucketNum = max / 10 - min / 10 + 1; List bucketList = new ArrayList >(); for (int i = 1; i <= bucketNum; i++) { bucketList.add(new ArrayList ()); } // insert into bucket for (int i = 0; i < n; i++) { int index = (arr[i] - min) / 10; ((ArrayList )bucketList.get(index)).add(arr[i]); } ArrayList bucket = null; int index = 0; for (int i = 0; i < bucketNum; i++) { bucket = (ArrayList )bucketList.get(i); bucketInsertSort(bucket); for (int num : bucket) { arr[index++] = num; } } } public void bucketInsertSort(List bucket) { for (int i = 0; i < bucket.size(); i++) { int temp = bucket.get(i); int j = i - 1; for (; j >= 0 && bucket.get(j) > temp; j--) { bucket.set(j + 1, bucket.get(j)); } bucket.set(j + 1, temp); } }
3. 基数排序（Radix Sort）
- 基本思想：
前面的计数和桶排序都是只能排一个关键字，而基数排序可以排多个关键字。
基数排序分为两种：假设有二元组 (a, b)，以 a 为首要关键字，b 为次要关键字排序
- MSD(Most Siginificant Digit) 先排 a，后排 b
- LSD(Least Siginificant Digit) 先排 b，后排 a
基数排序需要使用稳定的排序算法，一般用计数或者桶排序。
e.g. 采用 LSD
input: [170, 45, 75, 90, 802, 24, 2, 66]1. 从最后一个关键字开始排： 170, 45, 75, 90, 802, 24, 2, 66 0 5 5 0 2 4 2 6 排序后（注意保持原来的相对顺序，802 仍然在 2 前面）： 170, 90, 802, 2, 24, 45, 75, 662. 从次要关键字开始排 170, 90, 802, 2, 24, 45, 75, 66 7 9 0 2 4 7 6 排序后（170 仍然在 75 前面）： 802, 2, 24, 45, 66, 170, 75, 903. 从首要关键字开始排： 802, 2, 24, 45, 66, 170, 75, 90 8 1 排序后： 2, 24, 45, 66, 75, 90, 170, 802output: [2, 24, 45, 66, 75, 90, 170, 802]
- 时间复杂度：
平均 O(d * (r + n))
d:digit 数字位数 r:radix 基数 n:number 关键字个数
- 空间复杂度：
O(r + n)
- 是否稳定：是
public void radixSort(int[] arr, int n) { // find max element int max = 0; for (int i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; } for (int k = 1; max / k > 0; k *= 10) { countingSort(arr, n, k); } } public void countingSort(int[] arr, int n, int k) { // max number is 9 int C[] = new int[10]; // counting occurrences for (int i = 0; i < n; i++) { C[(arr[i] / k) % 10]++; } // counting elements less than or equal to C[i] for (int i = 1; i < 10; i++) { C[i] = C[i] + C[i - 1]; } // insert into result array int[] B = new int[n]; for (int i = n - 1; i >= 0; i--) { B[C[(arr[i] / k) % 10] - 1] = arr[i]; C[(arr[i] / k) % 10]--; } for (int i = 0; i < n; i++) { arr[i] = B[i]; } } 总结
-
关于稳定性：
- 稳定的排序算法：冒泡、插入、归并、计数、桶和基数排序
- 不稳定的排序算法: 选择、快速、希尔和堆排序
-
排序算法的选择：
- 如果数据有序或基本有序，冒泡和插入的时间复杂度可以降到 O(n)，而快排则相反。
- 如果数据很大，需要考虑使用 O(nlgn) 的排序方法，如快排、归并排序、堆排。
- 如果对空间限制不大，可以使用基数排序等方法降低时间复杂度，这些线性时间排序法是利用了数据的特性达到最佳的效果。
参考资料：