常见的排序算法|
| 排序方法 | 平均时间 | 最好时间 | 最坏时间 |
|---|---|---|---|
| 冒泡排序（稳定 ） | O(n2 ) | O(n) | O(n2) |
| 选择排序（不稳定） | O(n2 ) | O(n2 ) | O(n2 ) |
| 插入排序（稳定） | O(n2 ) | O(n) | O(n2) |
| 希尔排序（不稳定） | O(n1.5) | ||
| 快速排序（不稳定） | O(nlogn) | O(nlogn) | O(n^2) |
| 归并排序（稳定） | O(nlogn) | O(nlogn) | O(nlogn) |
| 堆排序（不稳定） | O(nlogn) | O(nlogn) | O(nlogn) |
| 基数排序（稳定） | O(n) | O(n) | O(n) |
关于空间复杂度：冒泡、选择、插入、希尔空间复杂度为O(1)
快排空间复杂度为logn（递归）
基数排序、归并排序空间复杂度为O(n)
冒泡排序
基本思想：俩个数比较大小，大的下沉，小的上浮
冒泡排序的过程想必大家都很清楚了，直接上代码
可食用代码—java版
private static void BubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 1 - i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
}
}
上面就是冒泡排序最简单的做法，但是如果中间某一时刻已经有序了，该算法仍然会继续进行直到比较length次停止。
优化：设置标记flag，如果发生交换则设为true，否则排序结束
private static void BubbleSort_Better(int[] arr) {
boolean flag;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;//初始化标记
for (int j = arr.length - 1 - i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
flag = true;
}
}
if (!flag) {
break;
}
}
}
适用场景：较少元素时
选择排序
基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
就是每次找第i小的并交换，直接上代码。
private static void SelctionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int tem = arr[min];
arr[min] = arr[i];
arr[i] = tem;
}
}
}
简单插入排序
基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码如下：
private static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tem = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > tem) {
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = tem;
}
}
优化：因为要插入的部分是有序的，所以我们可以用二分查找来缩短寻找插入位置时的时间（二分插入排序），但是主要的时间用在了复制操作上，所以时间上提升有限
适用场景：当数据基本有序时，插入排序可以接近O(n)的时间复杂度
希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本，它与插入排序的不同之处在于，它会优先比较距离较远的元素，该方法因D.L.Shell于1959年提出而得名。希尔排序的整体思想是将固定间隔的几个元素之间排序，然后再缩小这个间隔。这样到最后数列就成为了基本有序数列，而前面我们讲过插入排序对基本有序数列排序效果较好。
具体步骤如下：
1、计算一个增量（间隔）值
2、对元素进行增量元素进行比较，比如增量值为7，那么就对0,7,14,21…个元素进行插入排序
3、然后对1,8,15…进行排序，依次递增进行排序
4、所有元素排序完后，缩小增量比如为3，然后又重复上述第2，3步
5、最后缩小增量至1时，数列已经基本有序，最后一遍普通插入即可
已知的最增量式是由 Sedgewick 提出的 (1, 5, 19, 41, 109,…)，该步长的项来自 9 4^i - 9 2^i + 1 和 4^i - 3 2^i + 1 这两个算式。这项研究也表明 “比较在希尔排序中是最主要的操作，而不是交换。 用这样增量式的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比*快速排序慢。
private static void shellSort(int[] arr) {
int len = arr.length;
//首先分组，分组长度从数组长度的一半开始，即选定增量
for (int gap = len / 2; gap > 0; gap++) {
//对每一组进行插入排序
for (int i = gap; i < len; i += gap) {
insert(arr, gap, i);
}
}
}
private static void insert(int[] arr, int gap, int begin) {
//和普通的插入排序原理相同
int tem = arr[begin];
int j = begin- gap;
while (j >= 0 && tem < arr[j]) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tem;
}
快速排序
这是一个经常用到的排序算法，java.util.Arrays中的sort（）方法用的就是快排，当然我们这里说的经典快排，而sort（）方法用的是双基准快排（比快排效率更高，但还是分治思想）。有兴趣的读者可以自行了解《Dual-Pivot QuickSort》。
经典快排思想：
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
辅助理解：挖坑填数
- 初始时 i = 0; j = 9; key=72
由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。
> 数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
> 0 1 2 3 4 5 6 7 8 9
- 此时 i = 3; j = 7; key=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。
数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
- 可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。
数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
代码如下：
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int mid = getIndex(arr, low, high);
quickSort(arr, low, mid - 1);//左半部分
quickSort(arr, mid + 1, high);//右半部分
}
}
private static int getIndex(int[] arr, int low, int high) {
int tem = arr[low];//基准
while (low < high) {
//找第一个小于基准的数
while (low < high && arr[high] >= tem) {
high--;
}
arr[low] = arr[high];
//找第一个大于基准的数
while (low < high && arr[low] <= tem) {
low++;
}
arr[high] = arr[low];
}
arr[low] = tem;
return low;
}
基准的选择可以有多种方式，如中间数或随机数，选择不同基准会影响算法时间
适用场景：在大规模数据集上性能好
缺点：在小规模数据集上表现较差
解决方案：先使用快排对数据集排序，使其达到基本有序；当数据规模达到一定小时，采用插入排序。
归并排序
基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序适用于子序列有序的数据排序。归并排序是分治法的典型应用。分治法（Divide-and-Conquer）：将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些问题，然后再合并其结果，就得到原问题的解。
代码如下：
private static void divide(int[] arr, int low, int high, int[] tem) {
//此处划分数组
if (low < high) {
int mid = (high - low) >> 1 + low;
divide(arr, low, mid, tem);
divide(arr, mid + 1, high, tem);
mergeSort(arr, low, mid, high, tem);
}
}
private static void mergeSort(int[] arr, int low, int mid, int high, int[] tem) {
//合并数组
int i, j, k;
i = low;
j = mid + 1;
k = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
tem[k++] = arr[i++];
}else {
tem[k++] = arr[j++];
}
}
while (i <= mid) {
tem[k++] = arr[i++];
}
while (j <= high) {
tem[k++] = arr[j++];
}
for (int t = 0; t < k; t++) {
arr[low + t] = tem[t];
}
}
堆排序
首先堆可以分为大根堆和小根堆，从数据机构上来看是一个完全二叉树。所以根据这个特性，我们可以知道 i 节点的左孩子节点为2i+1，右孩子节点为2i+2.
基本思想：（大根堆）
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
代码主要分为两步：
1、构建堆
2、将堆排序，将根节点和最后一个节点调换，然后重新建造堆
代码如下：
private static void heapsort(int[] arr) {
//构建堆,从第一个非叶子节点开始建堆
int len = arr.length - 1;
int begin = len >> 1;
for (int i = begin; i >= 0; i--) {
maxHeap(arr, i);
}
//将根节点和最后一个元素互换，重建堆
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeap(arr, i - 1);
}
}
private static void maxHeap(int[] arr, int root) {
int len = arr.length - 1;
int le = root << 1 + 1;
int ri = le + 1;
int max = le;
if(le > root) return;
if (ri <= len && arr[ri] > arr[le]) { //判断左右节点大小
max = ri;
}
if (arr[max] > arr[root]) {//父节点是否大于所有子节点
swap(arr, max, root);
maxHeap(arr,max);
}
}
private static void swap(int[] arr, int a, int b) {
int tem = arr[a];
arr[a] = arr[b];
arr[b] = tem;
}
基数排序
因为基数排序是桶排序的扩展，所以先提一下桶排序。
桶排序：非常简单的思想，建立一个数组A[MaxValue]，然后将每个数都放置到相应位置（如4放到下标为4的地方），之后遍历一遍数组，即可获得排序结果。
问题：如果maxValue很大，造成空间浪费
基数排序以桶排序为基础，通过限制基数来减少空间开销。
**基数排序思想：**先排好各位，然后排好各位的基础上排十位，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话）
贴一张动图来帮助大家理解：
基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)
我下面的代码是LSD
可食用代码如下
private static void radixSort(int[] arr) {
int wid = getWidth(arr);
int weight = 1;//表示现在是个位
int loc = 1;
int k = 0;
int len = arr.length;
int[][] bucket = new int[10][len];
int[] count = new int[10];//记录每个桶里的元素个数
Arrays.fill(count, 0);
while (loc <= wid) {
for (int num : arr) {//将所有元素放入桶中
int digit = (num / weight) % 10;
bucket[digit][count[digit]] = num;
count[digit]++;
}
for (int i = 0; i < 10; i++) {//将桶中的元素拷贝回原来数组中
if (count[i] != 0) {
for (int j = 0; j < count[i]; j++) {
arr[k++] = bucket[i][j];
}
}
count[i] = 0;
}
k = 0;
weight *= 10;
loc++;
}
}
private static int getWidth(int[] arr) {//获取最大值的位数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int wid = 0;
while (max > 0) {
wid /= 10;
wid++;
}
return wid;
}
参考资料：
基数排序–讲的很棒
排序算法总结—菜鸟教程
堆排序—简书
各种排序算法详解及优劣对比