文章目录
- 一.认识本章要讲的排序算法
-
- 1.直接插入排序
- 2.希尔排序
- 3.选择排序
- 4.冒泡排序
- 5.堆排序
- 6.快速排序
-
- 6.1霍尔Hoare排序
- 6.2挖坑法
- 6.3前后指针法
- 6.4非递归法
- 7.归并排序
-
- 7.1归并排序的非递归法
- 8.计数排序
- 二.每个算法的时间复杂度和稳定性
一.认识本章要讲的排序算法
该文章会讲到比较基础的排序算法，比较重要的排序算法如，快排，堆，需要用到基础的数据结构知识栈，二叉树的堆。
1.直接插入排序
什么叫做直接插入排序，大家应该打过扑克牌（自己一张一张摸牌不是一次性发牌），那么大多数人都是，摸到了一张牌，摸下一张牌的时候我们都是去对这两张牌进行一个排序按自己的喜好，摸到三张同理以此类推完成一个合理的顺序。
这里的直接插入排序很类似，如我们有一串数据：3，5，7，8，9，1.这些乱序的数据，我们的处理方式是，我们和摸牌类似先取第一个数，因为第一个数绝对有序（没有和它能比较的它当然是绝对有序），当我们取完后我们再去取第二个数，对第一个进行比较然后放置到正确的位置上，再取第三个数，对其和前面两个数进行排序，依次类推就是直接插入排序的基本思路。
//插入排序
void InsertSort(int* a, int n)
{
//这里的条件是i<n-1是因为我们的end最多能取到n-2因为当end取到n-1时，我们的end+1越界了！
for (int i = 0; i < n - 1; i++)
{
//目的就是把[0,end]有序变成[0,end+1]有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
//这里使用break的意义是，因为有可能我们的这个tmp比我们所有的值都小，
//如果我们直接在这里更改tmp值的位置，那么我们就访问不到下标为0的值，因为我们的
//end已经--了
break;
}
end--;
}
a[end + 1] = tmp;
}
}
注：这里的end是指新模的牌的下标，tmp是临时存储这里的end的下一个值，因为排序完后可能会发生挪动，覆盖掉原本的end+1位置上的值所以才需要先保存再挪动覆盖
2.希尔排序
希尔排序是我们直接插入排序的一种变形，我们的直接插入是一次性让整个数据有序，但是我们的希尔排序则不然，它是逐渐让这里的数据趋向有序，直至最后一次就是用我们的直接插入排序让其变得有序，我们通过gap去实现这里的过程如我们有一串数据：3，5，7，8，9，1.
我们当gap为三的时候对他们进行分组（最重要的就是这里的分组排序再归一）
我们对这里的gap一般取值为：gap = gap/2 或者是gap = gap/3 +1 然后来保证这里的gap的最终值会在1.
//希尔
void ShellSort(int* a, int n)
{
int gap = n;
int end = 0;
int tmp = a[end + gap];
while (gap > 1)
{
gap = (gap / 3) + 1;
for (int i = 0; i < n - gap; i++)
{
end = i;
tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = tmp;
}
}
}
我这里选择的gap是 gap = (gap / 3) + 1，并且我这里并没有用循环来控制gap，用循环控制的gap是分组进行排序，我这里选用的是第一组排完第一次换到了第二组排第一次以此类推，否则要再套一层循环去控制gap，修改的位置就是我这里控制循环的n-gap因为要防止越界。
3.选择排序
选择排序顾名思义，有一组乱序的数据，我们进行选择，选肯定是挑最大的或者最小的选，我们这里优化一下，我们一次性选两个，一个是最大的，一个是最小的，这里的Swap函数就是一个交换两个值的函数。
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
int maxi = begin, mini = begin;
while (begin < end)
{
maxi = begin, mini = begin;
for (int i = begin; 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--;
}
}
注：这里的begin和end都是控制需要选择的边界，因为每选出一个最大值和最小值，我们的起始位置和结束位置就不需要再动再去比较了我们要去调整我们的起始位置。
4.冒泡排序
冒泡排序属于我们的老朋友了，典型只具备<教学意义>它的原理就是，我们走一趟确定一个值，和我们的选排没多大区别甚至不如选排，但是它有一个比较不错的地方就是在于它是一种极具稳定性的排序，虽然效率低下但是有稳定性。这里的稳定性待会下面会讲到。
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = n - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
这里最基本的写法，有一些地方可以进行优化，大家感兴趣的可以翻阅其他的文章，我们这里对冒泡排序就一笔带过了。
5.堆排序
堆是我们树形结构的一种表现形式，它很重要！堆排序的前提是我们得先有堆才能排序，所以我们的目的分两步，先建堆再排序，这里的建堆也颇有讲究，如果我们要升序那么我们需要建一个大堆，反之小堆，为什么升序要大堆呢？因为如果我们建小堆，1.我们无法直接确定节点处谁是最大值，如果我们选择利用Top拿出堆顶那个最小值放在第一个，那么我们下标为1的元素就是我们的新堆顶，但是大家发现了没有，如果我们按此把下标为1的元素当作了堆顶，那么我们的下标为2的元素将不在和下标为1的元素是兄弟关系改为了父子关系，那么这棵树就是个乱树，子树不在具备大堆或者小堆的特性，我们将无法进行向下调整建堆。
原理就是：取堆顶覆盖数组的末尾，从后往前走
所以首先我们选择了建大堆，取堆顶覆盖在数组的最后一位然后再覆盖倒数第二位
// 堆排序
//向下调整
void AdjustDwon(int* a, int n, int root)//这里的root相当于parent
{
assert(a);
int child = root * 2 + 1;//假设我们的左孩子是较小的那个孩子
while (child < n)
{
//如果我们有右孩子或者右孩子才是小的那个孩子
if (child + 1 < n && a[child] < a[child + 1])
{
child += 1;
}
if (a[root] < a[child])
{
Swap(&a[root], &a[child]);
root = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//排升序建大堆
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
//排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end--, 0);
}
}
如果要想建小堆的话，可以去计算一下时间复杂度就知道了。
6.快速排序
快排采取递归方式的方法有三种
6.1霍尔Hoare排序
首先我们来讲讲霍尔的方法，它的原理是利用第一个位置的值当作Key，然后使用了两个指针，一个right一个left去遍历，首先我们让right去往左走，当right遇到一个小于Key的值的时候它就停止，然后换left往前走，当left找到一个比key大的值的时候他们进行交换，如此反复，他们肯定会在某一个值进行相遇，那么这个值也肯定是小于Key的可以自己尝试想一下，推一下。这样当我们走完这一趟的时候，我们的Key是不是来到了刚刚好的位置，那么我们是不是不需要再动这个Key了，所以我们再将区间分成了[left，key-1] key [key+1，right]，这三个区间，但是我们的Key已经来到了最终位置，那么我们接下来需要遍历的是不是就是这两个区间的值，所以采取了递归的前序遍历，Key就是我们的根，然后Key的左子树一直走，递归完左树再递归右数，每递归一次就能找到一个Key，确定一个数的最终位置，那么这个递归结束回来后，我们的顺序就排好了
这是单次的演示！
这里采取了两个小优化，一个是三数取中一个是小区间优化
我们来分别讲讲
三数取中的原理就是，我们将left和right进行取中间值mid然后这三个数进行比较选择一个中间值，进行交换至最左边然后进行返回，这里的意义是，我们的Key要尽可能不大也不小，这样才能更多的进行把大的值往后倒，小的值往前来，这样进行取中间值的意义就避免了在遇到顺序的时候霍尔的效率不那么有优势
小区间优化的意义就是，我们如果递归一个只有十个数的数组，我们要递归四层树，这里得不偿失，本来数就不多，递归是在大数据的前提下非常有优势，因为再多的数据在树中也不过那么几十层，但是十个数居然占了四层，所以当我们的数字小于十的时候我们会选择直接插入排序，进行一次优化
//三数取中
int Getmidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[midi] > a[left])
{
if (a[midi] < a[right])
{
return midi;
}
else //midi是三数中最大的
{
if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}
else
{
if (a[midi] > a[right])
{
return midi;
}
else //说明midi是最小的
{
if (a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
}
}
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
int midi = Getmidi(a, left, right);
Swap(&a[midi], &a[left]);
int key = left;
while (left < right)
{
while (a[right] >= a[key] && left < right)
{
right--;
}
while (a[left] <= a[key] && left < right)
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[left]);
return left;
}
// 快速排序递归实现
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left > 10)
{
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
else
{
InsertSort(a + left, right - left + 1);
}
}
6.2挖坑法
挖坑法和霍尔法原理差距不大，但是也可以说是一种小的优化，它的原理就是先将Key的这个下标，标记为一个坑，然后还是right先走，如果遇到一个比Key小的值，那么就和Key的值交换然后right的这个位置 形成一个新的坑，然后才开始left继续走
这个图片可能得点开看
这是单次的演示
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int midi = Getmidi(a, left, right);
Swap(&a[midi], &a[left]);
int hole = left;
int key = a[left];
while (left < right)
{
while (a[right] >= key && left < right)
{
--right;
}
a[hole] = a[right];
hole = right;
while (a[left] <= key && left < right)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return left;
}
6.3前后指针法
前后指针法用的就是，一个指针prev一个指针cur，用cur去遍历数据，当cur找到一个比Key的值要大的时候我们的prev不在跟随cur++，只有cur自己++，当cur遇到一个比Key的值要小的值的时候我们对prev进行先++在把它的值和cur的值进行交换。
这是单次的演示，这三种方法全部都是利用的Key去确定了一个数的准确位置，然后在进行递归拆分把每一个新Key确定其位置。
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int midi = Getmidi(a, left, right);
Swap(&a[midi], &a[left]);
int key = left;
int cur = left + 1;
int prev = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[key], &a[prev]);
return prev;
}
6.4非递归法
这里的非递归法就比较有意思了，他需要用到一个数据结构，栈。我们刚刚递归使用的都是系统栈，这里的栈是我们自己写出来的人工栈。他的原理仍然是拆分，找Key，把除了Key以外的值放入栈，每一次进栈相较于上一次肯定是多了一组，因为还是拆分成[left,key-1] key [key+1, right]我们的key就不需要再进入栈了因为它的位置已经是确认好的了，那么其他的组再慢慢入栈，这里仍然也很像递归，也像二叉树的前序遍历，先遍历其左子树，出栈出完了再遍历右子树。
注：先入栈的肯定是右子树，因为栈的特点是先入的后出，我们排升序的话就优先排的是左子树，遍历好了后才去出右树。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define DefaultCapacity 4
typedef int STdatatype;
typedef struct Stack
{
STdatatype* a;
int top;
int capacity;
}ST;
//栈的初始化
void STInit(ST* ps);
//栈的销毁
void Destory(ST* ps);
//栈的插入
void STPush(ST* ps, STdatatype x);
//栈的删除
void STPop(ST* ps);
//栈的大小
int STSize(ST* ps);
//栈顶元素的显现
STdatatype STTop(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//栈的销毁
void Destory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//栈的插入
void STPush(ST* ps, STdatatype x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? DefaultCapacity : (ps->capacity) * 2;
STdatatype* tmp = ps->a;
tmp = (STdatatype*)realloc(ps->a, sizeof(STdatatype) * NewCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = NewCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
//栈的删除元素
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}
//栈的尺寸
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//栈顶元素的显现
STdatatype STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
//判断栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
ST sort;
STInit(&sort);
STPush(&sort, right);
STPush(&sort, left);
while (!STEmpty(&sort))
{
left = STTop(&sort);
STPop(&sort);
right = STTop(&sort);
STPop(&sort);
int key = PartSort1(a, left, right);
//[left,key-1] key [key+1,right]
if (key + 1 < right)
{
STPush(&sort, right);
STPush(&sort, key + 1);
}
if (left < key - 1)
{
STPush(&sort, key - 1);
STPush(&sort, left);
}
}
Destory(&sort);
}
这里的代码，包括了栈的基本实现
7.归并排序
归并排序有那么一丢丢的像快排的思路，但是也有较大的差距吧在实现的方式上，首先我们的原理也是拆分，如：[3，5，7，1，2，6]这么一组数据我们会把他拆成一个一个的数，因为一个数肯定是有序的，然后我们在进行两个两个数的比较如这里就是 3 5比 7 1比 2 6 比然后就形成了3 5 1 7 2 6 然后我们用了一个临时的数组去帮助他们进行比较然后排序这里第一次比完后会进行第二次比较 那么结果就是 1 3 5 7 2 6因为2 6还没开始比，注意这里的结果每一次进行完都在临时数组tmp中然后又tmp去对原数组进行覆盖，然后再进行排序，这里由于拆分成了不同的区间，所以仍然用到了几个指针去分别指向了不同区间的开头就是begin1 和begin2 end1 和end2 还有一个指针指向了临时数组的开头用于对未排序的数组进行排序
记住每一个操作都是存入到了tmp数组中
// 进行归并排序
void _MergeSort(int* a, int* tmp, int left, int right)
{
if (right <= left)
return;
//取中间的值
int mid = (left + right) / 2;
//[left,mid][mid+1,right]
_MergeSort(a, tmp, left, mid);
_MergeSort(a, tmp, mid + 1, right);
//上述操作是为了找到最小的有序区间也就是拆分至单个数的时候
//归并
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++];
}
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
7.1归并排序的非递归法
这里的非递归方式，其实也是进行先拆分再归并，这里用的是一一归并，二二归并，四四归并然后用一个变量gap去操作这里的循环次数和区间个数
这是一个大致的逻辑，我们会发现gap的变化由1->2->4我们区间的个数也由1->2->4的变化，所以这里的gap控制的就是区间的个数，但是有可能我们的这里的右区间可能会没有那么多数，比如说我们12个数进行到了8 8 归那么是不是就有可能存在越界的风险，所以这里我们要注意的一共有两点，1.控制这里的begin和end的位置因为都是多区间比较所以begin和end的位置尤其重要，2.我们需要控制这里的end2也就是对末尾位置进行修正如果它的值end2大于了right那么就能确定直接使用end2会导致越界，那么我们就把end2的值修改为right这样来保证end2的合法性。
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc failed");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int index = i;
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//归并
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++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
8.计数排序
计数排序的原理就是我会开辟一个很原数组中的最大值一样大的空间，但是这样很浪费空间，所以我们优化成了，开辟至最大值减最小值的那么多个空间，我们利用下标去存储原数组中的数值出现的次数记住这里存储的是次数而不是值，这里的下标就能转化为原数组的值，所以我们这里会用到一个临时的空间去记录这里的次数然后，直接可以进行排序，这里的排序速度是非常之快的，它不需要交换之类的，但是他的不足也很明显他的空间复杂度很高。
这里的转换通过是的±min这个min就是最小值，我们通过-min来确保数组中的最小值能在合理的位置，并且不需要从0开始开辟空间开辟那么大，开辟的空间的下标其实是原数组中的0+min所以后面我们覆盖回去的时候利用的就是tmp数组+min回归到原来的值
// 计数排序
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* tmp = (int*)malloc(sizeof(int) * range);
memset(tmp, 0, sizeof(int) * range);
//统计原数组中的数据个数
for (int i = 0; i < n; i++)
{
tmp[a[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (tmp[i]--)
a[j++] = i + min;
}
}
二.每个算法的时间复杂度和稳定性
这里的稳定性就指的是，相同数据再交换完顺序后他们的相对位置是否发生改变
这里时间复杂的为NlongN的多半都是采用了树形结构或者类似思路的方式，导致他们是以几何倍数增长的排序方法，其中选择排序是不稳定的如1 3 3 1我们的最大值max是第一个3min是第一个1那么换完就会发现两个三的相对位置发生了改变，那么稳定性肯定是不稳定得了
这里快速排序的时间复杂度是由它是不是有序的情况来算，但是我们如果已经加入了三数取中和小区间优化的话基本是不会出现这里的最差情况所以它仍然可以按照NlongN来看
整体代码再这里：我的gitee