基本概念
比较排序和非比较排序：
- 常见的排序算法都是比较排序
- 比较排序的时间复杂度通常为 O(n2) 或者 O(nlogn)，比较排序的时间复杂度下界就是 O(nlogn)
- 非比较排序包括计数排序、桶排序和基数排序， 非比较排序对数据有要求 ，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置
- 非比较排序的时间复杂度可以达到 O(n)，但是都需要额外的空间开销
几种排序算法的总结与比较
| 排序方法 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 |
|---|---|---|---|---|
| 简单排序 - 冒泡排序 | O(n2) | O(n^2) | O(1) | 稳定 |
| 简单排序 - 选择排序 | O(n2) | O(n2) | O(1) | 不稳定 |
| 简单排序 - 插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n2) | O(logn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 希尔排序 | O(nlogn2) = O(n1.3) | O(n2) | O(n) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 |
| 桶排序 | O(n + k) | O(n2) | O(n) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(n + k) | 不稳定 |
Array Sorting Algorithms
冒泡排序
通过与相邻元素的比较和交换来把小的数交换到最前面，或者把大的数交换到最后面。
冒泡排序的时间复杂度为 O(n 2)。
代码如下：
// 冒泡排序
public void bubbleSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
// 只需要循环 n-1 次
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
分析：假设输入为 4, 2, 5, 1, 3
第一次循环后，变为 2, 4, 1, 3, 5，5 被移动到最后
第二次循环后，变为 2, 1, 3, 4, 5，4 被移动到最后的第二个位置
以此类推
选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。
但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换， 大大减少了交换的次数。
选择排序的时间复杂度为 O(n 2)。
代码如下：
// 选择排序
public void selectSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int minIndex;
// 只需要循环 n-1 次
for (int i = 0; i < nums.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(nums, i, minIndex);
}
}
}
分析：假设输入为 4, 2, 5, 1, 3
第一次循环后，变为 1, 2, 5, 4, 3，1 被移动到最前
第二次循环后，变为 1, 2, 5, 4, 3，2 被移动到最前的第二个位置
以此类推
插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的。
插入排序的时间复杂度为 O(n 2)。
代码如下：
// 插入排序
public void insertSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
// 假设第一个数位置是正确的
for (int i = 1; i < nums.length; i++) {
int j = i;
int target = nums[j];
// 后移
while (j > 0 && nums[j - 1] > target) {
nums[j] = nums[j - 1];
j--;
}
// 插入
nums[j] = target;
}
}
分析：假设输入为 4, 2, 5, 1, 3
第一次循环后，变为 2, 4, 5, 1, 3
第二次循环后，变为 2, 4, 5, 1, 3
第三次循环后，变为 1, 2, 4, 5, 3
以此类推
快速排序
其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
快速排序是 不稳定的 ，其时间复杂度为 O(nlogn) 。
代码如下：
// 快速排序
public void quickSort(int[] nums, int start, int end) {
if (start >= end)
return;
int partitionIdx = partition(nums, start, end);
quickSort(nums, start, partitionIdx - 1);
quickSort(nums, partitionIdx + 1, end);
}
// partition
public int partition(int[] nums, int start, int end) {
if (start == end) {
return start;
}
int pivot = nums[start];
while (start < end) {
// 从右往左找到第一个小于 pivot 的元素
while (start < end && nums[end] >= pivot) {
end--;
}
// 把小的移动到左边
nums[start] = nums[end];
// 从左往右找到第一个大于 pivot 的元素
while (start < end && nums[start] <= pivot) {
start++;
}
// 把大的移动到右边
nums[end] = nums[start];
}
// 最后把pivot赋值到中间
nums[start] = pivot;
return start;
}
分析：假设输入为 4, 2, 5, 1, 3
第一轮递归后，变为 3, 2, 1, 4, 5
第一轮递归后，变为 1, 2, 3, 4, 5
以此类推
堆排序
堆排序是借助堆来实现的选择排序。
注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
具体参见：堆的使用及相关LeetCode题目
归并排序
归并排序使用了递归分治的思想。
把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列…倒着来看，其实就是先两两合并，然后四四合并…最终形成有序序列。
归并排序空间复杂度为 O(n) ，时间复杂度为 O(nlogn) 。
代码如下：
// 归并排序
public void mergeSort(int[] arr, int start, int end) {
if (start >= end)
return;
int mid = (start + end) / 2;
// 递归排序左边
mergeSort(arr, start, mid);
// 递归排序右边
mergeSort(arr, mid + 1, end);
// 合并
merge(arr, start, mid, end);
}
// 合并两个有序数组
public void merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1]; // 中间数组
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= end) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[start + p] = temp[p];
}
}
希尔排序
希尔排序是插入排序的一种高效率的实现。
简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。
希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
希尔排序时间复杂度为 O(nlogn) 。
代码如下：
// 希尔排序的一趟插入
public void shellInsert(int[] nums, int d) {
for (int i = d; i < nums.length; i++) {
int j = i - d;
// 记录要插入的数据
int temp = nums[i];
// 从后向前，找到比其小的数的位置
while (j >= 0 && nums[j] > temp) {
// 向后挪动
nums[j + d] = nums[j];
j -= d;
}
// 存在比其小的数
if (j != i - d)
nums[j + d] = temp;
}
}
// 希尔排序
public void shellSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int d = nums.length / 2;
while (d >= 1) {
shellInsert(nums, d);
d /= 2;
}
}
计数排序
前提条件：待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
计数排序空间复杂度为 O(n) ，时间复杂度为 O(n) 。
代码如下：
// 计数排序
public void countSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int max = max(nums);
int[] counts = new int[max + 1];
Arrays.fill(counts, 0);
// 计数
for (int i : nums) {
counts[i]++;
}
int k = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < counts[i]; j++) {
nums[k++] = i;
}
}
}
public int max(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i : nums) {
if (i > max)
max = i;
}
return max;
}
桶排序
桶排序算是计数排序的一种改进和推广。
基本思想：使用 映射函数 将待排序的数组划分成M个的子区间(桶)。接着对每个桶中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出每个桶中的全部内容即是一个有序序列。
桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1<k2，那么f(k1)<=f(k2)。 也就是说第i个桶中的最小数据都要大于第 i - 1 个桶中最大数据。
代码如下：
// 桶排序
public void bucketSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 桶数
int bucketNum = (max - min) / nums.length + 1;
// 创建桶
ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>(
bucketNum);
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for (int i = 0; i < nums.length; i++) {
int idx = (nums[i] - min) / (nums.length);
buckets.get(idx).add(nums[i]);
}
// 对每个桶进行排序
for (int i = 0; i < buckets.size(); i++) {
Collections.sort(buckets.get(i));
}
// 还原排好序的数组
int k = 0;
for (List<Integer> bucket : buckets) {
for (int i : bucket) {
nums[k++] = i;
}
}
}
基数排序
基数排序是一种和前面排序方式不同的排序方式，基数排序不需要进行关键字之间的比较。
基数排序是一种借助 多关键字排序 思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。
如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级依次增加。
代码如下：
// 基数排序
public void radixSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
// 获取最大位数
int maxBit = getMaxBit(nums);
/*
* 先根据个位数排序，再根据十位数排序...
*/
for (int i = 1; i <= maxBit; i++) {
// 分配
List<List<Integer>> buf = distribute(nums, i);
// 收集
collect(nums, buf);
}
}
// 分配
public List<List<Integer>> distribute(int[] nums, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for (int j = 0; j < 10; j++) {
buf.add(new LinkedList<Integer>());
}
for (int i = 0; i < nums.length; i++) {
buf.get(getNBit(nums[i], iBit)).add(nums[i]);
}
return buf;
}
// 收集
public void collect(int[] arr, List<List<Integer>> buf) {
int k = 0;
for (List<Integer> bucket : buf) {
for (int i : bucket) {
arr[k++] = i;
}
}
}
// 获取最大位数
public int getMaxBit(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i : nums) {
max = Math.max(max, (i + "").length());
}
return max;
}
// 获取数字x的第n位
public static int getNBit(int x, int n) {
String str = x + "";
if (str.length() < n)
return 0;
else
return str.charAt(str.length() - n) - '0';
}