文章目录
- 直接插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 快速排序hoare版本
- 快速排序递归挖坑版本
- 快速排序递归前后指针法
- 归并排序
- 计数排序
在介绍排序算法之前，先在其他小伙伴里找到一张排序算法时间复杂度，空间复杂度以及稳定性的总结图片(桶排序和基数排序先没更新)，而排序算法中的稳定性是指，在排序过程后，这一组数据之间的相对位置不能发生改变，就比如说：1 2 5 2 5 3，排完序后不能把原本后面的5排到前面那个5的前面去。
- 插入类排序
-
直接插入排序
时间复杂度: O(n2)
空间复杂度: O(1)
稳定性: 稳定
直接插入排序是把待排的数字，从后向前，依次插入一段有序的序列中，直至序列全部有序。至于为什么从后向前比较，是因为可以在比较的途中，直接把大数字向后挪移，就减少了遍历的时间，这种情况没有什么比用打牌来说明更好的了。
排序算法的多个版本直接插入排序希尔排序选择排序堆排序冒泡排序快速排序快速排序hoare版本快速排序递归挖坑版本快速排序递归前后指针法归并排序计数排序
// 插入排序
void InsertSort(int* a, int n)
{
int i = 0;
//i表示当前需要插入的数字的下标
for (i = 1; i < n; i++)
{
int end = i - 1;//需要比较的数字的下标
int tmp = a[i];//需要插入的数字
while (end >= 0)
{
//如果前面的数比较大，把大数向后挪
if (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
//找到第一个小于或等于后面数的位置就退出循环
break;
}
end--;
}
a[end + 1] = tmp;
}
}
-
希尔排序
时间复杂度：O(n logn) ~O(n2)
空间复杂度: O(1)
稳定性: 不稳定
希尔排序又称为缩小增量排序，先选定一个距离，然后把所有间隔为该距离的数想成一组，对改组数据进行排序，重复该操作，直至距离为1，整个序列有序了。
// 希尔排序
void ShellSort(int* a, int n)
{
//预排序 间距为gap 的插入排序
int gap = n;
//gap != 1 -->预排序阶段
//gap == 1 --> 排序阶段
while (gap != 1)
{
gap = gap / 3 + 1; //定义每次排序的间距
int j = 0;
for (j = 0; j < n - gap; j++)
{
int end = j ;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = tmp;
}
}
}
- 选择类排序
-
选择排序
时间复杂度:O(n2)
空间复杂度：O(1)
稳定性: 不稳定
选择排序有两种写法，一种是只从一边出发，每次找到当前无序数组中最大或者最小的，然后放在最后；另一种是从两边出发，每次找到当前数组最大和最小的数字，然后放在两边。(这里需要小心，如果说最大数在最左边，那么先交换最小数，可能会出现最大数不在记录的位置)
eg： 8 1 3 5 2 4
第一遍找完，发现min = 1,max = 0(该数字的下标)
然后先把min 放到 0号下标的位置，就变成了
1 8 3 5 2 4
紧接着再把max 放到 5 号末尾，按照下标交换的结果就是
4 8 3 5 2 1
就跟我们预期的结果不同，这种情况需要单独处理。
// 选择排序
void SelectSort(int* a, int n)
{
int i = 0;
int j = 0;
for (j = 0; j < n / 2; j++)
{
int min = j, max = j;
for (i = j; i < n - j; i++)
{
if (a[i] > a[max])
{
max = i;
}
else if (a[i] < a[min])
{
min = i;
}
}
Swap(a, j, min);
//处理冲突的情况
if (j == max)
{
max = min;
}
Swap(a, n - j - 1, max);
}
}
-
堆排序
时间复杂度：O(n log(n))
空间复杂度：O(1)
稳定性: 不稳定
在进行堆排序时，首先得知道堆这个概念
堆分为两种，一种是大根堆，一种是小根堆。根节点最大的堆叫做最大根堆或大根堆，根节点最小的堆叫做最小根堆或小根堆。
堆的特征: 堆中每个节点的值总是不大于或不小于其父亲节点的值；堆总是一颗完全二叉树。既然是完全二叉树，那么堆可以用数组来存储。
而在堆排序中，想要按照升序来排列，需要建大堆；按照降序排列需要建小堆。
如果是升序排列，根节点的值永远为当前堆的最大值，我们每次就可以交换当前无序数组两端的数字，然后再向下建堆(此时无序数组长度 -1)，这样就可以每次把最大值放到有序的位置。
应用：平常玩王者荣耀的时候，旁边总会有一个全区前100，排位前多少名的序列，这个时候，表中只需要前100名，总不可能每次更新排名的时候，都把所有玩家排个序，然后取前100名玩家。
这个时候就可以通过建立一个100个数据的小根堆，此时根节点为当前的最小值，然后只要后面的数据比根节点大，就交换根节点和改数据的值，再向下建堆，增加了效率。(广告加的一点也不生硬)
// 堆排序
//向下建立大根堆
//a 是堆的数组 n 是无序数组的长度 root 需要建堆的根节点
void AdjustDwon(int* a, int n, int root)
{
int parent = root;//父亲节点
int child = root * 2 + 1;//左孩子节点（因为数组的起始位置是 0 ，所以需要 +1）
while (child < n)
{
//先选择出父亲节点的左右孩子节点比较大的一个节点
if (child < (n - 1) && a[child] < a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
//如果父亲节点值小于孩子节点，交换两值
Swap(a, parent, child);
parent = child;
child = parent * 2 + 1;
}
else
{
//如果父亲节点大于孩子节点，就不需要再判断了，大根堆的每一个根节点都是一个大根堆。
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
int i = 0;
//先建立一个大根堆，向下调整法
for (i = n / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
//排序
for (i = n - 1; i > 0; i--)
{
Swap(a, 0, i);
AdjustDwon(a, i, 0);
}
}
- 交换类排序
-
冒泡排序
时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：稳定
冒泡排序作为我们平常使用最多的排序，代码简洁，不容易出错，还能解决很多不是大数据的问题，这里就不做解释了代码不香吗
void Bubbing(int* a,int len)
{
int i=0;
int j=0;
for(i=1;i<len;i++)
{
int flag = 1;
for(j=0;j<len-i;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
flag = 0;
}
}
//如果没发生交换，说明所有序列都是有序的，不需要再继续下去了
if(flag)
{
break;
}
}
}
-
快速排序
时间复杂度：O(n log(n)) ~ O(n2)
空间复杂度：O(log(n)) (递归调用函数，开辟栈帧消耗空间)
稳定性：不稳定
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的三总形式：hoare版本，挖坑法，前后指针版本
快速排序的优化：三数取中，随机数法(排序速度选择权交给上帝)
快速排序在排序中，如果当前序列本身就是有序的，那么快速排序的时间复杂度就到最坏的情况，即O(n2)，想要让快速排序排的越快，就跟我们的选值有关，如果我们让选的值最后都在当前序列的中间位置，就可以让他的速度相对来说快一点(三数取中)。
三数取中，随机数法
void choose(int* a,int left,int right)
{
//随机数法
//int key = left + rand()%(right - left);
//三数取中
int key = (left + right) / 2;
if (a[left] < a[key])
{
if (a[key] < a[right])
{
Swap(a, left, key);
}
else
{
if (a[left] < a[right])
{
Swap(a, left, right);
}
}
}
else
{
if (a[key] > a[right])
{
Swap(a, left, key);
}
else
{
if (a[left] > a[right])
{
Swap(a, left, right);
}
}
}
}
递归版本
快速排序hoare版本
如果第一个数选的是最左边的数，那么就先从右边开始找第一个比他小的，再从左边找第一个比他大的，然后交换这两个数的位置，持续这样做，直到两指针相遇，再交换最左边和相遇点的数据。
// 快速排序hoare版本
void PartSort1(int* a, int left, int right)
{
//递归结束条件
if (left >= right)
{
return;
}
//快速排序的优化，三数取中，随机数法
choose(a,left,right);
int key = left;
int l = left;
int r = right;
while (left < right)
{
//找到从右向左第一个小于 a[key] 的值
while (left < right && a[right] >= a[key])
{
right--;
}
//找到从左往右第一个大于 a[key] 的值
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(a, left, right);
}
Swap(a, left, key);
PartSort1(a, l, left - 1);
PartSort1(a, left + 1, r);
}
快速排序递归挖坑版本
挖坑法呢，顾明思议，排序前先在选择的位置留下一个坑，只要找到一个不符合的数，就用这个数来填坑，然后这个数原本的位置就变成了一个坑，留到最后给终止位置填坑。
// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
//递归结束条件
if (left >= right)
{
return;
}
choose(a, left, right);
int key = a[left];
int l = left;
int r = right;
while (left < right)
{
//找到从右向左第一个小于 a[key] 的值
while (left < right && a[right] >= key)
{
right--;
}
a[left] = a[right];
//找到从左往右第一个大于 a[key] 的值
while (left < right && a[left] <= key)
{
left++;
}
a[right] = a[left];
}
a[left] = key;//填坑
PartSort1(a, l, left - 1);
PartSort1(a, left + 1, r);
}
快速排序递归前后指针法
这个方法的思路就跟用O(n)的时间复杂度，把一个序列中偶数放在前面，奇数放在后面一样。
// 快速排序前后指针法
void PartSort3(int* a, int left, int right)
{
//递归结束条件
if (left >= right)
{
return;
}
int prev = left - 1;
int cur = left;
int key = a[left];
int i = 0;
while (cur <= right)
{
if (a[cur] < key)
{
Swap(a, ++prev, cur);
}
cur++;
}
PartSort1(a, left, prev - 1);
PartSort1(a, prev + 1, right);
}
非递归版本
首先呢，递归版本其实是利用函数调用开辟的栈帧来保存数据，栈帧的本质还是栈，先进后出，我们就可以利用栈来改成非递归的版本，感觉就像是一个换了名字的深度优先搜索。
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
//入栈方式 先入当前区间的左边，再入右边
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
//弹栈时，先得到的是区间的右边，后得到左边
right = StackTop(&st);
StackPop(&st);
left = StackTop(&st);
StackPop(&st);
//去除只有一个数或者没有数的情况的情况
if (left >= right)
{
continue;
}
int key = left;
int l = left;
int r = right;
while (left < right)
{
//找到从右向左第一个小于 a[key] 的值
while (left < right && a[right] >= a[key])
{
right--;
}
//找到从左往右第一个大于 a[key] 的值
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(a, left, right);
}
Swap(a, left, key);
//先让右边区间入栈
StackPush(&st, left+1);
StackPush(&st, r);
//左边区间入栈
StackPush(&st, l);
StackPush(&st, left - 1);
}
StackDestroy(&st);
}
- 归并类排序
-
归并排序
时间复杂度：O(n log(n))
空间复杂度：O(n)
稳定性：稳定
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
void _MergeSort(int* a, int* tmp, int left, int right)
{
int mid = (left + right) / 2;
/*
[0,7] -> [0,3] [4,7]
递归[0,3] -> 划分[0,1][2,3]
递归[0,1] ->划分[0,0][1,1] -->归并出有序的 [0,1]
递归[2,3] ->划分[2,2][3,3] -->归并出有序的 [2,3]
[0,1][2,3] --> 归并出有序的[0,3]
递归[4,7] -> 划分[4,5][5,7]
递归[4,5] ->划分[4,4][5,5] -->归并出有序的 [4,5]
递归[6,7] ->划分[6,6][7,7] -->归并出有序的 [6,7]
[4,5] [6,7] --> 归并出有序的[4,7]
[0,3] [4,7] --> 归并出有序的[0,7]
*/
if (left >= right)
{
return;
}
//[left,mid] [mid+1,right]
_MergeSort(a, tmp, left, mid);
_MergeSort(a, tmp, mid + 1, right);
//两个有序数组的合并
int begin1 = left, begin2 = mid + 1;
int end1 = mid, end2 = right;
int index = begin1;
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++];
}
//将tmp排序好的数据拷贝到a数组对应位置
memcpy(a + left, tmp + left, sizeof(int)* (right - left + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)* n);
_MergeSort(a, tmp, 0, n - 1);
}
非递归版本
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)//n为数组里元素的数量
{
int* tmp = (int*)malloc(sizeof(int)* n);
int size = 1;
int count = (int)(log(n) / log(2)) + 1;;
for (; size < n;size *= 2)
{
int i = 0;
for (i = 0; i < n; i += size*2)
{
int left = i, mid = i + size,right = mid + size;
//处理最后一组不满足size个大小的情况
if (mid > n)
{
mid = n;
}
if (right > n)
{
right = n;
}
//两个有序数组的合并
//[begin1,end1) [begin2,end2)
int begin1 = left, begin2 = mid;
int end1 = mid, end2 = right;
int index = begin1;
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++];
}
}
// 将tmp排序好的数据拷贝到a数组对应位置
memcpy(a, tmp, sizeof(int)* n);
}
free(tmp);
}
- 非比较类排序
-
计数排序
时间复杂度：O(max(n,范围))
空间复杂度：O(范围)
稳定性：稳定
计数排序需要先找到当前数组的最大值和最小值，然后通过一个辅助空间，把最大值和最小值压缩在一个辅助数组中，如果最大值和最小值之间差距比较大，而且数据还是那种稀疏矩阵类型的，是用计术排序就显得不那么好。
// 计数排序(非比较类)
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
//先找到数组中最大值和最小值
int i = 0;
for (i = 0; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
//数据所在的一个范围
int range = max - min + 1;
int* arr = (int*)calloc(range,sizeof(int));
//统计对应的数据出现的次数
for (i = 0; i < n; i++)
{
int tmp = a[i] - min;
arr[tmp]++;
}
int len = 0;
//根据次数排序，返回原数组
for (i = 0; i < range; i++)
{
while (arr[i])
{
a[len++] = i + min;
arr[i]--;
}
}
free(arr);
}