C++实现常用八大排序算法 |
您所在的位置:网站首页 › 堆排序和快速排序的区别 › C++实现常用八大排序算法 |
每种排序算法都各有优缺点。 影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点: 1.待排序的记录数目n的大小; 2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小; 3.关键字的结构及其分布情况; 4.对排序稳定性的要求。 设待排序元素的个数为n. 1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; 堆排序 : 如果内存空间允许且要求稳定性的, 归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。2) 当n较大,内存空间允许,且要求稳定性 ——归并排序 3)当n较小,可采用直接插入或直接选择排序。 直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。 直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序5)一般不使用或不直接使用传统的冒泡排序。 6)基数排序 它是一种稳定的排序算法,但有一定的局限性: 1、关键字可分解。 2、记录的关键字位数较少,如果密集更好 3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。 插入排序: 直接插入排序 希尔排序 直接插入排序 :思想:将数组中的所有元素依次和前面的已经排好序的元素相比较(依次),如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过。 代码实现: Sort.h: #pragma once #include using namespace std; #include //直接插入排序 void InsertSort (int* a,size_t n) { assert(a); for(size_t i = 1;i < n; ++i)//用end的位置控制边界 { //单趟排序 int end = i - 1 ; int tmp = a[i]; while( end >= 0 )//循环继续条件 { if( a[end] > tmp ) { a[end+1] = a[end]; --end; } else break; } a[end+1] = tmp; } }test.cpp : #include "Sort.h" void Print(int a[],int len) { for(int i = 0; i < len; ++i) { cout a[i] ) { swap(a[i-1],a[i]); exchange = 1; } } if( 0 == exchange )//数组本身为升序,如果一趟排序结束,并没有进行交换,那么直接跳出循环(减少循环次数,升高效率) break; --end; } } #### 快速排序排序算法:详情请见我的另外一篇文章: 快速排序算法—左右指针法,挖坑法,前后指针法,递归和非递归 https://blog.csdn.net/qq_37941471/article/details/80522354 归并排序: 思想:分治法每个递归过程涉及三个步骤 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序__MergeSort, 进行递归操作 第三, 合并: 合并两个排好序的子序列,生成排序结果. |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |