目录
① hoare版本
② 挖坑法
④ 非递归版本
概念：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的操作。
常见排序算法
接下来我会逐一介绍
插入排序
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：
把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。
直接插入排序
当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移
接下来用代码实现
// 直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}直接插入排序的特性
① 元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
② 时间复杂度：O(N^2)
③ 空间复杂度：O(1)
希尔排序
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。
它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。
接下来用代码实现
// 希尔排序
void ShellSort(int* arr, 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 = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}希尔排序的特性
① 希尔排序是对直接插⼊排序的优化。
② 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。
关于希尔排序的时间复杂度是一个很复杂的计算，因为 gap 的取值很多，导致很难去计算，所以它是不固定的，另外估算希尔排序的时间复杂度为O(N^1.3)，这是一个大概的值，大家记住就好了，感兴趣的话可以搜一下它的推导过程。
选择排序
选择排序的基本思想：
每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
直接选择排序
① 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素
② 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换
③ 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步骤，直到集合剩余 1 个元素
接下来用代码实现
//直接选择排序
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int min = begin, max = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] > arr[max])
{
max = i;
}
if (arr[i] < arr[min])
{
min = i;
}
}
//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
if (max == begin)
{
max = min;
}
Swap(&arr[begin], &arr[min]);
Swap(&arr[end], &arr[max]);
begin++;
end--;
}
}代码中我定义了一个max和min，意味着我是从两边向中间进行排序，如果单单只定义一个min往后寻找，时间复杂度会变得比较差，还有代码中我为什么要加if(max == begin)这个判断条件，是因为（大家动手尝试画一下图思路会清晰很多）
直接选择排序的特性
① 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使⽤
② 时间复杂度： O(N^2 )
③ 空间复杂度： O(1)
堆排序
堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。
接下来用代码实现
//堆排序
void Adjustdown(int* arr, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (child + 1 < size && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Heapsortdown(int* arr, int size)
{
for (int i = (size - 1 - 1) / 2; i >= 0; --i)
{
Adjustdown(arr, size, i);
}
int end = size - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
Adjustdown(arr, end, 0);
--end;
}
}这里我就不过多叙述了，如果代码看的不太懂可以看我前面的二叉树文章，里面我详细介绍了向上调整算法和向下调整算法以及堆排序的内容，忘记的话也可以去回顾一下
交换排序
交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置
交换排序的特点是：
将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动
冒泡排序
冒泡排序是⼀种最基础的交换排序。之所以叫做冒泡排序，因为每⼀个元素都可以像⼩⽓泡⼀样，根据⾃⾝⼤⼩⼀点⼀点向数组的⼀侧移动。虽然冒泡排序比较容易实现，但众所周知冒泡排序的时间复杂度很差。
接下来用代码实现
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
}
}
}
}冒泡排序的特性
① 时间复杂度： O(N^2 )
② 空间复杂度： O(1)
快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
//[left,right]--->找基准值mid
int meet = _QuickSort(a, left, right);
//左子序列：[left,mid-1]
QuickSort(a, left, meet - 1);
//右子序列：[mid+1,right]
QuickSort(a, meet + 1, right);
}下面有四种方法可以实现找基准值，接下来我一一介绍
hoare版本
算法思想 ：
① 创建左右指针，确定基准值
② 从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环
// 1.hoare版本
int _QuickSort(int* arr, int left, int right)
{
int begin = left;
int end = right;
int keyi = left;
++left;
while (left <= right)
{
// 右边找⼩
while (left <= right && arr[right] > arr[keyi])
{
--right;
}
// 左边找大
while (left <= right && arr[left] < arr[keyi])
{
++left;
}
if (left <= right)
{
swap(&arr[left++], &arr[right--]);
}
}
swap(&arr[keyi], &arr[right]);
return right;
}疑问：为什么跳出循环后right位置的值⼀定不⼤于key？那是因为当 left > right 时，即right⾛到left的左侧，⽽left扫描过的数据均不⼤于key，因此right此时指向的数据⼀定不⼤于key
挖坑法
算法思想：
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
// 2.挖坑法
int _QuickSort(int* arr, int left, int right)
{
int mid = arr[left];
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] >= key)
{
--right;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= key)
{
++left;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}lomuto前后指针
算法思想：
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。
// 3.lomuto前后指针
int _QuickSort(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int key = left;
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
swap(&arr[cur], &arr[prev]);
}
++cur;
}
swap(&arr[key], &arr[prev]);
return prev;
}快速排序的特性
① 时间复杂度： O(nlogn)
② 空间复杂度： O(logn)
非递归版本
非递归版本的快速排序需要借助数据结构：栈
void QuickSortNonR(int* arr, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
// 单趟
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
++cur;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}归并排序
归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。
归并排序核⼼步骤
接下来用代码实现
// 归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (right + left) / 2;
//[left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
//合并两个有序数组为⼀个数组
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}归并排序的特性
① 时间复杂度： O(nlogn)
② 空间复杂度： O(n)
计数排序
计数排序是一个非比较排序
计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 其算法思想：
① 统计相同元素出现次数
② 根据统计的结果将序列回收到原来的序列中
接下来用代码实现
// 计数排序
void CountSort(int* arr, int n)
{
int min = arr[0], max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!");
exit(1);
}
memset(count, 0, sizeof(int) * range);
// 统计次数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
// 排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
}计数排序的特性
① 计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限。
② 时间复杂度： O(N + range)
③ 空间复杂度： O(range)
④ 稳定性：稳定
排序比较
通过在vs上随机生成十万个数让这八个排序算法进行排序，看看最终每个排序消耗的时间是多少
我们通过结果就可以明显感觉到这几种排序算法的差距
排序算法复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
| 排序⽅法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 直接插⼊排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
文章到这里就结束啦，初阶数据结构的内容我已经介绍完啦，真心希望这些知识能够对大家有所帮助！后面我将开始介绍C++的内容啦，又是一个新的阶段，希望大家多多来支持一下！下篇文章见！
感谢大家三连支持！
敬请期待下篇文章！