[数据结构]排序——八大排序
前言
我们在学习数据结构中，我们经常接触到排序这个名词，但我们在学习时，直接面对代码时可能一脸茫然，为什么这个接口要用这些参数，为什么要前后交换…………这些就是我们不知道作者在实现这些接口时他们的思想是怎么样的，这篇博客我将通过对排序的概念、代码的分析、代码的分析、来逐步讲解每一种排序的思考方式与实现过程，真正帮助大家理解排序的实现，让我们面对代码时不再茫然
排序
①排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序： 数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
②排序运用
在生活中我们经常使用到排序，购物时的比价，点外卖时的好评比较，销量高低等
1.手机购买时的排序使用
2.外卖中的排序使用
插入排序
①概念
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
②分析
我们在看概念的时候可能还是不理解是什么意思，这里我们举例生活中的例子：
当我们在打扑克的时候，我们会不断的抓牌，而这个抓牌的过程就是我们的插入排序，首先我们会抓到我们的第一张牌，我们默认我们现在的牌有序；当我们抓到新的牌时，我们就有对之前已经有序的牌中插入这一张新牌，使我们的牌组依然有序，以此往复，直至我们摸牌结束，结束的同时，我们手里的牌也依旧按照从小到大的顺序排序。
③代码分析
通过上面的分析我们知道了代码要实现的结果，首先我们要处理一个数据，这个数据有两个部分组成，一个部分是已经排好序的数组，另一部分是一个要插入我们当前有序排列的元素。而这个过程我们分析可知，其实就是从数组中的第一个元素视为处理数据开始，我们通过我们的插入排序代码实现将其有序，然后再将前两个元素视为处理数据，依次递增，前三个元素，前四个元素…………直至所有元素都是为处理数据。
然后我们逐一对这些处理数据执行我们的排序插入代码，实现我们在插入元素之后，有序排列任然有序，那么我们应该如何实现我们的有序排序呢？
我们先通过下面的图解进行过程分析：
这个时候我们知道了这个过程是如何实现的，那么代码我们应该怎么编写呢？我们这里可以先从一趟开始写起，然后我们在去考虑循环的过程
下面我们先写我们一趟插入排序的代码：
void InsertSort(int*a, int n)
{
int end = ? ;//因为这个时候我们不知道我们的end坐标的位置，所以我们先用?代替，在循环中我们再修改
int tmp = a[end + 1];//这里我们将要插入的元素先进行保存，因为我们后续的代码会将这个位置的元素进行覆盖
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
//a[end+1] = tmp;
break;
}
}
a[end + 1] = tmp;//这里是考虑了多种情况：①当我们要插入的数一直比我们的有序数列的数字都要小的时候，我们将其放到end+1的位置；②正常情况，我们也要将其放到end +1的位置
}
现在我们只要再将end的大小考虑清楚即可实现我们的插入排序代码，现在我们来对end的大小取值进行分析
通过上面的分析，我们就可以得出完整的代码
void InsertSort(int*a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
④代码检验
Sort.h
#include<stdio.h>
#include<stdlib.h>
void InsertSort(int* a, int n);
void PrintArray(int*a, int n);
void InsertTest();
Sort.c
#include"Sort.h"
void InsertSort(int*a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void PrintArray(int*a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void InsertTest()
{
int a[] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
int size = sizeof(a) / sizeof(int);
PrintArray(a, size);
InsertSort(a, size);
PrintArray(a, size);
}
test.c
#include"Sort.h"
int main()
{
InsertTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
⑤插入排序的利弊
现在我们对插入排序的时间复杂度进行分析，我们可以得出插入排序的时间复杂度的大小，取决于我们的处理数据，当我们的处理数据为逆序时，我们的时间复杂度就是O(N^2)；而当我们的处理数据为顺序或者接近顺序时，我们的时间复杂度就是O(N)
注意，我们得出插入排序的利弊是：时间复杂度的大小取决于处理数据的排序程度，那么如果我们处理的数据在开始时即比较接近有序排列，这个时候我们再进行插入排序时我们的时间复杂度就可以大幅下降，那么我们可不可以实现在进行插入排序前先进行一次排序，使处理数据接近有序排列呢？
希尔排序
①概念
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
②分析
我们在第一次读上面概念时吗，可能不理解在讲述什么，我们通过下面的图解先进行简单分析，来讲解希尔排序的操作步骤
通过上面的图解分析，我们知道当我们对处理数据进行一次希尔排序时，我们的处理数据从一开始的无序变为较为有序，这个时候我们想，如果我们再一次进行希尔排序，会不会让处理数据较上一次更加有序呢？ 但这个时候我们发现， 如果我们的gap的数值不发生改变的话，那么我们再一次进行希尔排序后，数据不会发生改变，所以我们需要改变我们的gap的数值大小， 那么这个时候我们和我们的插入排序联想，我们可以思考出，如果我们的gap值较大，那么我们数据移动的单位距离也就越大，那么我们的处理数据的有序性就越低，相反，如果想我们的插入排序，每一次的元素移动距离为一个单位距离，这个时候我们得出的就是有序排列
③代码分析
通过上面的分析，我们得知我们希尔排序的方式为多次进行移动单位距离为gap的插入排序，并且我们的gap在每执行一次希尔排序之后，我们的gap都会减小，多次之后我们的处理数据就从无序变为有序排列
这个时候我们知道了这个过程是如何实现的，那么代码我们应该怎么编写呢？我们这里可以先从一趟开始写起，然后我们在去考虑循环过程中使我们的gap逐次减小的问题
void ShellSort(int* a, int n)
{
int gap = 3;//这里我们假设我们的gap为3
for (int i = 0; i < n - gap; i++)
{
int end = i ;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
对代码语句分析
现在我们得出了一趟执行的代码，其实就是我们的插入排序，只不过我们每一次移动的距离不再是单位距离，而是大小为gap的距离，那么这个时候我们就应该考虑，我们的gap的大小应该为多少？
这里关于希尔排序中gap的大小，官方给出的建议是每一次将gap的数据 / 3，因为这样处理数据时效率更高 而我们知道如果 我们在执行希尔排序时如果不将我们的希尔排序中gap减为1的话，也就是最终不执行插入排序的话，我们的处理数据永远不可能变为有序排列，永远只是无限接近有序排列，但不是有序排列
在进过这些分析之后我们可以得出我们的代码
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//这里可以保证我们最后一次gap的数值为1，使我们最后一次执行插入排序
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void ShellSort(int* a, int n);
void ShellTest();
sort.c
#include"Sort.h"
void PrintArray(int*a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void ShellTest()
{
int a[] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
int size = sizeof(a) / sizeof(int);
PrintArray(a, size);
ShellSort(a, size);
PrintArray(a, size);
}
test.c
#include"Sort.h"
int main()
{
ShellTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
查找排序（选择排序）
①概念
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
②分析
查找排序和前两个排序比较起来简单许多，这里我们对上面讲述的过程进行一个简单的讲述，这里我们先对上面讲述的概念进行一个分析：
上面概念中讲解的是每一次挑选出当前处理数据中的最大值或最小值，然后我们通过交换，遍历处理数据，最终实现排序排列，那么我们可以对这一过程进行一下升级，我们每一次找到当前处理数据中的最大值和最小值，然后我们将其分别与最后一个元素和第一个元素交换，然后缩小我们的查找范围，再重复上述的步骤，最终实现我们的有序排列，这样我们的效率可以更高一些
③代码分析
现在我们来对我们代码的实现进行分析
按照我们上述的内容，我们需要创建两个标志，分别记录我们处理数据的头元素和尾元素，这里我们用begin和end标记；然后我们每对数组遍历一次之后，我们就将我们在这一趟中寻找到的最大值和尾元素交换，最小值和头元素交换，之后我们要减小我们下一次的查找范围，那么我们的就要执行：begin++；end–；然后重复我们上述的步骤，最终实现将处理数据变为有序排列
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin <= end)
{
int mini = begin;
int maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;//记录我们最小值的下标
}
if (a[i] > a[maxi])
{
maxi = i;//记录我们最大值的下标
}
}
Swap(&a[mini], &a[begin]);
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void SelectSort(int* a, int n);
void SelectTest();
sort.c
#include"Sort.h"
void PrintArray(int*a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin <= end)
{
int mini = begin;
int maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[begin]);
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}
void SelectTest()
{
int a[] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
int size = sizeof(a) / sizeof(int);
PrintArray(a, size);
SelectSort(a, size);
PrintArray(a, size);
}
test.c
#include"Sort.h"
int main()
{
SelectTest();
return 0;
}
当我们执行代码后，编译执行的结果为
现在的执行结果显示我们的分析思路与代码编写是正确的;
可真的正确吗？
现在我们换一组处理数据进行检验
int a[] = { 154, 38, 96, 23, 15, 72, 60, 45, 83 };
当我们执行代码后，编译执行的结果为
这里我们发现，我们的执行结果并没有实现我们想要的有序排列，这个时候我们画图分析发现：
那么我们需要对代码进行修改，那么我们对下标进行判断即可：
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin <= end)
{
int mini = begin;
int maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[begin]);
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}
这样我们就可以避免交换失败的情况
堆排序
关于堆排序的内容我们在前面的博客中讲解过
博客地址：https://blog.csdn.net/weixin_52664715/article/details/120463777?spm=1001.2014.3001.5501
在这里我们再进行一次简单的讲解：
①概念
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
②分析
当我们进行堆排序时，我们的处理数据是一个随机数组，那么我们现在需要先将这个数组处理为大堆（这里我们讲解的有序排列默认为升序）
那么我们如何实现将一个随机数组处理为大堆呢？这里我们先找到我们的最后一个子树，也就是我们数组中最后一个元素所在的子树，我们对这个子树进行堆的向下调整，使这个子树变为大堆，然后将这个子树的父节点视为我们的遍历标志，将这个父节点逐次进行减一操作，直至我们的父节点超出我们的数组范围（父节点 < 0）；
堆的向下调整的实现，这里我们简单讲述：我们先默认参数中根节点的左节点为两个子树中较大的元素，然后我们判断右子树节点是否存在，如果存在同时判断是右子树节点大还是左子树节点大，如果同时符合条件，我们将child标记到右子树；这个时候我们在判断父节点与孩子节点的大小，当我们的孩子节点比我们的父节点大时，我们将孩子节点与父节点进行交换，同时改变孩子节点和父节点的下标；然后重复上述步骤，直至我们向下调整时，孩子节点越过我们的数组范围，此时我们向下调整结束，随机数组在逻辑结构中为大堆；
经历过上面的操作之后，我们的无序数组在逻辑结构中就是一个大堆，那么现在我们需要将这个大堆变为有序排列（升序），这个时候我们将这个堆的顶点，也就是我们的根节点与我们数组中最后一个节点进行交换（堆中的最后一个叶节点进行交换），这个时候我们的数据，除去交换后的元素，我们剩下的数据就是我们在讲解堆的向下调整中的特殊情况，根节点的左右子树都是大堆，那么这个时候我们对这个处理数据进行堆的向下排序，使我们的数组又变为大堆，这个时候我们将数组的长度减一，再重复上面的操作，这样当我们的循环结束时我们就实现了将处理数据随即数组变为升序排列；
③代码分析
我们图解说明各种接口实现的情况：
1.堆的向下调整：
2.堆的建立
3.堆的排序：
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustDown(int* a, int n, int parent)//a是我们的数组；n是我们数组的元素个数；parent是我们根节点的坐标
{
int child = parent * 2 + 1;
while (child < n)
{
//if (a[child + 1] < n && a[child + 1] > a[child])//判断我们的树中是否含有右子树；因为我们先前默认左子树为左右子树中大的树；
if (child + 1< n && a[child + 1] > a[child])//判断我们的树中是否含有右子树；因为我们先前默认左子树为左右子树中大的树；
{
child++;//这个时候我们确定了右子树的存在，同时我们将左右子树中的较大树真实确定为右子树
}
if (a[child] > a[parent])//这个时候如果我们的孩子大于我们的父节点，那么我们进行交换
{
Swap(&a[child], &a[parent]);//当我们交换结束之后，那么当前的树正常，称为大堆中的一个树，当他的左右子树被破坏，这个时候我们需要对其左右子树重复上述内容，重新建立堆
parent = child;
child = parent * 2 + 1;
}
else
{
break;//当我们孩子比我们的父节点小时，说我们的堆没有问题
}
}
}
//现在我们要编程堆排序的代码，我们进行分析：
void HeapSort(int* a, int n)//这里的n是我们的数组个数
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//这个时候我们将一个随机数组先建立成一个大堆；
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void HeapSort(int* a, int n);
void AdjustDown(int* a, int n, int parent);
void HeapTest();
sort.c
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustDown(int* a, int n, int parent)//a是我们的数组；n是我们数组的元素个数；parent是我们根节点的坐标
{
int child = parent * 2 + 1;
while (child < n)
{
//if (a[child + 1] < n && a[child + 1] > a[child])//判断我们的树中是否含有右子树；因为我们先前默认左子树为左右子树中大的树；
if (child + 1< n && a[child + 1] > a[child])//判断我们的树中是否含有右子树；因为我们先前默认左子树为左右子树中大的树；
{
child++;//这个时候我们确定了右子树的存在，同时我们将左右子树中的较大树真实确定为右子树
}
if (a[child] > a[parent])//这个时候如果我们的孩子大于我们的父节点，那么我们进行交换
{
Swap(&a[child], &a[parent]);//当我们交换结束之后，那么当前的树正常，称为大堆中的一个树，当他的左右子树被破坏，这个时候我们需要对其左右子树重复上述内容，重新建立堆
parent = child;
child = parent * 2 + 1;
}
else
{
break;//当我们孩子比我们的父节点小时，说我们的堆没有问题
}
}
}
//现在我们要编程堆排序的代码，我们进行分析：
void HeapSort(int* a, int n)//这里的n是我们的数组个数
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//这个时候我们将一个随机数组先建立成一个大堆；
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
void HeapTest()
{
int a[] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
int size = sizeof(a) / sizeof(int);
PrintArray(a, size);
HeapSort(a, size);//这里的n是我们的数值个数
PrintArray(a, size);
}
test.c
#include"Sort.h"
int main()
{
HeapTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
冒泡排序
关于冒泡排序的内容我们在学习C语言初期进行进行了学习与讲解，这里我们就不在赘述
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j--)//在这一种循环中我们控制我们交换后最大值存放的位置
{
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
}
}
}
}
我们对冒泡排序进行一个简单的优化
void BubbleSort(int* a, int n)//对冒泡排序的优化：
{
for (int j = 0; j < n; j++)
{
int exchange = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}
快速排序
①概念
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
②分析
若是我们直接看快速排序的定义可能不便于理解，这里我对上面内容先进行一个简单的讲述，我们在进行快速排序时，我们先将一个数定义为我们要进行排序的元素，当我们进行一次快速排序之后，这个元素会移动到它在这个数组从随机数组变为有序数组后的正确位置，同时，当达到正确位置之后，元素的左边的元素都比它要小，元素右边的元素都比它要大。
现在我们通过图解来对一趟快速排序的执行过程进行分析：
③代码分析
现在我们知道了快速排序的执行过程，那么我们现在对代码的执行进行分析：
我们现在知道我们需要先确定我们每一趟中的key值，那么我们就需要将其定义在程序中，其次我们创建两个指针，分别指向我们数组的首元素和尾元素，然后我们开始收缩我们的数组范围
当我们的确定的key元素是我们的首元素时，我们从右指针开始移动，然后开始判断当前元素与key元素的大小关系，当指针指向的元素大于我们的key元素时，指针前移，缩小我们的数组范围，当指针指向的元素小于我们的key元素时，指针停止移动；我们开始移动我们的左指针，当指针指向的元素小于我们的key元素时，指针后移，缩小我们的数组范围，当指针指向的元素大于我们的key元素时，指针停止移动；此时我们交换我们两个指针指向的元素
交换之后，我们继续重复上述的内容，直至左指针和右指针相遇，当我们的两个指针相遇时，我们将我们的key标记的元素与此时相遇的元素进行交换，此时key元素就到达了正确的排序位置
void PartSort(int* a, int left, int right)//现在我们编写的是一趟排序的执行方式
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//此时我们和left交换还是right交换已经没有区别，因为现在两个指针指向的元素相同
}
现在我们实现了一趟中实现将key元素移动的其排序之后的正确位置，那么接下来我们应该怎么去移动剩下的元素呢？
这个时候我们在看一下我们②中的分析，有一条内容是：
当我们执行一趟快速排序之后，key元素左边的元素的小于key元素，右边的数都大于key元素
这个时候我们可能会联想到我们在处理二叉树时的思想——分而治之，这里也是相同的，我们在第一趟中实现了将key元素移动到其排序之后的正确位置，而此时key元素的左右两边又组成数组，且这些元素在执行快速排序之后的位置分别在key元素左边元素组成的数组中、右边元素组成的数组中，不会出现移动之后其元素移动时出现数组越界的问题。 这样我们只需在每执行一次快速排序之后，将数组进行划分，通过递归就可以实现将整个随机数组变为有序数组，达到排序的目的。
int PartSort(int* a, int left, int right)//现在我们编写的是一趟排序的执行方式
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//此时我们和left交换还是right交换已经没有区别，因为现在两个指针指向的元素相同
return left;//此时下标为left或者right的位置中存放的是我们一开始的keyi下标的值，现在我们返回我们交换之后keyi的坐标，也就是keyi
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void QuickSortTest();
void QuickSort(int* a, int left, int right);
int PartSort(int* a, int left, int right);
sort.c
#include"Sort.h"
int PartSort(int* a, int left, int right)//现在我们编写的是一趟排序的执行方式
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//此时我们和left交换还是right交换已经没有区别，因为现在两个指针指向的元素相同
return left;//此时下标为left或者right的位置中存放的是我们一开始的keyi下标的值，现在我们返回我们交换之后keyi的坐标，也就是keyi
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
void QuickSortTest()
{
int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
PrintArray(a, sizeof(a) / sizeof(int));
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
test.c
#include"Sort.h"
int main()
{
QuickSortTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
⑤代码的改进1
现在我们实现了快速排序的执行，可我们思考一种特殊情况，如果我们要处理的数组已经是有序排序，那么我们在执行快速排序的时候每一次都变成了插入排序，这样的话时间复杂度太高，那么我们有没有什么办法可以改进一下我们的快速排序去避免这种情况呢？
这里我们采用 "三数取中法"
我们的三数取中法就是为了避免我们要处理数据是有序数组，这个方法的实现方法是，我们比较当前趟中的left、right、mid所标记的元素，然后我们选择这三个元素中中间大小的元素与key标记的元素进行交换，，这样当我们的处理数据是有序数组时就可以避免我们的快速排序变为插入排序
现在我们知道了我们方法的执行方式，现在让我们来实现代码
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else if (a[right] > a[left])
{
return right;
}
}
else//(a[left] > a[mid])
{
if (a[right] > a[left])
{
return left;
}
else if (a[right] > a[mid])
{
return right;
}
else if (a[mid] > a[right])
{
return mid;
}
}
}
通过上面的代码，我们可以比较出三个数中中间大小的数，同时返回它的下标，这个时候我们再对快速排序的代码稍加修改即可
int PartSort(int* a, int left, int right)//现在我们编写的是一趟排序的执行方式
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);//将数据进行交换，下标任然不变
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//此时我们和left交换还是right交换已经没有区别，因为现在两个指针指向的元素相同
return left;//此时下标为left或者right的位置中存放的是我们一开始的keyi下标的值，现在我们返回我们交换之后keyi的坐标，也就是keyi
}
⑥代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void QuickSortTest();
void QuickSort(int* a, int left, int right);
int PartSort(int* a, int left, int right);
int GetMidIndex(int* a, int left, int right);
sort.c
#include"Sort.h"
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
//为了避免排序数组已经有序，我们进行三数取中算法修改：
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else if (a[right] > a[left])
{
return right;
}
}
else//(a[left] > a[mid])
{
if (a[right] > a[left])
{
return left;
}
else if (a[right] > a[mid])
{
return right;
}
else if (a[mid] > a[right])
{
return mid;
}
}
}
int PartSort(int* a, int left, int right)//现在我们编写的是一趟排序的执行方式
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);//将数据进行交换，下标任然不变
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//此时我们和left交换还是right交换已经没有区别，因为现在两个指针指向的元素相同
return left;//此时下标为left或者right的位置中存放的是我们一开始的keyi下标的值，现在我们返回我们交换之后keyi的坐标，也就是keyi
}
void QuickSortTest()
{
int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
PrintArray(a, sizeof(a) / sizeof(int));
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
test.c
#include"Sort.h"
int main()
{
QuickSortTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
⑦代码的改进2
现在我们对快速排序的实现提供另一种方法，挖坑法
现在我们通过图解对这种方法进行讲解
我们和上面相同，先实现单趟排序的代码
int PartSort(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)//右边找小，填到左边的坑中
{
right--;
}
a[hole] = a[right];//找到后，交换内容，同时变更坑的下标
hole = right;
while (left < right && a[left] <= key)//左边找大，填到右边的坑中
{
left++;
}
a[hole] = a[left];
hole = left;
}
//这个时候我们找到了key值的最终位置，然后赋值
a[hole] = key;
return hole;
}
⑧代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void QuickSortTest();
void QuickSort(int* a, int left, int right);
int PartSort(int* a, int left, int right);
sort.c
int PartSort(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)//右边找小，填到左边的坑中
{
right--;
}
a[hole] = a[right];//找到后，交换内容，同时变更坑的下标
hole = right;
while (left < right && a[left] <= key)//左边找大，填到右边的坑中
{
left++;
}
a[hole] = a[left];
hole = left;
}
//这个时候我们找到了key值的最终位置，然后赋值
a[hole] = key;
return hole;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
void QuickSortTest()
{
int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
PrintArray(a, sizeof(a) / sizeof(int));
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
test.c
#include"Sort.h"
int main()
{
QuickSortTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
⑨代码的改进3
我们学习了上面两种方法之后，我们再讲解另一种快速排序的执行方式， 双指针方法
这里我们通过图解，直接说明这一种方法如何执行与实现快速排序
现在我们知道了这种方法的实现过程，那么我们和上面的过程相同，先将单趟排序的代码进行实现
int PartSort(int* a, int left, int right)
{
int keyi = left;
int prv = left;
int cur = prv + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
Swap(&a[++prv], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prv]);
return prv;
}
此时如果我们画图进行分析可知，上述代码在实现过程中，又是会进行自己与自己交换的情况，这样可能会让效率有所下降，所以我们可以对上述代码进行优化
int PartSort(int* a, int left, int right)//这里我们对两个标志多一步判断，当两个下标指向的位置相同时，我们不进行交换，这样就避免了自己和自己交换的情况
{
int keyi = left;
int prv = left;
int cur = prv + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prv != cur)
{
Swap(&a[prv], &a[cur]);
}
cur++;
}
Swap(&a[prv], &a[keyi]);
return prv;
}
在这里我更推荐使用第一种方法去实现我们快速排序中单趟代码，因为更容易理解，第三种方法在理解方面可能会有所困难
⑩代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void QuickSortTest();
void QuickSort(int* a, int left, int right);
int PartSort(int* a, int left, int right);
sort.c
int PartSort(int* a, int left, int right)
{
int keyi = left;
int prv = left;
int cur = prv + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
Swap(&a[++prv], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prv]);
return prv;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
void QuickSortTest()
{
int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
PrintArray(a, sizeof(a) / sizeof(int));
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
test.c
#include"Sort.h"
int main()
{
QuickSortTest();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
合并排序
①概念
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
②分析
我们在看了合并排序的概念之后，再结合之前二叉树的学习，其实我们对合并排序的实现是有一些熟悉的感觉，这里我们通过图解进行分析
我们将处理数组进行分割，然后按照分而治之的思想，继续分割，当我们分割的子数组中只含有一个元素时，我们认为当前数组有序，然后我们开始合并，按照升序进行排序，使得合并后的数组依然有序，就这样，我们通过递归实现将数组进行分割，然后我们再通过递归实现将子数组进行合并，并使合并后的子数组任保持升序，这样当我们递归结束时，我们的数组就从无序数组变为有序数组
③代码分析
void _MergeSort(int* a, int left, int right, int* tmp)//接口的参数：原数组、区间的左边界、区间的右边界、临时数组（用来存储原数组的内容）
{
if (left >= right)//这个时候说明范围内只有一个数据，那么我们默认其有序
return;
int mid = (right + left) / 2;
//[left,mid][mid+1,right];
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;//临时数组中的位置标记
while (begin1 <= end1 && begin2 <= end2)//分割数组中任然有元素
{
if (a[begin1] < a[begin2])//两个分割数组中的元素比较，取小存入
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//当一侧结束，全部存完时，另一个分割数组中仍然含有元素，将其移动到临时数组中
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//归并后，我们将数据拷贝到原数组中
for (int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)//我们原本是想通过递归来实现合并，但如果我们每一次都自己调用递归的话，都需要malloc，并且我们每一次处理的范围都在变化
//这样我们就在当前接口中再写一个接口，去实现递归
{
int* tmp = (int*)malloc(sizeof(int)* n);//创建一个数组，其大小与我们要进行排序的数组大小相等
_MergeSort(a, 0, n - 1, tmp);//我们通过内部接口递归实现排序，如使用本接口，每一次都要malloc，栈帧的开销太大
free(tmp);
}
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void MergeSort(int* a, int n);
void _MergeSort(int* a, int left, int right, int* tmp);
void TestMergeSort();
sort.c
void _MergeSort(int* a, int left, int right, int* tmp)//接口的参数：原数组、区间的左边界、区间的右边界、临时数组（用来存储原数组的内容）
{
if (left >= right)//这个时候说明范围内只有一个数据，那么我们默认其有序
return;
int mid = (right + left) / 2;
//[left,mid][mid+1,right];
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;//临时数组中的位置标记
while (begin1 <= end1 && begin2 <= end2)//分割数组中任然有元素
{
if (a[begin1] < a[begin2])//两个分割数组中的元素比较，取小存入
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//当一侧结束，全部存完时，另一个分割数组中仍然含有元素，将其移动到临时数组中
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//归并后，我们将数据拷贝到原数组中
for (int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)//我们原本是想通过递归来实现合并，但如果我们每一次都自己调用递归的话，都需要malloc，并且我们每一次处理的范围都在变化
//这样我们就在当前接口中再写一个接口，去实现递归
{
int* tmp = (int*)malloc(sizeof(int)* n);//创建一个数组，其大小与我们要进行排序的数组大小相等
_MergeSort(a, 0, n - 1, tmp);//我们通过内部接口递归实现排序，如使用本接口，每一次都要malloc，栈帧的开销太大
free(tmp);
}
void TestMergeSort()
{
//int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
int a[] = { 10, 6, 7, 1, 3, 9, 4, 2 };
PrintArray(a, sizeof(a) / sizeof(int));
MergeSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
test.c
#include"Sort.h"
int main()
{
TestMergeSort();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
计数排序
①概念
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
②分析
概念中给出的内容太过简短，没有学过相应知识的我们无从下手，这里我们通过图解进行分析
③代码分析
在这里我们要注意，上述图解中的数组我们给出的范围较小，如果我们的数组给出的元素的较大，且元素之间的跳跃较大，那么我们应该怎么处理呢？我们任通过图解分析和讲解处理办法
通过图解，我们知道当我们采用最基本的方法面对我们当前的数组时，并不适用，会造成空间的浪费，所以我们采用相对映射的办法，减少我们的数组内容的开辟，减少数组空间的浪费
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];//先选出当前数组中的最大值、最小值
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
int range = max - min + 1;//Count数组长度
int* count = (int*)calloc(range, sizeof(int));//创建Count数组
// 统计次数
for (int i = 0; i < n; ++i)
{
count[a[i] - min]++;//这里我们需要进行画图分析，更加便于理解
}
// 根据count数组排序
int i = 0;
for (int j = 0; j < range; ++j)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}
这里我们需要对代中的一条代码进行分析，我们通过图解的方式进行讲解
④代码检验
sort.h
#include<stdio.h>
#include<stdlib.h>
void PrintArray(int* a, int n);
void TestCountSort();
void CountSort(int* a, int n);
sort.c
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];//先选出当前数组中的最大值、最小值
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
int range = max - min + 1;//Count数组长度
int* count = (int*)calloc(range, sizeof(int));//创建Count数组
// 统计次数
for (int i = 0; i < n; ++i)
{
count[a[i] - min]++;//这里我们需要进行画图分析，更加便于理解
}
// 根据count数组排序
int i = 0;
for (int j = 0; j < range; ++j)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}
void TestCountSort()
{
int a[] = { 10, 6, 7, 1, 3, 9, 4, 2, 2, 3, 6, 7, 4, 10 };
PrintArray(a, sizeof(a) / sizeof(int));
CountSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
test.c
#include <time.h>
#include <stdlib.h>
#include "Sort.h"
int main()
{
TestHeapSort();
return 0;
}
当我们执行代码后，编译执行的结果为
这里说明我们的分析思路与代码编写是正确的
总结
以上就是我对排序内容中八大排序的个人理解与讲述，后续我还会对排序中的稳定性、时间复杂度、将排序用非递归实现进行讲解
上述内容如果有错误的地方，还麻烦各位大佬指教【膜拜各位了】【膜拜各位了】
