1.排序的概念排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。
2.常见的排序算法 3.插入排序3.1直接插入排序基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
我们来看一下动图：
如何用代码实现这个排序呢，我们观察动图可以看到假如0-end有序那么end+1挨个与0-end的值比较，如果比end+1大就像右移动一位然后继续下一个数比较，如果比end+1小则就插入到end的前面，以此内推
代码如下：
代码语言：javascript代码运行次数：0运行复制// 插入排序
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 TestInsertSor()
{
int a[] = { 2,4,1,7,8,3,9,2 };
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}直接插入排序的特性总结：1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)，什么情况最坏：逆序，最好：顺序有序：O(N)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
3.1 希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达gap=1时，所有记录在统一组内排好序。
希尔排序分为两个步骤：
1. 预排序（让数组接近有序）
2. 插入排序
什么是预排序，预排序就是把数据分为gap个组，gap是几就是几组，假如gap为3那就是分3组，间隔为3的就是一组数据，然后分别对每组数据进行预排序。如下图
我们以红色这组为例来对这组数据进行预排序。
代码如下：
我们的希尔排序用到了插入排序的思想
这里的结束条件为什么不是n-1而是n-gap呢，因为当我们排最后一组数据的时候i的位置位于8而tmp是5，如果结束条件是i 然后我们把每组都进行预排序，可以分开写也可以合并写。 一组一组进行预排序 多组并着走 预排序的目的是让数组接近有序，而不是真正的有序，如果是逆序的情况我们通过预排序就可以很快的把较大的数放到后面，因为我们一次移动gap个数，如果不进行预排序就需要一次一次的移动，使用预排序效率会有提升。 什么是希尔排序呢，希尔排序就是进多组预排序，当gap==1就是插入排序，我们先进行预排序，预排序排好后就已经快接近有序了，最后进行插入排序就可以了。 那么我们的gap应该给多少合适呢？ gap越大，大的可以越快跳到后面，小的数可以越快跳到前面，越不接近有序 gap越小，跳得越慢，但是越接近有序，当gap==1相当于插入排序就有序了 代码如下： 代码语言：javascript代码运行次数：0运行复制//希尔排序 //O(N ^ 1.3) void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { // +1保证最后一个gap一定是1 // gap > 1时是预排序 // 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; } printf("gap:%2d->", gap); PrintArray(a, n); } }这里gap每次缩小三倍是比较高效的+1是为了防止gap==0的情况没法进行最后一次的插入排序。 下面是一些对于gap=gap/3+1的解释说明： 《数据结构-用面相对象方法与C++描述》--- 殷人昆 希尔排序的特性总结：1. 希尔排序是对直接插入排序的优化。 2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--- 严蔚敏 4. 稳定性：不稳定 我们可以简单的分析一下它大概的时间复杂度 gap组数据，假设忽略掉+1(方便计算)，每组数据个数 = n/gap，gap = n / 3 1.gap = n/3，每组3个数据，最坏情况下，第一趟预排序的消耗:(1+2)*n/3，即n（每组比较次数*组数） 2.gap = n / 9，每组9个数据，最坏情况下，第二趟预排序的消耗：(1+2+3+...+8)*n/9，即4*n ... 3.最后一趟(已经很接近有序了)，gap==1，就是直接插入排序消耗:n 大概的消耗如图所示，我们可以记住希尔排序的时间复杂度大概是O(N^1.3)左右 4.选择排序4.1选择排序优化版每一次从待排序的数据元素中选出最小和最大的元素，将最小的与开头元素进行交换，最大的与最后面的元素进行交换，两边指针分别进行减减和加加，直到两个指针相等。 代码语言：javascript代码运行次数：0运行复制//选择排序 void SelectSort(int* a, int n) { int begin = 0,end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } Swap(&a[begin], &a[mini]); if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); ++begin; --end; } }选择排序的特性总结：1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：不稳定 4.2堆排序堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 代码语言：javascript代码运行次数：0运行复制//向下调整 void AdjustDown(HPDataType* a, int n, int parent) { //先假设左孩子 int child = parent * 2 + 1; while (child < n)//child >= n说明孩子不存在，调整到叶子了 { //找出小的那个孩子 if (child + 1 < n && a[child + 1] < a[child])//这里child+1是判断是否有右孩子 { ++child; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //向上调整 void AdjustUp(HPDataType* a, int child) { //初始条件 //中间过程 //结束条件 int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void TestHeap2() { int a[] = { 4,2,8,1,5,6,9,7 }; HeapSort(a, sizeof(a) / sizeof(int)); } void HeapSort(int* a, int n) { //降序 建小堆 //升序 建大堆 for (int i = 1; i < n; i++) { AdjustUp(a, i); } //O(N*logN) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } 直接选择排序的特性总结：1. 堆排序使用堆来选数，效率就高了很多。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(1) 4. 稳定性：不稳定 更多详情点击：【数据结构】堆的实现和堆排序--TOP-K问题-CSDN博客 5.交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 5.1冒泡排序冒泡排序的思想：两两相邻的元素进行比较，如果不满足顺序就交换，满足顺序就找下一对。 代码语言：javascript代码运行次数：0运行复制void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //冒泡排序 void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { int flag = 0; for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); flag = 1; } } if (flag == 0) { break; } } }冒泡排序的特性总结：1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：稳定 5.2快速排序（hoare版本）快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 我们先来看看快排的动图 整体的思想就是左边的数据做key，然后让right先走遇到比key小的就停下来，然后left走当left遇到比key大的值就停下来然后与right的值进行交换，当left和right相遇的时候就让key的值和left交换，在把key赋值成相遇 位置的值，这是单趟排序，然后以key为中心分成两个区间，进行不递归的递归直到最后的区间只有一个值，或许不存在区间，递归开始返回。 代码如下： 代码语言：javascript代码运行次数：0运行复制//hoar版本 int PartSort1(int* a, int left, int right) { int keyi = left; int begin = left, end = right; while (begin < end) { //右边找小 while (begin < end && a[end] >= a[keyi]) { --end; } //左边找大 while (begin < end && a[begin] <= a[keyi]) { ++begin; } Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); return begin; //快排 void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort1(a, left, right); // [left, keyi-1] keyi [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi +1, right); }如果我们想让快排的效率高就要考虑一些极端的情况，比如在有序的情况下右边一直没找到比key小的值他们直接在key的位置相遇了，这样不就变成一个等差数列了大大降低快排的效率，如果让key作为一个中间值那么效率才快，所以我们可以定义一个三数取中函数，函数的返回值作为key。 三数取中的代码很简单，就是比较最左边的和最右边的还有中间值，谁是第二大就返回谁 三数取中代码如下： 代码语言：javascript代码运行次数：0运行复制//三数取中 int GeMidi(int* a, int left, int right) { int midi = (left + right) / 2; //left midi right if (a[left] < a[midi]) { if (a[midi] < a[right]) { return midi; } else if (a[left] < a[right]) { return right; } else { return left; } } else //a[left] > a[midi] { if (a[midi] > a[right]) { return midi; } else if (a[left] < a[right]) { return left; } else { return right; } } }效率测试： 有了三数取中效率明显有提升，但还是有人觉得不够快，确实，随着不断的递归递归层次越深效率会越来越慢，所以为了加快效率，我们可以进行小区间优化。 小区间优化代码如下： 代码语言：javascript代码运行次数：0运行复制void QuickSort(int* a, int left, int right) { if (left >= right) { return; } if ((right - left + 1) < 10) { InsertSort(a + left, right - left + 1); } else { //三数取中 int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int begin = left, end = right; while (begin < end) { while (begin < end && a[end] >= a[keyi]) { end--; } while (begin < end && a[begin] <= a[keyi]) { begin++; } Swap(&a[begin], &a[end]); } Swap(&a[begin], &a[keyi]); keyi = begin; QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }如上图分析可知最后一次递归消耗次数最多，所以我们可以对最后几个区间进行小区间优化，我们用快速排序来代替，根据上图有区间优化和无小区间优化有明显的提升。 那么可能会有人问这么一个问题为什么要选左边为key，并且选左边为key时要让右边先走，为什么相遇位置比key小。如下图 5.3 快速排序（前后指针版本）快排还有一个版本叫前后指针版本，我们先来看一下动图 我们可以看到分别定义了两个指针分别为prev和cur，这两个指针一前一后，cur前prev后，cur找小，找到小的就++prev，然后与cur位置的值进行交换，没找到就++继续找，直到cur的越界。 画图分析： 代码如下： 代码语言：javascript代码运行次数：0运行复制//前后指针版本 int PartSort2(int* a, int left, int right) { //三数取中 int midi = GeMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[prev], &a[keyi]); return prev; }5.4快速排序（挖坑法版本）我们还有一个版本叫做挖坑法，这个版本没有效率的提升，但是可以 不用分析左边做key，右边先走的思想，也不用分析为什么相遇位置比key小的问题，因为它的相遇是坑。 我们看一下动图 此时left作为坑，右边找到小的之后与left交换然后left进行找大，而right的位置作为坑，直到相遇,因为相遇位置是坑我们直接把key的值填进去，我们可以定义一个临时变量作为坑 代码如下： 代码语言：javascript代码运行次数：0运行复制//挖坑法 int PartSort3(int* a, int left, int right) { int begin = left, end = right; int midi = GeMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = a[left]; int hole = left; //坑的位置 while (begin < end) { while (begin < end && a[end] >= keyi) { end--; } a[hole] = a[end]; hole = end; while (begin < end && a[begin] <= keyi) { begin++; } a[hole] = a[begin]; hole = begin; } a[hole] = keyi; return hole; }5.4快速排序（非递归版本）前三个版本都使用了递归，若不用递归我们可以使用栈来实现，代码整体不变只需要要把递归部分改了，让key左右两个区间全部入栈，先入右边在入左边这样我们就可以先取到左边的，直到栈为空。 画图看一下 循环每走一次相当于一次递归 代码语言：javascript代码运行次数：0运行复制//hoar版本 int PartSort1(int* a, int left, int right) { //三数取中 int midi = GeMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int begin = left, end = right; while (begin < end) { //右边找小 while (begin < end && a[end] >= a[keyi]) { --end; } //左边找大 while (begin < end && a[begin] <= a[keyi]) { ++begin; } Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); return begin; } void QuickSortNonR(int* a,int left,int right) { ST st; STInit(&st); STPush(&st, right); STPush(&st, left); while (!(STEmpty(&st))) { int begin = STTop(&st); STPop(&st); int end = STTop(&st); STPop(&st); int keyi = PartSort1(a, begin, end); if (keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); } if (begin < keyi - 1) { STPush(&st, keyi-1); STPush(&st, begin); } } STDestroy(&st); }快速排序的特性总结：1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(logN) 4. 稳定性：不稳定 6.归并排序6.1归并排序（递归法）基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤： 来看一下动图 画图分析： 归并排序通过递归的方式将待排序的数组分解成更小的子数组，直到每个子数组只包含一个元素。然后，它将这些有序的子数组合并成越来越大的有序数组，直到最终得到一个完整的有序数组。这个过程中，分解是递归进行的，而合并则是通过迭代的方式完成的，每次合并两个有序的子数组来形成一个更大的有序数组。 代码如下： 代码语言：javascript代码运行次数：0运行复制void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin >= end) return; int mid = (begin + end) / 2; //如果[begin,midi] [mid+1,end]有序就可以进行归并了 _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); //归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } //判断是否还有值没进tmp数组 while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); //左闭右闭要+1 } //归并 void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp = NULL; }6.2归并排序（非递归）快排我们通过用栈来实现了非递归，那么我们归并的非递归怎么实现呢，我们可以按组来归并。 首先我们先分gap组，gap为每组的个数，比如gap为1那么每组就归一个数据，一个数据和一个数据归归并成2个有序数据，如果gap为2那么一组就是两个数据，2个数据和2个数据归最后归并成4个有序数据，直到gap等于数据个数就结束。 代码如下： 代码语言：javascript代码运行次数：0运行复制//归并（非递归） void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } //gap每组归并数据的数据个数 int gap = 1; while (gap < n) { for (int i = 0; i < n; i +=2* gap) { //[begin1,end1][begin2,end2] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //第二组都要越界不存在，这一组不需要归并 if (begin2 >= n) break; //第二组的begin没越界，end越界了，需要修正一下，继续归并 if (end2 >= n) end2 = n - 1; int j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a+i, tmp+i, sizeof(int) * (end2 - i + 1)); } gap *= 2; } free(tmp); tmp = NULL; }这里有人可能要问为什么要i+=2* gap因为每组区间归并完后要进行下一段的区间归并，比如下标为0的和下标为1的进行11归那么他们归并完之后下一段区间开始归并也就是下标为2的要和下标为3的归并，每次要跳过2个组。 i为每组的起始位置，我们11归完后22归22归完后44归直到gap > n，但是这种方法有可能存在越界的风险 我们在对上面这组数据进行排序的时候就存在了越界的风险，除了begin1不会越界其他都越界了。处理方法如下： 对于end1和begin2的越界处理方式非常简单就是不需要归并了，如果end2越界了我们只需要修正一下它的区间。代码如下： 代码语言：javascript代码运行次数：0运行复制//第二组都要越界不存在，这一组不需要归并 if (begin2 >= n) break; //第二组的begin没越界，end越界了，需要修正一下，继续归并 if (end2 >= n) end2 = n - 1;归并排序的特性总结：1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(N) 4. 稳定性：稳定 7.计数排序思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤： 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 画图分析： 代码如下： 代码语言：javascript代码运行次数：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; int* count = (int*)calloc(range, sizeof(int)*range); if (count == NULL) { perror("malloc fail"); return; } //统计个数 for (int i = 0; i < n;i++) { count[a[i] - min]++; } //排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } free(count); }我们开了一个count数组用来记录原数组中元素出现的个数，那么这个数组开多大空间呢我们按范围开，找出最大值和最小值然后相减就是个数了，我们称他为相对映射 计数排序的特性总结：1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限，只适合整数，适合范围集中。 2. 时间复杂度：O(n+range) 3. 空间复杂度：O(range) 4. 稳定性：稳定 8.基数排序和桶排序这两个排序在面试中几乎不会考我们只需要了解即可。 8.1基数排序基数排序的思想： 基数排序是一种非比较型整数排序算法，其排序过程不需要进行元素间的比较。它的核心思想是将待排序的元素按照位数从低到高（或从高到低）进行排序，类似于对字符串的逐字符排序。具体来说，基数排序可以分解为多个稳定的计数排序过程，每个过程针对一个位数进行排序。 确定最大位数：首先，找到待排序元素中的最大值，从而确定最大位数。逐位排序：从最低有效位（个位）开始，依次对所有元素进行一次稳定的计数排序，直到最高有效位（最高位）完成排序。在每一次排序中，都是根据当前位数的值，将元素分配到不同的桶（或称为子数组）中，然后按照桶的顺序合并元素，得到新的有序序列。重复过程：重复上述过程，直到所有位数都排序完成。基数排序的优点在于它的高效性和稳定性，尤其适用于整数的排序。然而，基数排序需要额外的存储空间来存储桶和计数数组，这可能会增加空间复杂度。 8.2桶排序桶排序的思想： 桶排序是一种将元素分到有限数量的桶中的排序算法。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序地合并起来。 确定桶的数量：首先，需要确定桶的数量。桶的数量可以根据待排序元素的范围和分布来确定，通常选择比元素数量稍大一些的桶数量，以保证每个桶中的元素数量相对较少。分配元素到桶中：根据一定的规则（如元素的范围、元素的某种属性等），将待排序的元素分配到相应的桶中。桶内排序：对每个桶中的元素进行排序。这里可以使用任何适合的排序算法，如插入排序、快速排序等。由于桶内的元素数量相对较少，因此这一步的排序通常比较高效。合并桶中的数据：最后，按照桶的顺序（通常是从第一个桶到最后一个桶）将桶中的数据合并起来，得到有序的结果。桶排序的优点在于它对于一定范围内的数据排序非常高效，尤其是当数据分布相对均匀时。然而，桶排序的性能也依赖于桶的数量和桶内排序算法的选择。如果桶的数量选择不当或桶内排序算法效率不高，桶排序的性能可能会受到影响。 9.总结排序算法复杂度及稳定性分析