网站网页设计怎么收费,wordpress首页显示链接,上海室内设计工作室排名,南宁网站建设公司电话文章目录 排序1.基本概念2.分类2.存储结构 一.插入排序1.1直接插入排序1.2折半插入排序1.3希尔排序 二.选择排序2.1简单选择排序2.2堆排序 三.交换排序3.1冒泡排序3.2快速排序 四.归并排序五.基数排序**总结** 排序
1.基本概念
排序#xff08;sorting#xff09;又称分类sorting又称分类将一组杂乱无章的数据按一定规律排列起来。即将无序序列排成一个有序序列由小到大或由大到小的运算。
2.分类
我们可以看到排序的分类非常多 按存储介质可分为 内部排序数据量不大数据在内存无需内外存交换数据 外部排序数据量较大数据在外存文件排序 外部帕西时要将数据分批调入内存来排序中间结果还要及时放入外存显然外部排序要复杂的多。 按比较器个数可分为 串行排序单处理机同一时刻比较一对元素并行排序多处理机同一时刻比较多对元素 按主要操作可分为 比较排序通过比较来决定元素间的相对次数由于其时间复杂度不能突破O ( n log n ) 因此也称为非线性时间比较类排序。基数排序不比较元素的大小仅仅根据元素本身的取值确定其有序位置。它可以突破基于比较排序的时间下界以线性时间运行因此也称为线性时间非比较类排序。 按稳定性可分为 稳定排序能够使任何数值相等的元素排序以后相对次序不变非稳定性排序不是稳定排序的方法。 排序的稳定性只对结构型数据排序有意义。例如 排序方法是否稳定并不能衡量一个排序算法的优劣。 按辅助空间可分为 原地排序辅助空间量为O(1)的排序方法所占的辅助空间与参与排序的数据量大小无关通常意义上的排序都是指的原地排序。非原地排序辅助空间量超过O(1)的排序方法。 按自然性可分为 自然排序输入数据越有序排序的速度越快的排序方法非自然排序不是自然排序的方法。 按排序所需工作量 简单的排序方法T(n)O(n2)基数排序T(n)O(d.n)先进的排序方法T(n)O(nlogn)
2.存储结构
记录序列以顺序表存储:
#define MAXSIZE 20 //设记录不超过20个
typedef int KeyType; //设关键字为整形量int型Typedef struct{ //定义每个记录数据元素的结构KeyType key; //关键字InofType otherinfo; //其他数据项
}RedType;//Record TypeTypedef struct{ //定义顺序表的结构RedType r[MAXSIZE 1]; //存储顺序表的向量//r[0]一般作哨兵或缓冲区int length; //顺序表的长度
}SqList;一.插入排序
【基本思想】每步把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。
【基本操作】
在有序序列中插入一个元素保持序列有序有序长度不断增加。起初a[0]是长度为1的子序列。然后逐将a[1]至a[n-1]插入到有序子序列中。
【有序插入方法】
在插入a[i]前数组a的前半段a[0]a[i-1]是有序段后半段a[i]a[n-1]是停留于输入次序的无序段。插入a[i]使a[0]~a[i-1]有序也就是要为a[i]找到有序位置 j0 j i将a[i]插入在a[j]的位置上。 那么这个插入位置可以在哪呢 那么怎么找到这个插入位置呢 根据插入的方法我们将插入排序分为以下三种 1.1直接插入排序
直接插入排序(Straight Insertion Sort)——采用顺序查找法查找插入位置。
【算法思想】 在顺序查找法中我们使用哨兵来提高查找效率这里同样可以使用 【算法实现】
void InsertSort(SqList *L){int i,j;//i表示当前无序部分的第一个元素j表示寻找插入位置过程中的下标//依次将R[2]~R[n]插入到前面已排序序列R[1]为默认排好序的序列R[0]作为哨兵不存放元素for(i2; iL-length; i){if(L.r[i]key L.r[i-1].key){//插入前先比较若当前i比前一位置的大直接插入有序表中若小需将L.r[i]插入有序子表L.r[0]L.r[i]; //复制为哨兵for(ji-1; L-R[0]L-R[j]; --j){//从后往前查找待插入位置L.r[j1]L.r[j]; //向后挪位}L.r[j]L.r[0]; //复制到插入位置,即将哨兵上的元素赋值到插入位置}}
}假定初始序列为{ 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } 初始时49可以视为一个已排好序的子序列按照上述算法进行直接插入排序的过程如下图所示括号内是已排好序的子序列。 【性能分析】
实现排序的基本操作有两个
1“比较”序列中两个关键字的大小
2“移动”记录。 时间复杂度 最佳情况T(n) O(n) 数组有序的情况下最坏情况T(n) O(n2) 数组逆序的情况下平均情况T(n) O(n2) 耗时差不多是最坏情况的一半 原始数据越接近有序排序速度越快。所以要提高查找速度 减少元素的比较次数减少元素的移动次数 空间复杂度O(1)仅用了一个辅助单元哨兵 稳定性由于每次插入元素时总是从后向前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序方法。 适用性直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时可以从前往后查找指定元素的位置。
1.2折半插入排序
查找插入位置时采用折半查找法
【算法思想】 比较查找当highlow时此时的mid即是要插入的位置查找比较停止当前下标[0]~high的位置都小于要插入的数实际上如果有与要插入的数相等的也在这个区间范围里同时从low开始到有序区最后一个数都大于要插入的数。后移将low和其后面的元素统一向后移动一位腾出位置来这时有序区就扩充了一个位置插入到正确的位置即high1所对应的位置 当要插入的数lowhighmid时考虑到稳定性为了能让原本在后面的要插入的数排序之后还在后面所以此时我们应该将要插入的数插入到high值的后面也就是令leftmid1. 【算法实现】
void BInsertSort(SqList L){for(i2;iL.length;i){//依次插入第2~第n个元素if(L.r[i]key L.r[i-1].key){//插入前先比较若当前i比前一位置的大直接插入有序表中若小需将L.r[i]插入有序子表L.r[0]L.r[i]; //复制为哨兵low1;highi-1; //采用折半查找法查找插入位置while(lowhigh){mid(lowhigh)/2;if(L.r[0].keyL.r[mid].key) highmid-1;//如果哨兵位置比中间位置的值小就在左半区查找else lowmid1;//否则就在右半区查找}}for(int ji-1;j high; j--){L.r[j1]L.r[j];}L.r[high1]L.r[i];}
}【性能分析】
1比较次数
折半查找比顺序查找快所以折半插入排序就平均性能来说比直接插入排序要快
它所需要的关键码比较次数与待排序对象序列的初始排列无关仅依赖于对象个数。在插入第 i 个对象时需要经过⌊log_2i⌋1次关键吗比较。才能确定它的插入位置 当n较大时总关键码比较次数比直接插入排序的最坏情况要好得多但比其最好情况要差在对象的初始排列已经按关键码排好序或接近有序时直接插入排序比折半插入排序执行的关键码比较次数要少
2移动次数
折半插入排序的对象移动次数与直接插入排序相同依赖于对象的初始排列
减少了比较次数但没有减少移动次数平均性能优于直接插入排序
时间复杂度
最佳情况T(n) O(n) 数组有序的情况下最坏情况T(n) O(n2) 数组逆序的情况下平均情况T(n) O(n2) 耗时差不多是最坏情况的一半 虽然折半查找的效率比顺序查找的高但还是被元素的移动拖了后腿导致最终的时间复杂度都和直接插入排序一样。 空间复杂度O(1)是一种稳定的排序方法 前面我们提到直接插入排序在基本有序待排序的记录个数较少的情况下效率比较高。那么有比折半插入排序还快的吗怎么才能想办法让排序基本有序或每比较一次就移动一大步呢
希尔排序来啦~
1.3希尔排序
现将整个待排序记录序列分割成若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
它与插入排序的不同之处在于它会优先比较距离较远的元素。
特点①缩小增量②多遍插入排序 希尔增量 gaplength/2 希尔排序的增量序列的选择与证明是个数学难题希尔增量序列{n/2,(n/2)/2…1}是比较常用的也是希尔建议的增量但其实这个增量序列不是最优的。 增量序列必须是递减的最后一个必须是1增量序列应该是互质的 【算法思想】这里重要的是理解分组思想每一个组其实就是一个插入排序相当于进行多次插入排序。
①先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的元素进行排序。
②然后将gap逐渐减小重复上述分组和排序的工作。
③当到达gap1时所有元素在统一组内排好序。 【算法实现】
/*对顺序表L作希尔排序*/
void ShellSort(SqList *L,int dalta[],int t){//按增量序列dlta[0..t-1]对顺序表L做希尔排序for(k0;kt;k)Shelllnsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
}//ShellSortvoid Shelllsert(SqList L,int dk){//对顺序表L进行一趟增量为dk的Shell排序dk为步长因子for(idk1;iL.length;i)if(r[i].key r[i-dk].key){r[0]r[i];for(ji-dk;j0 (r[0].key r[j].key))jj-dk;r[jdk]r[j];r[jdk]r[0];}
}【性能分析】
希尔排序算法效率与增量序列的取值有关简单了解一下 时间复杂度由于希尔排序的时间复杂度依赖于增量序列的函数这涉及数学上尚未解决的难题所以其时间复杂度分析比较困难。当n在某个特定范围时希尔排序的时间复杂度约为O(n1.25)~O(1.6n1.25)——经验公式。要好于直接排序的O(n2)。 空间复杂度O(1)仅用了常数个辅助单元 稳定性当相同关键字的记录被划分到不同的子表时可能会改变它们之间的相对次序因此希尔排序是一种不稳定的排序方法。 适用性希尔排序算法仅适用于线性表为顺序存储的情况不宜在链式存储结构上实现。
二.选择排序
2.1简单选择排序
简单选择排序法(Simple Selection Sort) 就是通过n − i 次关键字间的比较从 n-i1个记录中选出关键字最小的记录并和第 i (1in) 个记录交换之。
【算法思想】
①第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始(末尾)位置
②然后选出次小(或次大)的一个元素存放在最大(最小)元素的下一个位置
③重复这样的步骤直到全部待排序的数据元素排完 。
【算法实现】
void SelectSort(SqList *L){int i,j,min;for(i0; iL-length-1;i){ //一共进行n-1趟min i; //记录最小元素位置for(jii; jL-length; j){if(L-R[j] L-R[min]){ //在R[i...n-1]中选择最小的元素min j; //更新最小元素位置}}if(min !i){swap(L-R[i], L-R[min]); //swap函数移动元素3次}}
}【性能分析】 时间复杂度 元素移动的操作次数很少不会超过3(n-1)次最好的情况是移动0 次此时对应的表已经有序但元素间比较的次数与序列的初始状态无关始终是n ( n − 1 ) / 2 次因此时间复杂度始终是O(n2)。 空间复杂度O(1)仅用了常数个辅助单元 稳定性不稳定
2.2堆排序
堆排序(Heap Sort)是对简单选择排序进行的一种改进。 堆的定义 堆是具有下列性质的完全二叉树每个结点的值都大于或等于其左右孩子结点的值称为大根堆(如下图所示)或者每个结点的值都小于或等于其左右孩子结点的值称为小根堆。 【算法思想】
利用堆的思想来进行排序总共分为两个步骤
1. 建堆
升序建大堆降序建小堆
2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
这里以升序为例
首先应该建一个大堆不能直接使用堆来实现。可以将需要排序的数组看作是一个堆但需要将数组结构变成堆。我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶这样就可以将数组调整成一个堆且如果建立的是大堆堆顶元素为最大值。 然后按照堆删的思想将堆顶和堆底的数据交换但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置然后从堆顶向下调整到倒数第二个元素这样次大的元素就在堆顶重复上述步骤直到只剩堆顶时停止。 【算法实现】
//建立大根堆算法
void BuildMaxHeap(ElemType A[], int len){for(int ilen/2; i0; i--){ //从i[n/2]~1反复调整堆HeadAdjust(A, i, len);}
}/*函数HeadAdjust将元素k为根的子树进行调整*/
void HeadAdjust(ElemType A[], int k, int len){A[0] A[k]; //A[0]暂存子树的根节点for(i2*k; ilen; i*2){ //沿key较大的子结点向下筛选if(ilen A[i]A[i1]){i; //取key较大的子节点的下标}if(A[0] A[i]){break; //筛选结束}else{A[k] A[i]; //将A[i]调整到双亲结点上k i; //修改k值以便继续向下筛选}}A[k] A[0]; //被筛选结点的值放入最终位置
}调整的时间与树高有关为O ( h )。在建含n个元素的堆时关键字的比较总次数不超过 4n时间复杂度为 O(n)这说明可以在线性时间内将一个无序数组建成一个堆。 下面是堆排序算法
void HeapSord(ElemType A[], int len){BuildMaxHeap(A, len); //初始建堆for(i len; i1; i--){ //n-1趟的交换和建堆过程Swap(A, i, 1); //输出堆顶元素和堆底元素交换HeapAdjust(A, 1, i-1); //调整把剩余的i-1个元素整理成堆}
}同时堆也支持插入操作 对堆进行插入操作时先将新结点放在堆的末端再对这个新结点向上执行调整操作。大根堆的插入操作示例如下图所示 【性能分析】
时间复杂度建堆时间为O ( n ) 之后有n − 1次向下调整操作每次调整的时间复杂度为O ( h )故在最好、最坏和平均情况下堆排序的时间复杂度为O(nlog_2 n)。空间复杂度O(1)仅用了常数个辅助单元稳定性进行筛选时有可能把后面相同关键字的元素调整到前面所以堆排序算法是一种不稳定的排序方法。适用性堆排序适合关键字较多的情况(如n1000)。例如在1亿个数中选出前100个最大值首先使用一个大小为100的数组读入前100个数建立小顶堆而后依次读入余下的数若小于堆顶则舍弃否则用该数取代堆顶并重新调整堆待数据读取完毕堆中100个数即为所求。
三.交换排序
3.1冒泡排序
在无序区间通过相邻数的比较将最大的数冒泡到无序区间的最后持续这个过程直到数组整体有序。
【算法思想】
比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个重复步骤1~3直到排序完成。
【算法实现】
void BubbleSort(SqList *L){int i, j;bool flag true; //表示本趟冒泡是否发生交换的标志for(i0; i L-length-1; i){ flag false; for(jn-1; ji; j--){ //一趟冒泡过程if(L-R[j-1] L-R[j]){ //若为逆序swap(L, j-1, j); //交换flag true;}}if(flag false){return; //本趟遍历后没有发生交换说明表已经有序}}
}【性能分析】 时间复杂度 当初始序列有序时显然第一趟冒泡后flag依然为false (本趟冒泡没有元素交换)从而直接跳出循环比较次数为n − 1 n-1n−1移动次数为0 00从而最好情况下的时间复杂度为O ( n ) O(n)O(n)当初始序列为逆序时需要进行n − 1 n- 1n−1趟排序第i ii趟排序要进行n − i n -in−i次关键字的比较而且每次比较后都必须移动元素3 33次来交换元素位置。这种情况下比较次数 ∑ i 1 n ( n − i ) n ( n − 1 ) / 2 比较次数\displaystyle\sum_{i1}^{n}(n-i)n(n-1)/2比较次数i1∑n(n−i)n(n−1)/2移动次数 ∑ i 1 n 3 ( n − i ) 3 n ( n − 1 ) / 2 移动次数\displaystyle\sum_{i1}^{n}3(n-i)3n(n-1)/2移动次数i1∑n3(n−i)3n(n−1)/2 最坏情况下的时间复杂度为O ( n 2 ) O(n^2)O(n2) 数据逆序,其平均时间复杂度也为O ( n 2 ) O(n^2)O(n2)。最好情况O(n)----数据有序 空间复杂度O(1)仅用了常数个辅助单元 稳定性由于每次插入元素时总是从后向前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序方法。
3.2快速排序
这里是排序算法的重点了非常重要
通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。
【算法思想】
从待排序区间选择一个数作为基准值(pivot)Partition: 遍历整个待排序区间将比基准值小的可以包含相等的放到基准值的左边将比基准值大的可以包含相等的放到基准值的右边采用分治思想对左右两个小区间按照同样的方式处理直到小区间的长度 1代表已经有序 或者小区间的长度 0代表没有数据。
【算法实现】
public class quickSort {public static void quickSort(long[] array) {quickSortRange(array, 0, array.length - 1);}// 为了代码书写方便我们选择使用左闭右闭的区间表示形式// 让我们对 array 中的从 from 到 to 的位置进行排序其他地方不用管// 其中fromto 下标的元素都算在区间的元素中// 左闭右闭的情况下区间内的元素个数 to - from 1;private static void quickSortRange(long[] array, int from, int to) {if (to - from 1 1) {// 区间中元素个数 1 个return;}// 挑选中区间最右边的元素 array[to]// array[to] 还是 array[to - 1] 还是 array[array.length] 还是 array[array.length - 1] 呢int pi partitionMethodA(array, from, to);// 小于等于 pivot 的元素所在的区间如何表示 array, from, pi - 1// 大于等于 pivot 的元素所在的区间如何表示 array, pi 1, to// 按照分治算法的思路使用相同的方式处理相同性质的问题只是问题的规模在变小quickSortRange(array, from, pi - 1); // 针对小于等于 pivot 的区间做处理quickSortRange(array, pi 1, to); // 针对大于等于 pivot 的区间做处理}/*** 以区间最右边的元素 array[to] 最为 pivot遍历整个区间从 from 到 to移动必要的元素* 进行分区* param array* param from* param to* return 最终 pivot 所在的下标*/private static int partitionMethodA(long[] array, int from, int to) {// 1. 先把 pivot 找出来long pivot array[to];// 2. 通过定义 left 和 right 两个下标将区间划分出来int left from;int right to;// [from, left) 都是 pivot 的// [left, right) 都是未参与比较的// [right, to] 都是 pivot 的// 循环保证每个元素都参与了和 pivot 的比较// 也就是只要 [left, right) 区间内还有元素循环就应该继续while (left right) {
// while (right - left 0) {// 先让左边进行比较// 随着 left 在循环过程中一直在 left请问 left right 的条件能一定保证么// 不一定所以我们时刻进行 left right 条件的保证// 并且只有在 left right 成立的情况下array[left] 和 pivot 的比较才有意义// left right array[left] pivot 的顺序不能交换while (left right array[left] pivot) {left;}// 循环停止时说明 array[left] pivotwhile (left right array[right] pivot) {right--;}// 循环停止时说明 array[right] pivot// 两边都卡住时交换 [left] 和 [right] 位置的元素long t array[left];array[left] array[right];array[right] t;}// 说明 left right说明 [left, right) 区间内一个元素都没有了// 所有元素都和 pivot 进行过比较了然后都在各自应该的位置上了// 并且 array[left] 一定是 pivot 的第一个元素不给大家证明了long t array[to];array[to] array[left];array[left] t;// 返回 pivot 最终所在下标return left;}public static void main(String[] args) {long[] array {-1, -1, -1, -1, 8, 7, 6, 5, 4, 3, 2, 1, -1, -1, -1 };int pi partitionMethodA(array, 4, 11);System.out.println(pi);}
}【性能分析】 时间复杂度 最好情况O(n * log(n)) 平均情况O(n * log(n)) 最坏情况O(n^2) 空间复杂度最好 平均 O(log(n))最坏 O(n) 稳定性在划分算法中若右端区间有两个关键字相同且均小于基准值的记录则在交换到左端区间后它们的相对位置会发生变化即快速排序是一种不稳定的排序方法。 适用性
四.归并排序
和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是O(n log n的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。 可以看到这种结构很像一棵完全二叉树本文的归并排序我们采用递归去实现也可采用迭代的方式去实现。分阶段可以理解为就是递归拆分子序列的过程递归深度为log2n。
再来看看治阶段我们需要将两个已经有序的子序列合并成一个有序序列比如上图中的最后一次合并要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列合并为最终序列[1,2,3,4,5,6,7,8]来看下实现步骤。
【算法思想】
【算法实现】
ElemType *B (ElemType *)malloc((n1)*sizeof(ElemType)); //辅助数组B
void Merge(ElemType A[], int low, int mid, int high){//表A的两段A[low...mid]和A[mid1...high]各自有序将它们合并成一个有序表for(int klow; khigh; k){B[k] A[k]; //将A中所有元素复制到B中}for(ilow, jmid1, ki; imid jhigh; k){//从low到midj从mid1到highk是最终排序数组的下标if(B[i] B[j]){ //比较B左右两段的元素A[k] B[i]; //将较小值赋值给AB左段下标加1右段不动}else{A[k] B[j]; //将较小值赋值给AB右段下标加1左段不动}}while(i mid){ //若第一个表左段未检测完复制A[k] B[i];}while(j high){ //若第二个表右段未检测完复制A[k] B[j];}
}【性能分析】 时间复杂度每趟归并的时间复杂度为O ( n )共需进行⌈log_2n⌉趟归并所以算法的时间复杂度为 O(nlog_2n)。 空间复杂度Merge()操作中辅助空间刚好为n 个单元所以算法的空间复杂度为O ( n ) 。 稳定性由于Merge()操作不会改变相同关键字记录的相对次序所以2路归并排序算法是一种稳定的排序方法。
五.基数排序
基数排序也是非比较的排序算法对每一位进行排序从最低位开始排序复杂度为O(kn),为数组长度k为数组中的数的最大的位数
基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数排序基于分别排序分别收集所以是稳定的。
【算法思想】
取得数组中的最大数并取得位数arr为原始数组从最低位开始取每个位组成radix数组对radix进行计数排序利用计数排序适用于小范围数的特点
【算法实现】
void InsertSort(SqList *L){int i,j;//依次将R[2]~R[n]插入到前面已排序序列R[1]为默认排好序的序列R[0]作为哨兵不存放元素for(i2; iL-length; i){//若R[i]关键码小于其前驱将A[i]插入有序表if(L-R[i] L-R[i-1]){L-R[0] L-R[i]; //复制为哨兵R[0]不存放元素//从后往前查找待插入位置for(ji-1; L-R[0]L-R[j]; --j){L-R[j1] L-R[j]; //向后挪位}L-[j1] A[0]; //复制到插入位置}}
}【性能分析】
时间复杂度 最佳情况T(n) O(n * k)最差情况T(n) O(n * k)平均情况T(n) O(n * k)
总结 n: 数据规模k: “桶”的个数In-place: 占用常数内存不占用额外内存Out-place: 占用额外内存
比较和非比较的区别
在冒泡排序之类的排序中问题规模为n又因为需要比较n次所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中问题规模通过分治法消减为logN次所以时间复杂度平均O(nlogn)。 比较排序的优势是适用于各种规模的数据也不在乎数据的分布都能进行排序。可以说比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前应该有多少个元素来排序。针对数组arr计算arr[i]之前有多少个元素则唯一确定了arr[i]在排序后数组中的位置。 非比较排序只要确定每个元素之前的已有的元素个数即可所有一次遍历即可解决。算法时间复杂度O(n)。 非比较排序时间复杂度底但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
