个人主页：@我要成为c嘎嘎大王
希望这篇小小文章可以让你有所收获！
目录
一、直接插入排序
基本思想：把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中，直到所有的待排序的数据插入完为止，得到一个新的有序序列 。
// 时间复杂度：O(N^2)
// 最坏：逆序
// 最好：顺序有序，O(N)
// 插入排序
void InsertSort(int* a, int n) {
for(int i = 0; i < n - 1;i++){
// [0, n-2]是最后一组
// [0,end]有序;
// end+1位置的值插入[0,end]，保持有序
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;
}
}
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：最坏情况下为O(N ^ 2)，此时待排序列为逆序，或者说接近逆序 最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
- 空间复杂度：O(1）
- 稳定性：稳定
二、希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作。当 gap == 1时，就相当整个序列被分到一组，进行一次直接插入排序，排序完成。
// O(N^1.3)
// 希尔排序
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;// +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;
}
}
}
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了。这样整体而言，可以达到优化的效果。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，所以需要特殊记忆 ：O(N ^ 1.3)
- 稳定性：不稳定
三、冒泡排序
基本思路：当左边大于右边时，进行交换。排序一趟可以确定最大值的位置。
// O(N^2) 最坏
// O(N) 最好
// 冒泡排序
void BubbleSort(int* a, int n) {
for (int i = 0; i < n; i++) {
int flag = 1;
for (int j = 1; j < n - i; j++) {
if (a[j - 1] > a[j]) {
Swap(&a[j - 1], &a[j]);
flag = 0;
}
}
if (flag) {
break;
}
}
}
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
四、堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
代码实现可以看这篇文章：【数据结构】堆的实现
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
五、选择排序
基本思路：每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
// O(N^2)
// 选择排序
void SelectSort(int* a, int n) {
int begin = 0;
int end = n - 1;
while (begin < end) {
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++) {
if (a[i] > a[maxi]) {
maxi = i;
}
if (a[i] < a[mini]) {
mini = i;
}
}
Swap(&a[mini], &a[begin]);
if (maxi == begin) {
maxi = mini;
}
Swap(&a[maxi], &a[end]);
begin++;
end--;
}
}
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
六、 快速排序
6.1 hoare版本 (左右指针法)
基本思路：
- 选出一个key，一般是最左边或是最右边的。
- 定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
- 在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
- 此时key的左边都是小于key的数，key的右边都是大于key的数。
- 将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right) {
// 三数取中
int midi = GetMid(a, left, right);
Swap(&a[left], &a[midi]);
int begin = left;
int end = right;
int keyi = begin;
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
否则有序时时间复杂度为O(N^2)。
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
6.2 挖坑法
基本思路：
挖坑法思路与hoare版本(左右指针法)思路类似
- 选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
- 还是定义一个begin和一个end，begin从左向右走，end从右向左走。（若在最左边挖坑，则需要end先走；若在最右边挖坑，则需要begin先走）
- 后面的思路与hoare版本(左右指针法)思路类似。
// 快速排序挖坑法
int PartSort2(int* a, int left, int right) {
// 三数取中
int midi = GetMid(a, left, right);
Swap(&a[left], &a[midi]);
int begin = left;
int end = right;
int keyi = begin;
while (begin < end) {
while (begin < end && a[end] >= a[keyi]) {
end--;
}
a[begin] = a[end];
while (begin < end && a[begin] <= a[keyi]) {
begin++;
}
a[end] = a[begin];
}
a[begin] = a[keyi];
return begin;
}
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
}
int keyi = PartSort2(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}6.3 前后指针法
思路：
- 选出一个key，一般是最左边或是最右边的。
- 起始时，prev指针指向序列开头，cur指针指向prev+1。
- 若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。
- 经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
- 然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作
// 快速排序前后指针法
int PartSort3(int* a, int left, int right) {
// 三数取中
int midi = GetMid(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (a[cur] <= a[keyi] && ++prev != cur) {
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int left, int right) {
if (left >= right) {
return;
}
int keyi = PartSort3(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}6.4 非递归实现
这里我们结束 栈 这一数据结构模拟快速排序递归的过程。
基本思路：
- 我们先把左右区间对应的下标进行入栈。我们都知道，栈的特点是后进先出LIFO（Last In First Out），这样我们可以先入右区间、再入左区间，这样就达到了递归的效果。（即先排左区间、后排右区间）
- 拿到 keyi 后，我们需要注意不能直接就将keyi的两侧进行入栈，这样会有越界访问的风险。需要进行判断后再入栈。
- 当栈不为空时，说明还有区间没有进行排序。为空时说明所有区间均以排好即已经为有序数组
// 快速排序 非递归实现
void QuickSortNonR(int* a, 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 = PartSort2(a, begin, end);
if (end > keyi + 1) {
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (begin < keyi - 1) {
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}七、 归并排序
7.1 递归实现
思路：
- 不断的分割数据，让数据的每一段都有序（一个数据相当于有序）
- 当所有子序列有序的时候，在把子序列归并，形成更大的子序列，最终整个数组有序。
// 时间复杂度：O(N*logN)
// 空间复杂度：O(N)
// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int left, int right) {
if (left == right) {
return;
}
int midi = (left + right) / 2;
_MergeSort(a, tmp, left, midi);
_MergeSort(a, tmp, midi + 1, right);
int begin1 = left;
int end1 = midi;
int begin2 = midi + 1;
int end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2) {
if (a[begin1] < a[begin2]) {
tmp[i++] = a[begin1++];
}
else {
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1) {
tmp[i++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[i++] = a[begin2++];
}
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc");
exit(1);
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp == NULL;
}7.2 非递归实现
// 归并排序非递归实现
void MergeSortNonR(int* a, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc");
exit(1);
}
int gap = 1;
while (gap < n) {
for (int i = 0; i < n; i += 2 * gap) {
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (begin2 > n - 1) {
break;
}
if (end2 > n - 1) {
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;
}
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
八、计数排序
一种特殊的排序，唯一种没有比较的排序（指没有前后比较，还是有交换的）
体现的是映射思维。
// 计数排序
void CountSort(int* a, int n) {
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc");
exit(1);
}
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 = NULL;
}
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围）
- 稳定性：稳定
九、总结
完
希望这篇小小文章可以为你解答疑惑！
若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！