十大经典排序算法

博主：想长胖的阿鹏
发布时间：2021 年 10 月 27 日
366次浏览
暂无评论
6418字数
分类：随便写写

> 转载文章，排版可能出现错误，建议到原文阅读：https://blog.csdn.net/qqzhaojianbiao/article/details/120881724

# 稳定排序：

冒泡排序、[插入排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)、归并排序

# 非稳定排序：

选择排序、希尔排序、[堆排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E5%A0%86%E6%8E%92%E5%BA%8F)、快速排序

# 1、冒泡排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYxMGExYTlhMTVkNDc?x-oss-process=image/format,png)

步骤：

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

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

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

示例代码：

```cpp
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、选择排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE5LzE2OTA0MzNkOTFiZGY1YjY?x-oss-process=image/format,png)

步骤：

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

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

3、重复1、2步骤

示例代码：

```cpp
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、[插入排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYxMDk3ZjhjMzUxNTI?x-oss-process=image/format,png)

步骤：

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

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

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

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

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

6、重复2\~5

示例代码：

```cpp
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、快速排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYwZTY5NzE1OGE0Yjk?x-oss-process=image/format,png)

步骤：

1、选取一个数为基数

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

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

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

示例代码：

```cpp
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有序。

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/4110362525.gif)

步骤：

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

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

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

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

示例代码：

```cpp
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、[堆排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E5%A0%86%E6%8E%92%E5%BA%8F)

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

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

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/931438286.png)

步骤：

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

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

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

示例代码：

```java
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、计数排序

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/1128340522.png)

步骤：

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

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

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

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

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

示例代码：

```cpp
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个子序列，子序列排序后，合并两个子序列实现排序

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/782529745.png)

步骤：

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

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

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

示例代码：

```java
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、桶排序

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

动图如下：

![æ¡¶æåº](https://blog.zpzp.xyz/usr/uploads/2021/10/1780718743.gif)

步骤：

1、设置一定数量的空桶

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

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

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

示例代码：

```cpp
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、基数排序

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/2536917051.png)

步骤：

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

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

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

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

示例代码：

```cpp
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;    }}
```

最后修改：2021 年 10 月 27 日 10 : 05 AM

要多恰饭才能长胖

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱

地址

十大经典排序算法

想长胖的阿鹏 • 2021 年 10 月 27 日

> 转载文章，排版可能出现错误，建议到原文阅读：https://blog.csdn.net/qqzhaojianbiao/article/details/120881724

# 稳定排序：

冒泡排序、[插入排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)、归并排序

# 非稳定排序：

选择排序、希尔排序、[堆排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E5%A0%86%E6%8E%92%E5%BA%8F)、快速排序

# 1、冒泡排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYxMGExYTlhMTVkNDc?x-oss-process=image/format,png)

步骤：

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

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

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

示例代码：

# 2、选择排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE5LzE2OTA0MzNkOTFiZGY1YjY?x-oss-process=image/format,png)

步骤：

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

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

3、重复1、2步骤

示例代码：

# 3、[插入排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYxMDk3ZjhjMzUxNTI?x-oss-process=image/format,png)

步骤：

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

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

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

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

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

6、重复2\~5

示例代码：

# 4、快速排序

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

动图如下：

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8yLzE1LzE2OGYwZTY5NzE1OGE0Yjk?x-oss-process=image/format,png)

步骤：

1、选取一个数为基数

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

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

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

示例代码：

# 5、希尔排序

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/4110362525.gif)

步骤：

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

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

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

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

示例代码：

# 6、[堆排序](https://so.csdn.net/so/search?from=pc_blog_highlight&q=%E5%A0%86%E6%8E%92%E5%BA%8F)

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

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

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/931438286.png)

步骤：

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

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

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

示例代码：

# 7、计数排序

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/1128340522.png)

步骤：

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

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

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

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

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

示例代码：

# 8、归并排序

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/782529745.png)

步骤：

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

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

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

示例代码：

# 9、桶排序

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

动图如下：

![æ¡¶æåº](https://blog.zpzp.xyz/usr/uploads/2021/10/1780718743.gif)

步骤：

1、设置一定数量的空桶

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

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

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

示例代码：

# 10、基数排序

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

动图如下：

![](https://blog.zpzp.xyz/usr/uploads/2021/10/2536917051.png)

步骤：

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

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

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

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

示例代码：

十大经典排序算法

发表评论取消回复

CentOS通过yum升级Openssh8.x

欢迎使用 Typecho

甲骨文云 Oracle Cloud 免费 ARM 实例硬盘扩容

OpenVZ架构一键开启BBR加速的方法

libvirt 启用TCP远程连接，windows平台java调用示例

js动态加载script脚本

相爱100件事

flask_apscheduler的app上下文问题

CentOS7.6升级内核

CentOS7下swap分区创建(添加),删除以及相关配置

十大经典排序算法

发表评论 取消回复

十大经典排序算法

发表评论取消回复