大家好,我是多选参数的程序锅,一个正在捣鼓操作系统、学数据结构和算法以及 Java 的失业人员。数据结构和算法我已经学了有一段日子了,最近也开始在刷 LeetCode 上面的题目了,但是自己感觉在算法上还是 0 ,还得猛补啊。
今天这篇基于之前的 8 大排序算法基础之上,增加一个堆排序,也就是这么 9 个排序算法:冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。它们对应的时间复杂度如下所示:
排序算法 | 时间复杂度 | 是否基于比较 |
---|---|---|
冒泡、插入、选择 | O(n^2) | √ |
快排、归并、堆排序 | O(nlogn) | √ |
桶、计数、基数 | O(n) | × |
整篇文章的主要知识提纲如图所示,本篇相关的代码都可以从 https://github.com/DawnGuoDev/algorithm 获取,另外,该仓库除了包含了基础的数据结构和算法实现之外,还会有数据结构和算法的笔记、LeetCode 刷题记录(多种解法、Java 实现) 、一些优质书籍整理。
★本文的图很多都是从极客时间王争老师专栏那边拷贝过来或者截图过来的,少部分图是自己重新画的。为什么不全都换成自己画的图?主要是我比较懒,我觉得图能将自己要阐述的点解释清楚,或者说和自己整理过后的文字结合的不错,我觉得这个图就没必要重新画了,人家的画已经很好看了,也很清晰了,你将它重新画,其实也是差不多,可能就是换个样式而已,核心的东西还是没有变。但是,在有些地方,我觉得别人的图跟我阐述的内容不符合,或者不能很好地阐述我想表达的东西,又或者这个地方需要一个图,那么我会画一个。 ”
学习排序算法除了学习它的算法原理、代码实现之外,最重要的是学会如何评价、分析一个排序算法。分析一个排序算法通常从以下几点出发。
而对执行效率的分析,一般从这几个方面来衡量:
内存消耗其实就是空间复杂度。针对排序算法来说,如果该排序算法的空间复杂度为 O(1),那么这个排序算法又称为原地排序。
是什么
稳定性是指待排序的序列中存在值相等的元素。在排序之后,相等元素的前后顺序跟排序之前的是一样的。
为什么
我们将排序的原理和实现排序时用的大部分都是整数,但是实际开发过程中要排序的往往是一组对象,而我们只是按照对象中的某个 key 来进行排序。
比如一个对象有两个属性,下单时间和订单金额。在存入到数据库的时候,这些对象已经按照时间先后的顺序存入了。但是我们现在要以订单金额为主要 key,在订单金额相同的时候,以下单时间为 key。那么在采用稳定的算法之后,只需要按照订单金额进行一次排序即可。比如有这么三个数据,第一个数据是下单时间、第二数据是订单金额:(20200515、20)、(20200516、10)、(20200517、30)、(20200518、20)。在采用稳定的算法之后,排序的情况如下:(20200516、10)、(20200515、20)、(20200518、20)、(20200517、30)可以发现在订单金额相同的情况下是按订单时间进行排序的。
冒泡排序就是依次对两个相邻的元素进行比较,然后在不满足大小条件的情况下进行元素交换。一趟冒泡排序下来至少会让一个元素排好序(元素排序好的区域相当于有序区,因此冒泡排序中相当于待排序数组分成了两个已排序区间和未排序区间)。因此为了将 n 个元素排好序,需要 n-1 趟冒泡排序(第 n 趟的时候就不需要)。
下面用冒泡排序对这么一组数据4、5、6、3、2、1,从小到大进行排序。第一次排序情况如下:
可以看出,经过一次冒泡操作之后,6 这个元素已经存储在正确的位置上了,要想完成有所有数据的排序,我们其实只需要 5 次这样的冒泡排序就行了。图中给出的是带第 6 次了的,但是第 6 次其实没必要。
使用冒泡排序的过程中,如果有一趟冒泡过程中元素之间没有发生交换,那么就说明已经排序好了,可以直接退出不再继续执行后续的冒泡操作了。
下面的冒泡排序实现是优化之后的:
/**
* 冒泡排序:
* 以升序为例,就是比较相邻两个数,如果逆序就交换,类似于冒泡;
* 一次冒泡确定一个数的位置,因为要确定 n-1 个数,因此需要 n-1
* 次冒泡;
* 冒泡排序时,其实相当于把整个待排序序列分为未排序区和已排序区
*/
public void bubbleSort(int[] arr, int len) {
// len-1 趟
for (int j = 0; j < len-1; j++) {
int sortedFlag = 0;
// 一趟冒泡
for (int i = 0; i < len-1-j; i++) {
if (arr[i] > arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
sortedFlag = 1;
}
}
// 该趟排序中没有发生,表示已经有序
if (0 == sortedFlag) {
break;
}
}
}
**插入排序中将数组中的元素分成两个区间:已排序区间和未排序区间(最开始的时候已排序区间的元素只有数组的第一个元素),插入排序就是将未排序区间的元素依次插入到已排序区间(需要保持已排序区间的有序)。最终整个数组都是已排序区间,即排序好了。**假设要对 n 个元素进行排序,那么未排序区间的元素个数为 n-1,因此需要 n-1 次插入。插入位置的查找可以从尾到头遍历已排序区间也可以从头到尾遍历已排序区间。
如图所示,假设要对 4、5、6、1、3、2进行排序。左侧橙红色表示的是已排序区间,右侧黄色的表示未排序区间。整个插入排序过程如下所示
这边查找插入位置的方式采用从尾到头遍历已排序区间,也没有使用哨兵。
/**
* 插入排序:
* 插入排序也相当于把待排序序列分成已排序区和未排序区;
* 每趟排序都将从未排序区选择一个元素插入到已排序合适的位置;
* 假设第一个元素属于已排序区,那么还需要插入 len-1 趟;
*/
public void insertSort(int[] arr, int len) {
// len-1 趟
for (int i = 1; i < len; i++) {
// 一趟排序
int temp = arr[i];
int j;
for (j = i-1; j >= 0; j--) {
if (arr[j] > temp) {
arr[j+1] = arr[j];
} else {
break;
}
}
arr[j+1] = temp;
}
}
冒泡排序和插入排序的时间复杂度都是 O(n^2),都是原地稳定排序。而且冒泡排序不管怎么优化,元素交换的次数是一个固定值,是原始数据的逆序度。插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。但是,从代码的实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要一个赋值操作。所以,虽然冒泡排序和插入排序在时间复杂度上都是 O(n^2),但是如果希望把性能做到极致,首选插入排序。其实该点分析的主要出发点就是在同阶复杂度下,需要考虑系数、常数、低阶等。
选择排序也分为已排序区间和未排序区间(刚开始的已排序区间没有数据),选择排序每趟都会从未排序区间中找到最小的值(从小到大排序的话)放到已排序区间的末尾。
/**
* 选择排序:
* 选择排序将待排序序列分成未排序区和已排序区;
* 第一趟排序的时候整个待排序序列是未排序区;
* 每一趟排序其实就是从未排序区选择一个最值,放到已排序区;
* 跑 len-1 趟就好
*/
public void switchSort(int[] arr, int len) {
// len-1 趟,0-i 为已排序区
for (int i = 0; i < len-1; i++) {
int minIndex = i;
for (int j = i+1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
**归并排序的核心思想就是我要对一个数组进行排序:首先将数组分成前后两部分,然后对两部分分别进行排序,排序好之后再将两部分合在一起,那整个数组就是有序的了。对于分出的两部分可以采用相同的方式进行排序。**这个思想就是分治的思想,就是先将大问题分解成小的子问题来解决,子问题解决之后,大问题也就解决了。而对于子问题的求解也是一样的套路。这个套路有点类似于递归的方式,所以分治算法一般使用递归来实现。分治是一种解决问题的处理思想,而递归是一种实现它的编程方法。
下面使用递归的方式来实现归并排序。递归的递推公式是:merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r)),终止条件是 p>=r,不再递归下去了。整个实现过程是先调用 __mergeSort()
函数将两部分分别排好序,之后再使用数组合并的方式将两个排序好的部分进行合并。
/**
* 归并排序
*/
public void mergeSort(int[] arr, int len) {
__mergerSort(arr, 0, len-1);
}
private void __mergerSort(int[] arr, int begin, int end) {
if (begin == end){
return;
}
__mergerSort(arr, begin, (begin+end)/2);
__mergerSort(arr, (begin+end)/2 + 1, end);
merge(arr, begin, end);
return;
}
private void merge(int[] arr, int begin, int end) {
int[] copyArr = new int[end-begin+1];
System.arraycopy(arr, begin, copyArr, 0, end-begin+1);
int mid = (end - begin + 1)/2;
int i = 0; // begin - mid 的指针
int j = mid; // mid - end 的指针
int count = begin; // 合并之后数组的指针
while (i <= mid-1 && j <= end - begin) {
arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];
}
while (i <= mid-1) {
arr[count++] = copyArr[i++];
}
while (j <= end - begin) {
arr[count++] = copyArr[j++];
}
}
T(n)= 2*T(n/2) + n
= 2*(2*T(n/4)+ n/2)+n = 2^2*T(n/4) + 2*n
= 2^2*(2*T(n/8)+n/4) + 2*n = 2^3*T(n/8) + 3*n
= ....
= 2^k*T(n/2^K) + k*n
= ....
= 2^(log_2^n)*T(1) + log_2^n*n
最终得到 ,使用大 O 时间复杂表示 T(n)=O(nlogn)。 归并排序中,无论待排数列是有序还是倒序,最终递归的层次都是到只有一个数组为主,所以归并排序跟待排序列没有什么关系,最好、最坏、平均的时间复杂度都是 O(nlogn)。
快速排序利用的也是分治思想,核心思想是从待排数组中选择一个元素,然后将待排数组划分成两个部分:左边部分的元素都小于该元素的值,右边部分的元素都大于该元素的值,中间是该元素的值。然后对左右两个部分套用相同的处理方法,也就是将左边部分的元素再划分成左右两部分,右边部分的元素也再划分成左右两部分。以此类推,当递归到只有一个元素的时候,就说明此时数组是有序了的。
首先要对下标从 begin 到 end 之间的数据进行分区,可以选择 begin 到 end 之间的任意一个数据作为 pivot(分区点),一般是最后一个数据作为分区点。之后遍历 begin 到 end 之间的数据,将小于 pivot 的放在左边,大于的 pivot 的放在右边,将pivot 放在中间(位置 p)。经过这一操作之后,数组 begin 到 end 之间的数据就被分成了三个部分:begin 到 p-1、p、p+1 到 end。最后,返回 pivot 的下标。那么这个过程一般有三种方式:
在返回 pivot 的下标 q 之后,再根据分治的思想,将 begin 到 q-1 之间的数据和下标 q+1 到 end 之间的数据进行递归。这边一定要 q-1 和 q+1 而不能是 q 和 q+1 是因为:考虑数据已经有序的极端情况,一开始是对 begin 到 end;当分区之后 q 的位置还是 end 的位置,那么相当于死循环了。最终,当区间缩小至 1 时,说明所有的数据都有序了。
如果用递推公式来描述上述的过程的话,递推公式:quick_sort(begin...end) = quick_sort(begin...q-1) + quick_sort(q+1...end),终止条件是:begin >= end。将这两个公式转化为代码之后,如下所示:
/**
* 快速排序
*/
public void quickSort(int[] arr, int len) {
__quickSort(arr, 0, len-1);
}
// 注意边界条件
private void __quickSort(int[] arr, int begin, int end) {
if (begin >= end) {
return;
}
// 一定要是 p-1!
int p = partition(arr, begin, end); // 先进行大致排序,并获取区分点
__quickSort(arr, begin, p-1);
__quickSort(arr, p+1, end);
}
private int partition(int[] arr, int begin, int end) {
int pValue = arr[end];
// 整两个指针,两个指针都从头开始
// begin --- i-1(含 i-1):小于 pValue 的区
// i --- j-1(含 j-1):大于 pValue 的区
// j --- end:未排序区
int i = begin;
int j = begin;
while (j <= end) {
if (arr[j] <= pValue) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j++;
} else {
j++;
}
}
return i-1;
}
首先从思想上来看:归并排序的处理过程是由下到上的,先处理子问题,然后对子问题的解再合并;而快排正好相反,处理过程是由上到下的,先分区,再处理子问题。
从性能上来看:归并是一个稳定的、时间复杂度为 O(nlogn) 的排序算法,但是归并并不是一个原地排序算法(所以归并没有快排应用广泛)。而快速排序算法时间复杂度不一定是 O(nlogn),最坏情况下是 O(n^2),而且不是一个稳定的算法,但是通过设计可以让快速排序成为一个原地排序算法。
堆是一种特殊的树。只要满足以下两个条件就是一个堆。
由于”堆是一个完全二叉树“,因此一般堆使用数组来存储,一是节省空间,二是通过数组的下标就可以找到父节点、左右子节点(数组下标最好从 1 开始,该节的代码实现都将从数组下标为 1 的地方开始)。那么,借助堆这种数据结构实现的排序被称为堆排序。堆排序是一种原地的、时间复杂度为 O(nlogn) 且不稳定的排序算法。
整个堆排序的实现分为建堆和排序两个步骤。
建堆
首先是将待排序数组建立成一个堆,秉着能不借助额外数组则不借助的原则,我们可以直接在原数组上直接操作。这样,建堆有两个方法:
我们将第二种思路实现成如下代码段所示:
public void buildHeap(int[] datas, int len) {
this.heap = datas;
this.capacity = len - 1;
this.count = len - 1;
for (int i = this.count/2; i >=1; i--) {
heapifyFromTop(i);
}
}
public void heapifyFromTop(int begin) {
while (true) {
int i = begin; // i 是节点及其左右子节点中较大值的那个节点的下标
/* 就是在节点及其左右子节点中选择一个最大的值,与节点所处的位置进行;
但是,需要注意的是假如这个值正好是节点本身,那么直接退出循环;
否则需要进行交换,然后从交换之后的节点开始继续堆化 */
if (begin * 2 <= this.count && this.heap[begin] < this.heap[2 * begin]) {
i = 2 * begin;
}
if ((2 * begin + 1) <= this.count && this.heap[i] < this.heap[2 * begin + 1]) {
i = 2 * begin + 1;
}
if (i == begin) {
break;
}
swap(begin, i);
begin = i;
}
}
★为什么下标从 n/2 到 1 的数组元素所在节点都是非叶子节点,下标从 n/2+1 到 n 的数组元素所在节点都是叶子节点?这个算是完全二叉树的一个特性。严格的证明暂时没有,不严谨的证明还是有的。这里采用反证法,假如 n/2 + 1 不是叶子节点,那么它的左子节点下标应该为 n+2,但是整个完全二叉树最大的节点的下标为 n。所以 n/2 + 1 不是叶子节点不成立,即 n/2 + 1 是叶子节点。那么同理可证 n/2 + 1 到 n 也是如此。而对于下标为 n/2 的节点来说,它的左子节点有的话下标应该为 n,n 在数组中有元素,因此 n/2 有左子节点,即 n/2 不是叶子节点。同理可证 1 到 n/2 都不是叶子节点。 ”
排序
建完堆(大顶堆)之后,接下去的步骤是排序。那么具体该怎么实现排序呢?
此时,我们可以发现,堆顶的元素是最大的,即数组中的第一个元素是最大的。实现排序的过程大致如下:我们把它跟最后一个元素交换,那最大元素就放到了下标为 n 的位置。此时堆顶元素不是最大,因此需要进行堆化。采用从上而下的堆化方法(参考删除堆顶元素的堆化方法),将剩下的 n-1 个数据构建成堆。最后一个数据因为已知是最大了,所以不用参与堆化了。n-1 个数据构建成堆之后,再将堆顶的元素(下标为 1 的元素)和下标为 n-1 的元素进行交换。一直重复这个过程,直至堆中只剩一个元素,此时排序工作完成。如图所示,这是整个过程的示意图。
下面将排序的过程使用 Java 实现,如下所示。那么讲建堆和排序的过程结合在一起之后就是完整的堆排序了。
public void heapSort() {
while (this.count > 1) {
swap(this.count, 1);
this.count--;
heapifyFromTop(1);
}
}
★详细的代码看文章开头给出的 Github 地址。 ”
时间复杂度
堆排序的时间复杂度是由建堆和排序两个步骤的时间复杂度叠加而成。
在采用第二方式建堆时,从粗略的角度来看,每个节点进行堆化的时间复杂度是 O(logn),那么 n/2 个节点堆化的总时间复杂度为 O(nlogn)。但是这此时粗略的计算,更加精确的计算结果不是 O(nlogn),而是 O(n)。
因为叶子节点不需要进行堆化,所以需要堆化的节点从倒数第二层开始。每个节点需要堆化的过程中,需要比较和交换的次数,跟这个节点的高度 k 成正比。那么所有节点的高度之和,就是所有节点堆化的时间复杂度。假设堆顶节点对应的高度为 h ,那么整个节点对应的高度如图所示(以满二叉树为例,最后一层叶子节点不考虑)。
那么将每个非叶子节点的高度求和为
求解这个公式可将两边同时乘以 2 得到 S2,
然后再减去 S1,从而就得到 S1
由于
所以最终时间复杂度为 O(2n-logn),也就是 O(n)。
排序过程中,我们需要进行 (n-1) 次堆化,每次堆化的时间复杂度是 O(logn),那么排序阶段的时间复杂度为 O(nlogn)。
那么,整个总的时间复杂度为 O(nlogn)。
★不对建堆过程的时间复杂度进行精确计算,也就是建堆以 O(nlogn) 的时间复杂度算的话,那么总的时间复杂度还是 O(nlogn)。 ”
稳定与否
堆排序不是稳定的排序算法。因为在排序阶段,存在将堆的最后一个节点跟堆顶点进行互换的操作,所以有可能会改变相同数据的原始相对顺序。比如下面这样一组待排序 20、16、13、13
,在排序时,第二个 13 会跟 20 交换,从而更换了两个 13 的相对顺序。
是否原地
堆排序是原地排序算法,因为堆排序的过程中的两个步骤中都只需要极个别临时存储空间。
在实际开发中,为什么快速排序要比堆排序性能要好?
**桶排序的核心思想就是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。**桶内排序完成之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。一般步骤是:
public void buckerSort(int[] arr, int len, int bucketCount) {
// 确定数据的范围
int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < len; ++i) {
if (arr[i] < minVal) {
minVal = arr[i];
} else if (arr[i] > maxVal){
maxVal = arr[i];
}
}
// 确认每个桶的所表示的范围
bucketCount = (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount;
int bucketSize = (maxVal - minVal + 1) / bucketCount;
bucketCount = (maxVal - minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;
int[][] buckets = new int[bucketCount][bucketSize];
int[] indexArr = new int[bucketCount]; // 数组位置记录
// 将数据依次放入桶中
for (int i = 0; i < len; i++) {
int bucketIndex = (arr[i] - minVal) / bucketSize;
if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
expandCapacity(buckets, bucketIndex);
}
buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
}
// 桶内排序
for (int i = 0; i < bucketCount; ++i) {
if (indexArr[i] != 0) {
quickSort(buckets[i], 0, indexArr[i] - 1);
}
}
// 桶内数据依次取出
int index = 0;
for (int i = 0; i < bucketCount; ++i) {
for (int j = 0; j < indexArr[i]; ++j) {
arr[index++] = buckets[i][j];
}
}
// 打印
for (int i = 0; i < len; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 对数组进行扩容
public void expandCapacity(int[][] buckets, int bucketIndex) {
int[] newArr = new int[buckets[bucketIndex].length * 2];
System.arraycopy(buckets[bucketIndex], 0, newArr, 0, buckets[bucketIndex].length);
buckets[bucketIndex] = newArr;
}
计数排序跟桶排序类似,可以说计数排序其实是桶排序的一种特殊情况。**当要排序的 n 个数据,所处的范围并不大的时候,比如最大值是 K,那么就可以把数据划分到 K 个桶,每个桶内的数据值都是相同的,**从而省掉了桶内排序的时间。可以说计数排序和桶排序的区别其实也就在于桶的大小粒度不一样。
下面通过举例子的方式来看一下计数排序的过程。假设数组 A 中有 8 个数据,值在 0 到 5 之间,分别是:2、5、3、0、2、3、0、3。
/**
* 计数排序,暂时只能处理整数(包括整数和负数)
* @param arr
* @param len
*/
public void countingSort(int[] arr, int len) {
// 确定范围
int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < len; ++i) {
if (maxVal < arr[i]) {
maxVal = arr[i];
} else if (arr[i] < minVal) {
minVal = arr[i];
}
}
// 对数据进行处理
for (int i = 0; i < len; ++i) {
arr[i] = arr[i] - minVal;
}
maxVal = maxVal - minVal;
// 遍历数据数组,求得计数数组的个数
int[] count = new int[maxVal + 1];
for (int i = 0; i < len; ++i) {
count[arr[i]] ++;
}
printAll(count, maxVal + 1);
// 对计数数组进行优化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
}
printAll(count, maxVal + 1);
// 进行排序,从后往前遍历(为了稳定)
int[] sort = new int[len];
for (int i = len - 1; i >= 0; --i) {
sort[count[arr[i]] - 1] = arr[i] + minVal;
count[arr[i]]--;
}
printAll(sort, len);
}
桶排序和计数排序都适合范围不是特别大的情况(请注意是范围),但是桶排序的范围可以比计数排序的范围稍微大一点。假如数据的范围很大很大,比如对手机号这种的,桶排序和技术排序显然不适合,因为需要的桶的数量也是十分巨大的。此时,可以使用基数排序。**基数排序的思想就是将要排序的数据拆分成位,然后逐位按照先后顺序进行比较。**比如手机号中就可以从后往前,先按照手机号最后一位来进行排序,之后再按照倒数第二位来进行排序,以此类推。当按照第一位重新排序之后,整个排序就算完成了。
需要注意的是**,按照每位排序的过程需要稳定的**,因为假如后一次的排序不稳定,前一次的排序结果将功亏一篑。比如,第一次对个位进行排序结果为 21、11、42、22、62,此时 21 在 22 前面;第二次对十位的排序假如是不稳定的话,22 可能跑到 21 前面去了。那么整个排序就错了,对个位的排序也就相当于白费了。
下面举个字符串的例子,整个基数排序的过程如下图所示:
/**
* 基数排序
* @param arr
* @param len
*/
public void radixSort(int[] arr, int len, int bitCount) {
int exp = 1;
for (int i = 0; i < bitCount; ++i) {
countingSort(arr, len, exp);
exp = exp * 10;
}
}
public int getBit(int value, int exp) {
return (value / exp) % 10;
}
/**
* 计数排序,暂时只能处理整数(包括整数和负数)
* @param arr
* @param len
*/
public void countingSort(int[] arr, int len, int exp) {
// 确定范围
int maxVal = getBit(arr[0], exp);
for (int i = 1; i < len; ++i) {
if (maxVal < getBit(arr[i], exp)) {
maxVal = getBit(arr[i], exp);
}
}
// 遍历数据数组,求得计数数组的个数
int[] count = new int[maxVal + 1];
for (int i = 0; i < len; ++i) {
count[getBit(arr[i], exp)] ++;
}
// 对计数数组进行优化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
}
// 进行排序,从后往前遍历(为了稳定)
int[] sort = new int[len];
for (int i = len - 1; i >= 0; --i) {
sort[count[getBit(arr[i], exp)] - 1] = arr[i];
count[getBit(arr[i], exp)]--;
}
System.arraycopy(sort, 0, arr, 0, len);
printAll(sort, len);
}
几乎所有编程语言都会提供排序函数,比如 C 语言中 qsort()、C++ STL 中的 sort()/stable_sort()、Java 中的 Collections.sort()。这些排序函数,并不会只采用一种排序算法,而是多种排序算法的结合。当然主要使用的排序算法都是 O(nlogn) 的。
在以从小到大为有序的情况中,有序度是数组中有序关系的元素对的个数,用数学公式表示如下所示。
如果 i < j,那么 a[i] < a[j]
比如 2、4、3、1、5、6 这组数据的有序度是 11;倒序排列的数组,有序度是 0;一个完全有序的数组,有序度为满有序度,为 n*(n-1)/2,比如1、2、3、4、5、6,有序度就是 15。
逆序度的定义正好跟有序度的定义相反
如果 i < j,那么 a[i] > a[j]
关于逆序度、有序度、满有序度满足如下公式
逆序度 = 满有序度 - 有序度
排序的过程其实就是减少逆序度,增加有序度的过程,如果待排序序列达到满有序度了,那么此时的序列就是有序了。
不甘于「本该如此」,「多选参数 」值得关注