十大经典排序算法

稳定排序：

冒泡排序、插入排序、归并排序

非稳定排序：

选择排序、希尔排序、堆排序、快速排序

1、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。（类似于气泡上浮过程）

动图如下：

步骤：

1、比较相邻的元素，如果第一个比第二个大，则交换

2、对每对相邻元素重复步骤1操作，筛选出最大元素

3、针对所有元素重复步骤1、2（除最后一个元素，已经是最大）

示例代码：
void bubbleSort(std::vector<int> &vecArry) { for (int i = 0;i <
vecArry.size();i++) { for (int j = 0;j < vecArry.size() - i -1;j++) { if
(vecArry[j] > vecArry[j+1]) { int nTemp = vecArry[j]; vecArry[j] =
vecArry[j+1]; vecArry[j+1] = nTemp; } } } } //优化代码 void
bubbleSort(std::vector<int> &vecArry) { bool bSwitch = false; for (int i = 0;i
< vecArry.size();i++) { for (int j = 0;j < vecArry.size() - i -1;j++) { if
(vecArry[j] > vecArry[j+1]) { bSwitch = true; int nTemp = vecArry[j];
vecArry[j] = vecArry[j+1]; vecArry[j+1] = nTemp; } } if (!bSwitch) { return; }
} }
2、选择排序

 从未排序序列中找到最小（最大），放在已排序序列尾部

动图如下：

 步骤：

1、找到排序队列最小（最大）元素，存放在序列起始位置

2、在未排序序列找到最小（最大）元素，放在已排序序列尾部

3、重复1、2步骤

示例代码：
void selectSort(std::vector<int> &vecArry) { for(int i = 0; i <
vecArry.size(); ++i) { int nIndex = i; for (int j = i+1; j <
vecArry.size();++j) { if (vecArry[j] < vecArry[nIndex]) { nIndex = j; } } int
nTemp = vecArry[i]; vecArry[i] = vecArry[nIndex]; vecArry[nIndex] = nTemp; } }
3、插入排序

用未排序序列第一个元素，从已排序序列尾部到起始位置方向开始比较，也就是插入元素和已排序最大元素开始比较，一直找到比它小的元素位置后插入。

动图如下：

步骤：

 1、设置第一个元素为已排序

2、取出下一个元素，在已排序序列尾部向前比较

3、如果该元素（已排序）大于新元素（需插入元素），将该元素移到下一位置

4、重复步骤3，找到已排序元素小于或等于新元素

5、将新元素插入已排序序列

6、重复2~5

示例代码：
void insertSort(std::vector<int> &vecArry) { for (auto i = 1; i <
vecArry.size(); ++i) { int m = vecArry[i]; for (int n = i-1; n >=0; --n) { if
(m < vecArry[n]) { int nTemp = vecArry[n + 1]; vecArry[n+1] = vecArry[n];
vecArry[n] = nTemp; } } } }
4、快速排序

以一个元素为基数，将小于基数的元素移到基数前面，大于基数的元素移到基数后面，对左右区间递归以上步骤，知道区间只有一个数

动图如下：

步骤：

1、选取一个数为基数

2、将比基数小的元素移到基数前面

3、将比基数大的元素移到基数后面 

4、对基数左右区间重复1~3步骤，直到区间只有一个数

示例代码：
void quickSort(std::vector<int> &vecArry,int nLeft,int nRight) { if (nLeft >=
nRight) { return; } int nLow = nLeft; int nHight = nRight; int nBase =
vecArry[nLeft]; while (nLow < nHight) { while( nLow < nHight && nBase<
vecArry[nHight]) { nHight--; } if (nLow < nHight) { vecArry[nLow++] =
vecArry[nHight]; } while (nLow < nHight && nBase > vecArry[nLow]) { nLow++; }
if (nLow < nHight) { vecArry[nHight--] = vecArry[nLow]; } } vecArry[nLow++] =
nBase; quickSort(vecArry,nLeft,nLow-1); quickSort(vecArry,nHight+1,nRight); }
5、希尔排序

希尔排序可以理解成插入排序的优化版本。希尔排序是先将任意间隔为N的元素有序，刚开始可以是N=n/2，接着让N=N/2，让N一直缩小，当N=1,时，此时序列间隔为1有序。

动图如下：

步骤：

1、初始间隔N=数组长度/2

2、对间隔为N的分组进行插入排序，直至有序

3、缩小N值，N=N/2；

4、重复2、3步骤，直至间隔N=1

示例代码：
void shellSortCore(std::vector<int> &vecArry) { int gap = vecArry.size()/2;
while(gap) { for (int i = gap; i < vecArry.size(); i++)//分了多少个组 { int m =
vecArry[i]; for (int n = i - gap; n >=0; --n) { if (m < vecArry[n]) { int nTemp
= vecArry[n + gap]; vecArry[n+gap] = vecArry[n]; vecArry[n] = nTemp; } } }
gap/=2; } }
6、堆排序

堆可以分为大根堆和小根堆，而堆排序是根据堆的数据结构设计的一种排序。

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

动图如下：

步骤：

1、将待排序序列构建成大根堆，此堆为初始无序堆

2、将堆顶元素和最后一个元素交换，此时得到新的N-1无序堆和有序序列

3、重复2直到无序堆为1，此时有序序列为N-1

示例代码：
int nLen = 0; void swap(std::vector<int> &vecArry,int nSrc, int nDes) { int
nTemp = vecArry[nSrc]; vecArry[nSrc] = vecArry[nDes]; vecArry[nDes] = nTemp; }
void funcBuild(std::vector<int> &vecArry, int n) { int left = 2 * n + 1; int
right = 2 * n + 2; int largest = n; if (left < nLen && vecArry[left] <
vecArry[largest]) { largest = left; } if (right < nLen && vecArry[right] <
vecArry[largest]) { largest = right; } if (largest != n) { swap(vecArry, n,
largest); funcBuild(vecArry, largest); } } void heapify_sort(std::vector<int>
&vecArry) { nLen = vecArry.size(); for (int i = nLen/2-1; i >= 0; i--) {
funcBuild(vecArry,i); } for (int j = nLen-1;j >= 0; j--) { swap(vecArry,0,j);
nLen--; funcBuild(vecArry,0); } }
7、计数排序

将待排序序列元素出现次数做为键值存在新开辟数组空间中

动图如下：

步骤：

1、找出待排序序列A最大元素Max

2、新开辟一个Max+1的数组B，初始值为0

3、将序列A中元素值做为数组B索引x，A中元素出现次数做数组B索引为x的值

4、开辟一个长度和A序列大小相同的数组C

5、循环取出数组B的值存入C中，取出一个B值--

示例代码：
void countSort(std::vector<int> &vecArry) { int nMax = 0; for (auto &item :
vecArry) { if (nMax < item) { nMax = item; } } std::vector<int>
vecCount(nMax+1,0); for (int i = 0; i < vecArry.size();i++) {
vecCount[vecArry[i]]++; } std::vector<int> vecResult(vecArry.size(),0); int
nIndex = 0; for (int j = 0; j< vecCount.size();j++) { while(vecCount.at(j) > 0)
{ vecResult[nIndex++] = j; vecCount[j]--; } } }
8、归并排序

归并排序采用分治思想，把待排序序列分成N个子序列，子序列排序后，合并两个子序列实现排序

动图如下：

步骤：

1、把长度为N的序列分成N/2个子序列

2、对子序列进行归并排序

3、将有序子序列合并成一个子序列

示例代码：
void merge(std::vector<int> &vecArry,int nLeft, int nMid, int nRight) { int
nLen = nRight-nLeft+1; int nTempLeft = nLeft, nTempRight = nMid+1; int nIndex =
0; std::vector<int> vecTemp(nLen,0); while (nTempLeft <= nMid && nTempRight <=
nRight) { vecTemp[nIndex++] = vecArry[nTempLeft] <= vecArry[nTempRight] ?
vecArry[nTempLeft++] : vecArry[nTempRight++]; } while(nTempLeft <= nMid) {
vecTemp[nIndex++] = vecArry[nTempLeft++]; } while (nTempRight <= nRight) {
vecTemp[nIndex++] = vecArry[nTempRight++]; } for (int i = 0; i < nLen; i++) {
vecArry[nLeft+i] = vecTemp[i]; } } void mergeSort(std::vector<int> &vecArry,
int nLeft, int nRight) { if (nLeft == nRight) { return; } int nMid = (nLeft +
nRight)/2; mergeSort(vecArry,nLeft,nMid); mergeSort(vecArry,nMid+1,nRight);
merge(vecArry,nLeft,nMid,nRight); }
9、桶排序

桶排序是将数组分别放到有限数量的桶里。每个桶再进行排序。桶排序是鸽巢排序的一种归纳结果

动图如下：

步骤：

1、设置一定数量的空桶

2、遍历待排序序列，将每个元素放入对应桶里

3、对每个不空的桶进行排序

4、从不空的桶将元素从桶中取出

示例代码：
void bucketSort2(std::vector<int> &vecArry) { int nMax = vecArry[0]; for (auto
&value : vecArry) { if (value > nMax) { nMax = value; } } std::vector<int>
vecTemp(nMax+1,0); for (auto &value : vecArry) { vecTemp[value]++; } int nIndex
= 0; for (int i = 0; i < vecTemp.size(); ++i) { while (vecTemp[i] > 0) {
vecArry[nIndex++] = i; vecTemp[i]--; } } } void bucketSort(std::vector<int>
&vecArry) { int nMax = vecArry.at(0); int nMin = vecArry.at(0); for (auto &data
: vecArry) { if (data > nMax) { nMax = data; } if (data < nMin) { nMin = data;
} } int nValue = nMax - nMin;//差值 std::vector<std::vector<int>> vecTemp; int
nLen = vecArry.size();//序列长度 vecTemp.resize(nLen); for (auto &value : vecArry)
{ //nLen-1 个区间 //将差值为nValue平分到nLen-1个区间上 //value-min是当前元素和最小值差值
//nIndex就为(value - nMin)/nValue/(nLen-1) int nIndex = (value -
nMin)/nValue/(nLen-1); vecTemp[nIndex].push_back(value); } for (auto &data :
vecTemp) { insertSort(data); } int nIndex= 0; for (auto &data : vecTemp) {
for(auto &value : data) { vecArry[nIndex++] = value; } } }
10、基数排序

基数排序是按照低位先排序，然后收集，再按照高位排序，再收集，以此类推，直到最高位。

动图如下：

步骤：

1、取待排序序列中最大数，并获取位数

2、从待排序序列每个元素低位相同放到一个radix数组

3、从多个radix数组取出元素，组成新的待排序序列

4、以此重复2、3（步骤2从低到高位）

示例代码：
void radixSort(std::vector<int> &vecArry) //基数排序 { int nLen = vecArry.size();
int nMax = vecArry.at(0); for (auto &value : vecArry) { if (nMax < value) {
nMax = value; } } int nCount = 0; while(nMax) { nMax/=10; nCount++; } int radix
= 1; std::vector<std::vector<int>> vecTemp(10); for (int i = 0; i < nCount;
i++) { vecTemp.clear(); vecTemp.resize(10); for(auto &value : vecArry) { int
nIndex = (value/radix)%10; vecTemp.at(nIndex).push_back(value); } int nIndex =
0; for (auto &value : vecTemp) { for (auto &data : value) { vecArry[nIndex++] =
data; } } radix *= 10; } }

• « 上一篇：5款热门的远程控制软件，让你事半功倍
• » 下一篇：蓝桥杯历年真题你刷了吗？过来人教你逆袭！