前言:


写在这篇博客前面,最近发现自己做事学东西远没有以前的踏实,往往学过之后很快就忘记,包括基础的排序算法,虽然看过几遍,但是却没有真正掌握,到了突然需要自己抛开书本手写的时候,发现自己对它们其实挺陌生的。所以希望借写这篇博客的机会,让自己好好复习一下基本的排序算法,也希望自己从现在开始能做到学东西像之前一样踏实。

这篇博客中包含的排序算法主要有:冒泡排序,插入排序,希尔排序,选择排序,堆排序,归并排序,快速排序,计数排序,基数排序,桶排序。

冒泡排序:

冒泡排序是一种很简单的排序算法,也是大多数人所学的第一种排序算法,其基本思想
是“比较相邻元素,将大的元素放后边,小的放前边,每一轮比较,总有一个最大元素被‘冒’到数组最后边。”N轮比较下来,就完成了排序。

* 时间复杂度:O(n2)O(n2)
* 空间复杂度:原址排序
* 是否稳定:是
* 应用场景:优化后的冒泡排序可用于当数据已经基本有序,且数据量较小时。
* 优化措施:设置一个标志,每轮比较时,如果发现没有进行交换操作,说明数组已经有序,退出循环,停止比较。
* 代码: /*冒泡排序*/ void BubbleSort(vector<int>& arr) { int len = arr.size(); if
(len ==0) return; bool change = false; for (int i = 0; i < len; i++) { for (int
j =1; j < len - i; j++) { if (arr[j] < arr[j - 1]) { swap(arr[j], arr[j - 1]);
change =true; } } if (!change) break; } return; }
插入排序:

插入排序也是一种基本的排序算法,它的基本思想
类似于我们抓扑克牌。开始时,我们的左手为空,然后我们每次从牌堆中拿走一张牌并插入到正确的位置;为了找到每一张牌的正确位置,需要将它从右到左与每一张牌比较,直到找到小于它的那张牌,保证左手的牌随时都是有序的,同样N轮插入操作下来,数组有序。

* 时间复杂度:O(n2)O(n2)
* 空间复杂度:原址排序
* 是否稳定:是
* 应用场景:若数组基本有序且数据规模较小时,选用插入排序较好.
* 优化措施:由于每次插入是向已排序数组中插入,可使用二分查找查找到相应位置进行插入.
* 代码: /*插入排序*/ void InsetionSort(vector<int>& arr) { int len = arr.size(); for
(int i = 1; i < len; i++) { int idx = i; while (idx > 0 && arr[idx - 1] >
arr[idx]) {int ntmp = arr[idx]; arr[idx] = arr[idx - 1]; arr[idx - 1] = ntmp;
idx--; } }return; }
希尔排序:

希尔排序是对插入排序的一种改进,其改进思想来源于“序列越基本有序,插入排序效率越高”;该算法是第一批突破O(n2)时间复杂度的排序算法。基本思想:
先将整个待排记录序列分割成若干列,即若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

* 时间复杂度:小于O(n4/3)O(n4/3)
* 空间复杂度:原址排序
* 是否稳定:否
* 注:对于希尔排序涉及到一个增量步长的选择,具体选择标准可参照WIKI Gap_sequence
<https://en.wikipedia.org/wiki/Shellsort#Gap_sequences>
* 应用场景:数据量较小且基本有序时
* 代码: /*希尔排序*/ void ShellSort(vector<int>& arr) { int len = arr.size(); if
(len ==0) return; vector<int> gaps = { 1,3,7,15,31,63,127,255,511,1023 }; int
idx = gaps.size() -1; while (idx >= 0) { int span = gaps[idx];
//从第二行开始对每列数进行插入排序 for (int i = span; i < len; i++) { for (int j = i; j >=
span; j -= span) {if (arr[j] >= arr[j - span]) break; int ntmp = arr[j]; arr[j]
= arr[j - span]; arr[j - span] = ntmp; } } idx--; }return; }
选择排序:

选择排序也是一种简单直观的排序算法,它的基本思想也很简单直观:每次总是选择未排序序列中最小(或最大)的元素,放置在已排序序列最后或最前即可。

* 时间复杂度:O(n2)O(n2)
* 空间复杂度:原址排序
* 是否稳定:否
* 应用场景:当数据规模较小时,选择排序性能较好
* 优化措施:每次寻找最小或最大元素时,同时记录最小最大元素的位置,每次使用3次比较寻找两个元素的位置,而不是4次比较
* 代码: /*选择排序*/ void SelectionSort(vector<int>& arr) { int len = arr.size(); if
(len ==0) return; int idx = 0; int min = 0; for (int i = 0; i < len; i++) {
min = arr[i];for (int j = i; j < len; j++) { if (arr[j] < min) { min = arr[j];
idx = j; } }int ntmp = arr[idx]; arr[idx] = arr[i]; arr[i] = ntmp; } return; }
堆排序


堆排序利用了二叉堆的性质,维护一个数组,数组可被看成一个近似的完全二叉树,堆顶总是储存数组中最大(或最小)的元素;每次将堆中最大元素取出,与数组最后一位数交换,堆大小减一,这个操作破坏了堆的性质(堆顶不一定为最大元素),于是维护堆的性质,下沉堆顶元素,反复操作后即可得到有序数组。

* 时间复杂度:O(nlog(n))O(nlog(n))
* 空间复杂度:原址排序
* 是否稳定:否
* 应用场景:堆排序适合处理数据量大的情况,数据呈流式输入时用堆排序也很方便
* 优化措施:建立堆的时候不需要对叶子结点进行维护堆性质操作,因此只需要对n/2个数进行维护堆操作
* 代码: /*堆排序*/ int parent(int i) { return i / 2; } int left(int i) { return 2
* i; }int right(int i) { return 2 * i + 1; } void maxHeapIfy(vector<int>& arr,
int heap_size, int i) { int l = left(i); int r = right(i); int largest = 0; if
(l < heap_size&&arr[l] > arr[i]) largest = l;else largest = i; if (r <
heap_size&&arr[r] > arr[largest]) largest = r;if (largest != i) { int ntmp =
arr[i]; arr[i] = arr[largest]; arr[largest] = ntmp; maxHeapIfy(arr, heap_size,
largest); } }void buildMaxHeap(vector<int>& arr, int heap_size) { for (int i =
heap_size /2; i >= 0; i--) { maxHeapIfy(arr, heap_size, i); } } void HeapSort(
vector<int>& arr) { int len = arr.size(); int heap_size = len; if (len == 0)
return; buildMaxHeap(arr, heap_size); for (int i = len - 1; i > 0; i--) { int
ntmp = arr[i]; arr[i] = arr[0]; arr[0] = ntmp; heap_size--; maxHeapIfy(arr,
heap_size,0); } }
归并排序


归并排序在结构上是递归的,归并排序每一次递归将原数组均分为规模较小的两个部分,直到无法再分为止,此时每一个部分只有一个元素,那么自然是有序的,于是递归开始自下往上进行合并;
合并时,新建一个数组,长度等于两个子数组长度之和,依次比较两个子数组中的元素,每次将较小的元素放进新数组即可;
对于归并排序,每一层递归将原数组均分成了两部分,于是递归树一共logn+1logn+1 层,每一层最多进行n次比较,所以时间复杂度为 nlognnlogn


* 时间复杂度:O(nlogn)O(nlogn)
* 空间复杂度:O(n)O(n)
* 是否稳定:是
* 应用场景:数据量较大且要求排序稳定时
* 优化措施:由于使用递归,递归深度太深容易造成内存溢出,所以可使用非递归版本归并排序
* 代码: /*归并排序*/ void Merge(vector<int>& arr, int p, int q, int r) { int len1 =
q - p +1; int len2 = r - q; vector<int> arr1; vector<int> arr2;
arr1.assign(arr.begin() + p, arr.begin() + p + len1); arr2.assign(arr.begin() +
p + len1, arr.begin() + p + len1 + len2);int idx1 = 0; int idx2 = 0; for (int i
= p; i <= r; i++) {if (idx1 >= len1) { arr[i] = arr2[idx2]; idx2++; } else if
(idx2 >= len2 || arr1[idx1] <= arr2[idx2]) { arr[i] = arr1[idx1]; idx1++; }else
{ arr[i] = arr2[idx2]; idx2++; } }return; } void MergeSort(vector<int>& arr, int
p,int r) { if (p < r) { int q = (p + r) / 2; MergeSort(arr, p, q);
MergeSort(arr, q +1, r); Merge(arr, p, q, r); } }
快速排序

快速排序是一种最坏情况时间复杂度为O(n2)O(n2)的排序算法,但是快速排序通常是实际排序应用中最好的选择,因为它的平均性能非常好O(nlogn)O(nlo
gn)。
快速排序算法每次选择一个基准元素,将小于基准元素的数放到左边,大于基准元素的数放到右边,递归的重复这个划分过程,直到需要划分的数组中只有一个元素,结束递归。

* 时间复杂度:O(nlogn)O(nlogn)
* 空间复杂度:原址排序
* 是否稳定:否
* 应用场景:快速排序适合处理大量数据排序时的场景
*
优化措施:由于如果每次选取基准元素时都选到了最小或最大的元素,会导致快排时间复杂度很高,所以可以随机选取基准元素,能有效的提高排序的平均性能,防止时间复杂度达到
O(n2)O(n2)。
* 代码: /*快速排序*/ int partition(int p, int r, vector<int>& arr) { if (r - p < 1)
return -1; srand((unsigned)time(NULL)); int ele = rand() % (r - p + 1) + p;
//生成随机数,随机选取基准元素 int pivot = arr[ele]; int idx = p; for (int i = p; i < r; i++)
{if (arr[i] < pivot) { swap(arr[i], arr[idx]); idx++; } } swap(arr[r],
arr[idx]);return idx; } void QuickSort(vector<int>& arr, int p, int r) { int q
= partition(p, r, arr);if (q != -1) { QuickSort(arr, p, q - 1); QuickSort(arr,
q +1, r); } return; }
计数排序

本篇博客以上排序算法均属于非线性时间排序算法,现在开始介绍三种线性时间排序算法。由于以上排序均依赖于元素之间的比较,任何比较排序在最坏情况下都需要O(nlog
n)O(nlogn) 的时间复杂度,接下来的三种排序算法均可打破这个限制。
限制:计数排序假设n个输入元素中的每一个元素都是在0到k区间内的一个整数,只可处理非负数;计数排序的基本思想
:对每一个元素x,确定小于x的元素个数,利用这一信息,就可以直接把x放到输出排序数组的正确位置上了。

* 时间复杂度:O(n)O(n)
* 空间复杂度:O(n)+O(N)O(n)+O(N)
* 是否稳定:是
* 应用场景:计数排序虽然时间复杂度较低,但需要满足的条件较多,如果能满足限制条件与空间需求,计数排序自然很快
* 优化措施:为了保障稳定性,算法中进行了多余的操作,如果不需要稳定性,可以优化时间。
* 代码: /*计数排序*/ void CountingSort(vector<int>& arr, int max_elem) { int len =
arr.size();if (len == 0) return; vector<int> extraArr(max_elem + 1); for (int i
=0; i < len; i++) { extraArr[arr[i]]++; } for (int i = 1; i <= max_elem; i++)
extraArr[i] = extraArr[i] + extraArr[i -1]; //画出直方图 vector<int> copyArr;
copyArr.assign(arr.begin(), arr.end());for (int i = len - 1; i >= 0; i--) {
arr[extraArr[copyArr[i]] -1] = copyArr[i]; extraArr[copyArr[i]]--; //防止有重复元素 }
return; }
基数排序


基数排序是基于计数排序的,基数排序着眼于输入序列的每一位数,每一轮排序都是根据序列中的某一位数进行排序,从低位到高位各进行一次这种排序思想,最终序列便是有序的。由于输入序列每一位数都是有限的,比如十进制序列,每位数都是0~9的数字,于是可以选择计数排序对序列某一位数进行排序。同样,基数排序也不能处理非负数。

* 时间复杂度:O(n)O(n)
* 空间复杂度:O(n)O(n)
* 是否稳定:是
* 应用场景:同计数排序
* 代码: /*基数排序*/ void RadixSort(vector<int>& arr, int max_elem) { int len =
arr.size();if (len == 0) return; int exp_max = 1; int radix = 10; //十进制序列 while
(max_elem / exp_max >0) exp_max *= radix; int exp = 1; vector<int>
countArr(radix);vector<int> exchangeArr; exchangeArr.assign(arr.begin(),
arr.end());while (exp < exp_max) { for (int i = 0; i < len; i++)
countArr[(exchangeArr[i] /exp) % radix]++; for (int i = 1; i < radix; i++)
countArr[i] = countArr[i] + countArr[i -1]; for (int i = len - 1; i >= 0; i--) {
int tmp = countArr[(exchangeArr[i] / exp) % radix] - 1;
arr[countArr[(exchangeArr[i] /exp) % radix] - 1] = exchangeArr[i];
countArr[(exchangeArr[i] /exp) % radix]--; } exchangeArr.assign(arr.begin(),
arr.end()); countArr.assign(radix,0); exp *= radix; } return; }
桶排序

桶排序假设输入数据服从均匀分布,防止所有元素集中在少数几个桶中,平均情况下它的时间代价为O(n)O(n) 。基本思想:
桶排序将[0,1)区间划分为n个相同大小的子区间,也就是桶,然后将n个输入数据分别放到各个桶中,为了得到输出结果,我们队每个桶中的数进行插入排序,最后遍历所有桶按照次序输出数据即可。

* 时间复杂度:O(n)O(n)
* 空间复杂度:O(n)O(n)
* 是否稳定:是
* 应用场景:如果满足桶排序的假设条件,那么桶排序的速度是非常快的
* 代码: /*桶排序*/ void BucketSort(vector<int>& arr, int max_elem) { int len =
arr.size();if (len == 0) return; int radix = 1; while (radix < max_elem) radix
*=10; int idx = 0; vector<vector<int> > bucket(len); for (int i = 0; i < len;
i++) { idx = len*(arr[i] / (double)radix); bucket[idx].push_back(arr[i]); } idx
=0; for (int i = 0; i < len; i++) { sort(bucket[i].begin(), bucket[i].end()); if
(!bucket.empty()) {for (int j = 0; j < bucket[i].size(); j++) { arr[idx] =
bucket[i][j]; idx++; } } }return; }
总结

本文一共总结了10种排序算法,其中
基于比较的排序算法有:冒泡排序,插入排序,希尔排序,选择排序,归并排序,堆排序,快速排序;
线性时间排序算法包括:计数排序,基数排序,桶排序;

前边有提到过,基于比较的排序算法,时间复杂度最差达到O(nlogn)O(nlogn),无法突破这个界限,只有线性时间排序能够突破,达到O(n)O(n)
,所以说,如果满足了线性时间排序算法的限制条件,使用线性时间排序将会使排序性能得到极大提升。
下面对以上涉及到的每种算法做一个简单的实际测试对比:利用随机数,随机生成区间0 ~
K之间的序列,共计N个数字,利用各种算法进行排序,记录排序所需时间,测试环境为i7+vs2015+Debug版本。

算法\输入数据 N=50 K=50 N=200 K=100 N=500 K=500 N=2000 K=2000 N=5000 K=8000 N=10000
K=20000 N=20000 K=20000 N=20000 K=200000
冒泡排序 0ms 15ms 89ms 1493ms 9363ms 36951ms 147817ms 143457ms
插入排序 1ms 13ms 82ms 1402ms 8698ms 34731ms 134817ms 134836ms
希尔排序 0ms 1ms 6ms 30ms 110ms 257ms 599ms 606ms
选择排序 0ms 5ms 31ms 461ms 2888ms 11736ms 45308ms 44838ms
堆排序 0ms 3ms 9ms 40ms 124ms 247ms 525ms 527ms
归并排序 2ms 6ms 18ms 75ms 199ms 392ms 778ms 793ms
快速排序 0ms 1ms 2ms 14ms 36ms 84ms 196ms 163ms
计数排序 0ms 1ms 1ms 5ms 15ms 32ms 51ms 62ms
基数排序 0ms 1ms 4ms 19ms 47ms 114ms 237ms 226ms
桶排序 0ms 2ms 6ms 25ms 68ms 126ms 254ms 251ms
性能对比小结:
1. 传统简单排序确实当数据量很小的时候也表现不错,但当数据量增大,其耗时也增大十分明显;
2. 冒泡,插入,选择三种排序中,当数据量很大时,选择排序性能会更好;
3. 堆排,希尔,归并,快排几种排序算法也表现不错,源于其时间复杂度达到了O(nlogn)O(nlogn);
4. 随机快速排序性能确实表现十分亮眼,甚至有时比基数排序和桶排序还好,这可能也是快排如此流行的原因;
5. 线性排序中计数排序表现最好,但他们的限制也比较明显,只能处理范围内的正整数。

下面贴上测试代码,博主以上算法只有部分是优化过的,有兴趣的还可以将优化措施都加上,再进行性能表现对比。
int main() { clock_t start, end; srand((unsigned)time(NULL)); int N = 50; //
数据个数 intK = 50; //数据上限 vector<int> arr(N); vector<int> arr2; int max_elem = 0;
for (int i = 0; i < N; i++) { arr[i] = rand() % K; if (arr[i] > max_elem)
max_elem = arr[i]; } arr2.assign(arr.begin(), arr.end()); start = clock();
BubbleSort(arr); end = clock(); cout << "冒泡排序:" << end - start << endl;
arr.assign(arr2.begin(), arr2.end()); start = clock(); InsetionSort(arr); end =
clock(); cout <<"插入排序:" << end - start << endl; arr.assign(arr2.begin(), arr2.
end()); start = clock(); ShellSort(arr); end = clock(); cout << "希尔排序:" << end
- start << endl; arr.assign(arr2.begin(), arr2.end()); start = clock();
SelectionSort(arr); end = clock(); cout << "选择排序:" << end - start << endl;
arr.assign(arr2.begin(), arr2.end()); start = clock(); HeapSort(arr); end =
clock(); cout <<"堆排序:" << end - start << endl; arr.assign(arr2.begin(), arr2.end
()); start = clock();MergeSort(arr, 0, N - 1); end = clock(); cout << "归并排序:" <<
end - start << endl; arr.assign(arr2.begin(), arr2.end()); start = clock();
QuickSort(arr, 0, N - 1); end = clock(); cout << "快速排序:" << end - start <<
endl; arr.assign(arr2.begin(), arr2.end()); start = clock(); CountingSort(arr,
max_elem);end = clock(); cout << "计数排序:" << end - start << endl;
arr.assign(arr2.begin(), arr2.end()); start = clock(); RadixSort(arr, max_elem);
end = clock(); cout << "基数排序:" << end - start << endl; arr.assign(arr2.begin(),
arr2.end()); start = clock(); BucketSort(arr, max_elem); end = clock(); cout <<
"桶排序:" << end - start << endl; system("pause"); return 0; }

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信