此文将以总分的形式对排序算法进行梳理与总结，用于学习或复习使用，接下来请跟随代码骑士一起搞定排序算法吧。
=========================================================================
目录
一、（总--化整为零）
A、按排序方式分类：
1、插入排序：
（1）直接插入排序
（2）希尔排序
2、交换排序：
（3）冒泡排序
（4）快速排序
3、选择排序：
（5）简单选择排序
（6）堆排序
4、归并排序：
（7）二路归并排序
5、计数排序
（8）计数排序
6、基数排序
（9）基数排序
7、桶排序
（10）桶排序
B、按排序方法分类：
二、（分-化零为整）
（1）直接插入排序：
（2）希尔排序：
（3）冒泡排序：
（4）快速排序：
（5）简单选择排序：
（6）堆排序：
（7）归并排序：
（8）计数排序：
（9）基数排序：
（10）桶排序：
=========================================================================
一、（总--化整为零） A、按排序方式分类：经典的十大排序算法：
（图示）
B、按排序方法分类：(图示)
B1、排序过程中需要进行比较的有：
插入、交换、选择、归并；
B2、排序过程中不需要进行比较的有：
计数、桶、基数。
若你和代码骑士是校友并且对排序算法还不是那么熟悉，那么一定要掌握这三种：
（a）直接插入排序
（b）简单选择排序
（c）冒泡排序
老师重点强调过，同时也比较好理解。
=========================================================================
二、（分-化零为整） （1）直接插入排序：1、思想：
依次将待排序列中的每一个记录插到已排好的序列中，直到全部记录都排好序。
实例类似于生活中打牌时，每从牌堆里摸一张牌都要与手里摆好的牌进行比较然后找到相应位置把它插入。
2、如何写代码：
（1）思想：假设一组无序数列存储在一维数组当中，我们想把它们排好序，我们可以把这些无序的数想象成一组洗好的牌，现在我们就来摸第一张牌，并把它放在数组的第一个位置上设为Data[0]，因为只有一张牌不需要跟任何牌比较就默认成已排好。那么接下来再摸第二张牌也就是Data[1]，因为我们摆牌时，大部分人习惯上喜欢按从左到右依次增大的顺序摆牌，那就默认我们的摆好的牌顺也是从小到大的。
摸到第二张牌后，因为手里已经有了一张牌Data[0],此时我们要判断Data[1]是否比Data[0]的值要小，如果比它小，那么就要把Data[0]这张牌向后挪动一位，给Data[1]腾出空间来把它插入。挪动的过程中有个需要解决的编程问题，设我们 *** 作的顺序是：先比较->再挪动->最后再插入。那么挪动的过程是把Data[0]直接赋值给它的下一位Data[1],那么此时的Data[1]值就变成了Data[0]的值了，也就是原来的Data[1]已经被Data[0]覆盖了，这时我们再把Data[1]插入到Data[0]的位置上去，那么此时手里的牌是两张一样的Data[0]了，这可不是我们想看到的，打牌时这可是恶劣的出老千行为！所以我们需要再往后挪动Data[0]之前，找一个临时的变量将Data[1]的值存在里面，然后插入时将这个临时变量插入到Data[0]的位置即可。这样就能解决原Data[1]值被覆盖的问题了。这个临时变量就像是我们的摸牌手，在没插入之前无序的牌都是经过这只手才能插入到摆好的牌堆里的。所以上面的 *** 作顺序需要改成：先抓牌->再比较->再挪动->再插入，就没有问题了。
接着，再摸第三张，第四张……都是同样的道理。
3、插入函数源代码：
void Insert(int* a, int aLen)//a是待排数组，aLen是待排数组长度
{
for (int i = 1; i < aLen; i++)//从下标1开始，因为下标0默认排好
{
int temp = a[i];//摸牌手抓牌
for (j = i - 1; j >= 0 && temp < a[j]; j--)
{
a[j + 1] = a[j];//把比temp大的数依次往后移动一位
a[j] = temp;//将temp插入到原a[j]的位置
}
}
}
4、性能：
时间复杂度：O(n*n)~O(n)~O(n*n)
空间复杂度：O(1)
稳定性：稳定
简单性：初级
5、D-OJ练习题：
D-OJ刷题日记：直接插入排序验证性实验 题目编号:584_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121339450?utm_source=app&app_version=4.18.0&code=app_1562916241&ulinkId=usr1mkqgl919blen
（2）希尔排序：1、思想：
由于直接插入排序在序列无序状态下插入效率极低，在1959年希尔提出了一种将一个无序数列通过一个增量分割成多个子序列，在分别对子序列进行排序的算法，此算法名为”希尔排序“，也称”缩小增量排序“。此算法能将一串无序数列基本有序化，使得在对整体进行直接插入时的效率更高。
大致步骤分为：
设置增量->分割->直插排序->缩小增量->分割->直插排序->缩小增量->……->增量为1->直插排序
2、如何写代码：
(1)思想：第一步先取增量。到目前为止，尚未有人求得过一个最好的增量序列。希尔最早提出的方法是d1= n/2，di+1 = di/2，……，dn = 1且增量序列d1,d2,d3……dn互质。
开始时的增量取值较大，每个子序列中的记录个数就少，这样移动的个数也少，排序效率就高；后来增量逐步减小，虽然每个子序列中的数的个数增加，但是已基本有序，这样移动的个数还是较少，便能大大提高直接插入排序的效率。
在进行子序列的直插排序时，我们首先联想一下普通的直插排序，比较时是用Data[i]和Data[i-1]进行比较的，可以理解成这是增量为1的插入排序！那么如果增量不为1，比较时是用Data[i]与前面的Data[i-d]进行比较的。如果Data[i]比Data[i-d]小，那就将Data[i]赋值给临时变量temp，然后Data[i-d]向后挪,赋值给Data[i](写成Data[i] = Data[i-d]),然后Data[i-d] = temp，完成插入。
3、希尔排序函数源代码：
void Shell(int* a, int aLen)
{
int i = 0, j = 0, d, temp;//设置增量与暂存值
for (d = aLen / 2; d >= 1; d = d / 2)//增量为d进行直接插入排序，增量 = 1，进行的是最后一次插入
{
for (i = d; i < aLen; i++)//进行一趟希尔排序
{
temp = a[i];//抓牌
for (j = i - d; j >= 0 && temp < a[j]; j = j - d)
{
a[j + d] = a[j];//后移
a[j] = temp;//空出来的位置插入temp
}
}
}
}
4、性能：
时间复杂度：O(nlog2n)~O(n^1.3)~O(n*n)
空间复杂度：O(1)
稳定性：不·稳定
简单性：中级
5、D-OJ练习题：
(2条消息) D-OJ刷题日记：希尔排序验证性实验 题目编号:587_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121351620
（3）冒泡排序：1、思想：
两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。
2、如何写代码：
（1）思想：假设一组无序数列存在一维数组中，根据相邻交换的思想，如果从数组第一个位置Data[0]开始排序，第一次Data[0]与Data[1]相比较，若Data[0]比Data[1]大，则Data[0]与Data[1]互换位置，若Data[0]比Data[1]小，则二者相对位置不变。接下来让Data[1]与Data[2]比较，若Data[1]比Data[2]大，则互换二者的位置，反之，二者相对位置不发生变化。然后再让Data[3]与Data[4]相比较，若Data[3]比Data[4]大，则二者互换位置，反之，二者相对位置不变。往后以此类推，Data[i]与Data[i+1]比较,若Data[i]比Data[i+1]大，则二者互换位置，反之，则相对位置不变。
如果有n个无序数要进行冒泡排序，从第一个记录开始比较，循环要进行n-1趟。因为每进行一趟比较都会有一个最大的（或最小的）数排到数组的末尾，这样N个数再进行了n-1次后，已经有n-1个数按有序数列排好了，最后一个数还需要排吗？显然，不需要了。
3、冒泡函数源代码：
void Bubble(int* a, int aLen)
{
int temp;//交换时的临时存储变量
for (int i = 1; i <= aLen-1; i++)//总趟数：n-1
{
for (int j = 0; j < aLen - i; j++)//每进行一趟就排好一个，那么每次相邻比较的次数就是aLen - i次
{
if (a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
4、性能：
时间复杂度：O(n*n)~O(n*n)~O(n*n)
空间复杂度：O(1)
稳定性：稳定
简单性：初级
5、D-OJ练习题：
(4条消息) D-OJ刷题日记：起泡排序验证性实验 题目编号:586_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121340185
（4）快速排序：1、思想：
学完冒泡排序我们知道，在冒泡排序中记录的比较和移动是在相邻的位置间进行的，记录每次交换只能向后移动一个位置，因此这种方式比较和移动的次数都比较多。为了改进这种算法，我们从前后两端向中间开始遍历，比较前后两端的记录大小，如果前面的比后面的值大就交换否则就继续遍历；直到两边的游标都指向中间的同一个值时，我们说这个过程是完成了一次划分。而这个中间值就称作轴值。然后我们在把轴值两边的子序列再次用这种方式进行划分，只要各个子序列的下标值首端小于尾端那么就将这种划分就一直进行下去，直到每个子序列都找到自己的轴值时，划分就结束了同时各个序列也就全部排好了。所以，通过每次记录移动较远的距离减少比较和移动次数的排序方式我们称之为快速排序，这种排序方法运用了算法中典型的分治递归思想。
2、如何写代码：
假设有一组无序数列存储在一维数组当中，运用快速排序的思想，我们要先对整个序列进行一次划分。划分时首先要定义两个游标，分别指向前后两端的数组元素的下标，同时定义一个temp用来存储临时变量，因为在划分过程中可能会进行记录位置的互换。划分开始的条件是后面游标的位置大于左边游标的位置（设i是前面的游标，j是后面的游标。开始条件为：i < j），游标可以先从左移动也可以先从右移动，默认从右边开始扫描。当i < j并且Data[i]<=Data[j]时，不需要交换，那就使 j 继续向前扫描，当Data[i] > Data[j]时右侧扫描结束，前后记录交换同时使左游标 i ++，开始进行左侧扫描，步骤与右侧扫描相似。当 i = j 时，整个序列的扫描就都结束了，此时的游标 i 和 j 都指向中间的轴值位置。再将这个轴值看作左子序列的尾端，右子序列的首段，在进行一次递归划分，直到每个序列的游标都指向各自的轴值时，整个的序列就排好序了。.
3、快速排序函数源代码：
（1）划分函数
int Partition(int *a, int first, int last)//快排划分
{
int i = first, j = last, temp;
while (i < j)
{
while (i < j && a[i] <= a[j]) j--;
if (i < j)
{
temp = a[i];//Swap
a[i] = a[j];
a[j] = temp;
i++;//前游标后移
}
while (i < j && a[i] <= a[j]) i++;
if (i < j)
{
temp = a[i];//Swap
a[i] = a[j];
a[j] = temp;
j--;//后游标前移
}
}
return i;//返回轴值位置
}
（2）快速排序函数(递归)
void Quick(int* a, int first, int last)
{
int pivot;//定义轴值
if (first >= last) return;
else
{
pivot = Partition(a, first, last);
Quick(a, first, pivot-1);
Quick(a, pivot+1,last);
}
}
4、性能：
时间复杂度：O(nlog2n)~O(nlog2n)~O(n*n)
空间复杂度：O(log2n~n)
稳定性：不稳定
简单性：中级
5、D-OJ练习题：
D-OJ刷题日记：快速排序验证性实验 题目编号:589_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121373832
（5）简单选择排序：1、思想：
把一组无序数列分成两部分也可以视为两个集合，左边的集合是已排好的有序数列，右边的是未排好的待排序列，假设有n个数，那么就进行n趟比较，每一趟都在待排序列中挑出最小的记录与待排序列的第一个记录进行交换。这样排好的序列记录为i个，那么待排的序列记录就是n-i个，当进行了n次选择（i = n）后，待排序列中个数为0，那么此时的数列就已经排好了。
2、如何写代码:
(1)思想：假设一组无序数列存储在一维数组中，根据选择排序的思想，视整个数组为无序数列，那么Data[0]就是无序数列的首位记录，接下来要在Data[1]~Data[n]中找到一个最小的元素并与Data[0]交换，这样就完成了一次简单的选择排序。接下来，Data[0]是我们已排好的元素，那么它的下一位Data[1]就变成了未排元素的首位，那么再从Data[2]~Data[n]中选择出最小的元素与Data[2]进行交换，此时排好的元素为Data[0]和Data[1]。依次类推，当我们有 i 个元素已经拍好的时候，就在剩下的 n - i 个元素里面找最小的。编程时需要注意的问题是，如果待排序列的首元素就是最小的值，那么不需要交换位置，这里可以设一个变量来进行判断。
3、简单选择排序函数源代码：
void simpleSelect(int* a, int aLen)
{
int index, temp;
for (int i = 0; i < aLen - 1; i++)//进行n-1次选择
{
index = i;//待排序列的首元素下标
for (int j = i + 1; j < aLen; j++)//在无序数列中选择一个最小的
{
if (a[j] < a[index])//indext表示最小元素下标（是随无序数列中j变化的）
index = j;//找到最小值下标（这是一个过程……）
}
if (index != i)
{
temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
}
4、性能：
时间复杂度：O(n*n)~O(n*n)~O(n*n)
空间复杂度：O(1)
稳定性：不稳定
简单性：初级
5、D-OJ练习题：
(4条消息) D-OJ刷题日记：简单选择排序验证性实验 题目编号:585_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121348855
（6）堆排序：1、思想：
学完简单选择排序我们可以知道，简单选择排序每选择一个最小值都要在待排序列中通过比较找到一个最小的，这种方式比较次数过多。那么，有没有一种方法在选择出一个最小记录后次小记录也能很快找到呢？基于这种想法，堆排序出现了。
堆是一种有特殊属性的完全二叉树。如果每个结点的值都小于等于其左右孩子结点，那么这棵树称为小根堆；如果每个结点的值都大于等于其左右孩子结点，那么这棵树称为大根堆。
且它还具有完全二叉数的这种性质：把各个结点放在数组中排列，下标为 i 的记录的左孩子下标为 2i ，右孩子为 2i + 1 。
堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，当记录中的数据发生变化，完全二叉树的结点就会发生改变，这时，我们为了维护原有的堆的性质，就要对堆进行调整。那么我们该如何调整呢？
这个例子可以看出，在堆调整的过程中，总是将根结点（被调整的结点）与左右孩子进行比较，若不满足堆的条件，则将根结点与左右孩子中最大的进行交换。这个过程一直进行到所有子树均为堆或将别调整结点交换到叶子结点为止。
堆排序：
2、如何写代码：
堆调整：
将完全二叉树存储到Data[0]~Data[n-1]中，则Data[i]的左孩子是Data[2*i+1],右孩子是Data[2*i+2]。所以，堆调整就是从第k个结点开始与其左右孩子进行比较，比较所指的一般为左右孩子中的最大者，如果根结点小于孩子结点中的最大结点则发生交换，孩子结点到根的位置，根结点到孩子结点的位置。当所比较的左右孩子为叶节点或者结点所在子树符合堆的性质就结束循环。
堆排序：
堆排序是基于堆的特性进行的排序方法。思想：首先先将数组里的记录调整成大根堆，然后选出记录中的最大者，也就是堆顶记录，将他与数组的最后一个记录（也就是最后一个叶子结点）进行交换，然后再将剩余的堆进行调整，这样以此类推，直到堆中只有一个记录为止。
3、函数源代码：
堆调整：
void Sift(int* a, int k, int last)//堆调整
{
int i, j, temp;
i = k; j = 2 * i + 1;
while (j <= last)
{
if (j < last && a[j] < a[j + 1])j++;//j指向孩子中最大的结点
if (a[i] > a[j])break;//符合堆性质，结点所在子树不用调整
else
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
堆排序：
void Heap(int *a,int length)//堆排序
{
int i, temp;
for (i = ceil(length / 2) - 1; i >= 0; i--)//ceil()取整函数
{
Sift(a, i, length - 1);
}
for (i = 1; i < length; i++)
{
temp = a[0];
a[0] = a[length - i];
a[length - i] = temp;
Sift(a, 0, length - i - 1);
}
}
4、性能：
时间复杂度：O(nlog2n)~O(nlog2n)~O(nlog2n)
空间复杂度：O(1)
稳定性：不稳定
简单性：中级
5、D-OJ练习题：
D-OJ刷题日记：堆排序验证性实验 题目编号:588_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121439422
（7）归并排序：1、思想：
将若干个有序序列逐步归并，最终归并为一个有序序列。这里以最简单的二路归并为例。二路归并就是将待排序列划分成两个长度相同的子序列，分别对两个子序列进行排序，得到两个有序子序列，再将这两个有序子序列进行合并。
递归图解：
非递归图解：
2、如何写代码：
递归：
归并排序的递归算法是一种自顶向下的排序方法。为了确保归并时不破坏原来的有序序列， 那么就需要创建一个新的数组用来存储归并好的记录。也就是说：设相邻的两个子序列为：
Data[first1]~Data[last1]和Data[last1+1]~Data[last2]，合并后为temp[first1]~temp[last2]。为此设三个参数i，j，k分别指向两个子序列的第一个记录，i = first1, j = last1+1。k指向存放合并结果的位置，即 k = first1。
非递归：
归并排序的递归算法是一种自底向上的排序方法。将n个待排序列的记录n个长度为1的子序列，然后进行两两合并，得到（n/2）个长度为2的子序列，再进行两两归并，得到（n/4）个长度为4的有序子序列……直到得到一个长度为n的序列时，归并结束。
3、函数源代码：
递归：
void Merge(int *a,int length,int first1, int last1, int last2)//归并1
{
int* temp = new int[length];
int i = first1, j = last1 + 1, k = first1;
while (i <= last1 && j <= last2)
{
if (a[i] <= a[j])temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= last1)
temp[k++] = a[i++];
while (j <= last2)
temp[k++] = a[j++];
for (i = first1; i <= last2; i++)
a[i] = temp[i];
delete[]temp;
}
void Merge1(int *a,int length,int first,int last)//递归
{
if (first == last) return;//自顶向下只有一个记录时，排序结束
else
{
int mid = (first + last) / 2;
Merge1(a,length,first, mid);//归并排序前半个
Merge1(a,length,mid + 1, last);//归并排序后半个
Merge(a, length, first, mid, last);//合并成一个
}
}
非递归：
void mergePass(int *a,int h,int len)//归并2
{
int i = 0;
while (i + 2 * h <= len)
{
Merge(a, len, i, i + h - 1, i + 2 * h - 1);
i = i + 2 * h;
}
if(i+h
void Merge2(int* a, int length)//归并非递归
{
int h = 1;
while (h < length)
{
mergePass(a, h, length);;//实现一趟归并
h = 2 * h;
}
}
4、性能：
时间复杂度：O(nlog2n)~O(nlog2n)~O(nlog2n)
空间复杂度：O(n)
稳定性：稳定
简单性：初级
5、D-OJ练习题：
D-OJ刷题日记：归并排序验证性实验 题目编号:590_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121439396
（8）计数排序：
1、思想：
是一种线性时间的排序算法。
2、如何写代码：
计数排序的工作原理是使用一个额外的数组 ，其中第 个元素是待排序数组 中值等于 的元素的个数，然后根据数组 来将 中的元素排到正确的位置。
它的工作过程分为三个步骤：
1）、计算出每个数出现了几次。
2）、求出每个数出现的次数和前缀和。
3）、利用出现次数的前缀和，从右至左计算每个数的排名。
3、函数源代码：
// C++ Version
const int N = 100010;
const int W = 100010;
int n, w, a[N], cnt[W], b[N];
void counting_sort() {
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) ++cnt[a[i]];
for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}
4、性能：
时间复杂度：O(n+m)//m表示待排数据的值域大小
空间复杂度：O(n)
稳定性：稳定
简单性：高级
5、D-OJ练习题：略
（9）基数排序：
1、思想：
基数排序是一种非比较型的排序算法，最早用于解决卡片排序的问题。
它的工作原理是将待排序的元素拆分为 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 关键字进行稳定排序，再对第 关键字进行稳定排序，再对第 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。
基数排序需要借助一种 稳定算法 完成内层对关键字的排序。
通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。
基数排序的正确性可以参考 《算法导论（第三版）》第 8.3-3 题的解法 或自行理解。
2、如何写代码：
略。
3、函数源代码：
const int N = 100010;
const int W = 100010;
const int K = 100;
int n, w[K], k, cnt[W];
struct Element {
int key[K];
bool operator<(const Element& y) const {
// 两个元素的比较流程
for (int i = 1; i <= k; ++i) {
if (key[i] == y.key[i]) continue;
return key[i] < y.key[i];
}
return false;
}
} a[N], b[N];
void counting_sort(int p) {
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) ++cnt[a[i].key[p]];
for (int i = 1; i <= w[p]; ++i) cnt[i] += cnt[i - 1];
// 为保证排序的稳定性，此处循环i应从n到1
// 即当两元素关键字的值相同时，原先排在后面的元素在排序后仍应排在后面
for (int i = n; i >= 1; --i) b[cnt[a[i].key[p]]--] = a[i];
memcpy(a, b, sizeof(a));
}
void radix_sort() {
for (int i = k; i >= 1; --i) {
// 借助计数排序完成对关键字的排序
counting_sort(i);
}
}
4、性能：
时间复杂度：O(nklogn）
空间复杂度：O(k+n)
稳定性：稳定
简单性：高级
5、D-OJ练习题：略
（10）桶排序：
1、思想：
桶排序是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。
2、如何写代码：
桶排序按下列步骤进行：
1）设置一个定量的数组当作空桶；
2）遍历序列，并将元素一个个放到对应的桶中；
3）对每个不是空的桶进行排序；
4）从不是空的桶里把元素再放回原来的序列中。
3、函数源代码：
// C++ Version
const int N = 100010;
int n, w, a[N];
vector bucket[N];
void insertion_sort(vector& A) {
for (int i = 1; i < A.size(); ++i) {
int key = A[i];
int j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
}
void bucket_sort() {
int bucket_size = w / n + 1;
for (int i = 0; i < n; ++i) {
bucket[i].clear();
}
for (int i = 1; i <= n; ++i) {
bucket[a[i] / bucket_size].push_back(a[i]);
}
int p = 0;
for (int i = 0; i < n; ++i) {
insertion_sort(bucket[i]);
for (int j = 0; j < bucket[i].size(); ++j) {
a[++p] = bucket[i][j];
}
}
}
4、性能：
时间复杂度：O(n)~O(n*n)
空间复杂度：
稳定性：稳定
简单性：高级
5、D-OJ练习题：略
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）