目录
一、排序的概念
排序
：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性
：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]
，且
r[i]
在
r[j]
之前，而在排序后的序列中，
r[i]
仍在
r[j]
之前，则称这种排序算法是稳定的；否则称为不稳定的。
例如：
内部排序
：数据元素全部放在内存中的排序。
外部排序
：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
二、常见的排序
三、常见排序算法的实现
1.插入排序
1.1 基本思想：
实际中我们玩扑克牌时，就用了插入排序的思想
1.2直接插入排序动态图
1.3直接插入排序的代码实现
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++){//外围循环的次数
//单个元素的插入
int end=i-1;
int key=a[i];
while (end >= 0 && key < a[end])
{
a[end + 1] = a[end];
end--;
}
a[end+1] = key;
}
}
时间复杂度：
O(N^2)
空间复杂度：
O(1)
稳定性：稳定
应用场景：序列接近有序或者元素个数比较少
2.希尔排序
2.1基本思想：
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然 后取，重复上述分组和排序的工作。当到达gap
=1
时，所有记录在统一组内排好序
。
2.2希尔排序过程
2.3希尔排序代码实现
// 希尔排序
//gap选取的原则size/3+1
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 0)
{
gap = gap / 3 + 1;
for (int i = gap; i < n; i++)
{
int end = i - gap;
int key = a[i];
while (end >= 0 && key < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = key;
}
if (gap == 1)
{
return;
}
}
}
2.4gap的选取
gap的取值是有多种方法的，不同的gap取值不同则会有不同的时间复杂度。我们这里gap的选取原则是
gap = gap / 3 + 1
时间复杂度：
空间复杂度：O(1)
稳定性：不稳定
应用场景：数据比较随机，数据量比较大。（分组之后减少了数据量）
3.选择排序
3.1基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的 起始位 置，直到全部待排序的数据元素排完 。
3.2直接选择排序动态图
上图每次找到序列中最小数的一个位置，将位置标记起来，将一次遍历完成之后将最小值的 位置和区间最前面的一个值交换。（每次找到一个最小值）
3.3直接选择排序的代码实现
// 选择排序
static void Swap(int *left, int *right)
{
int temp = *left;
*left = *right;
*right = temp;
}
void SelectSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++){//外围选择的次数
int Max = 0;
int right = n - i - 1;
for (int j = 0; j < n-i-1; j++)//每一次的选择排序【用Max来标志最大位置的值】
{
if (a[j]>a[Max])
{
Max = j;
}
}
Swap(&a[Max], &a[right]);
}
}1.
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2.
时间复杂度：
O(N^2)
3.
空间复杂度：
O(1)
4.
稳定性：不稳定
3.4选择排序的优化
区间
（这里的区间是随着外围的遍历而改变的）的最右侧，最小值放在区间的最左侧。
2.代码的实现
void SelectSortop(int* a, int n)//优化后的选择排序
{
int left = 0;
int right = n - 1;
while (left < right)
{
int Min = left;
int Max = left;
for (int j = left; j <= right; j++)//一次找处区间[left,right]中的最大值和最小值
{
if (a[j]>a[Max])
{
Max = j;
}
else if (a[j] < a[Min])
{
Min = j;
}
}
if (left != Min)
{
Swap(&a[left], &a[Min]);
}
//最小值交换之后可能影响了最大值的位置
//需要对最大值的位置进行更新
if (Max==left)
{
Max=Min;
}
if (Max != right)
{
Swap(&a[right], &a[Max]);
}
left++;
right--;
}
}
时间复杂度：
O(N^2)【虽然时间复杂度没有变，但是效率却提升了一倍】
空间复杂度：O(1)
稳定性：不稳定
4.堆排序
4.1基本思想：
堆排序(Heapsort)
是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆，排降序建小堆。
4.2堆排序的过程图
4.3堆排序代码实现：
// 堆排序
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
//用child标记两个孩子中较小的一个
if (child + 1 < n&&a[child] > a[child + 1])
{
child++;
}
//判断双亲和孩子的大小
//如果双亲大于孩子，则交换双亲和孩子
if (a[parent]>a[child])
{
Swap(&a[parent], &a[child]);
}
//双亲和孩子进行更新
parent = child;
child = parent * 2 + 1;
}
}
//堆的创建
void HeapCReat(Heap*hp,int *a,int n)
{
hp->a = (int*)malloc(sizeof(int)*n);
hp->capacity = n;
hp->size = 0;
//将数据放入
for (int i = 0; i < n; i++)
{
hp->a[i] = a[i];
}
hp->size = n;
//从后往前开始的非叶子节点用向下调整
for (int root = (hp->size - 2) / 2; root >= 0; root--)
{
AdjustDwon(hp->a, hp->size, root);
}
}
//获取堆顶元素
int HeapTop(Heap *hp)
{
return hp->a[0];
}
//堆删除
void HeapPop(Heap *hp)
{
assert(hp);
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDwon(hp->a,hp->size,0);
}
//判断堆是否为空
int HeapEmpty(Heap *hp)
{
return 0 == hp->size;
}
//堆销毁
void HeapDestory(Heap *hp)
{
assert(hp);
if (HeapEmpty(hp))
{
free(hp->a);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
}
void HeapSort(int* a, int n)
{
Heap hp;
HeapCReat(&hp,a,n);
for (int i = 0; i < n; i++)
{
a[i] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestory(&hp);
}
注意：排升序的时候是建小堆，排降序的时候是建大堆
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
5.冒泡排序
5.1基本思想：
5.2冒泡排序动态图
5.3冒泡排序的代码实现
static void Swap(int *left, int *right)
{
int temp = *left;
*left = *right;
*right = temp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//总共冒几轮
{
for (int j = 0; j < n - i-1; j++)//每一轮冒的次数
{
if (a[j]>a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}冒泡排序是一种非常容易理解的排序
时间复杂度：
O(N^2)
空间复杂度：
O(1)
稳定性：稳定
6.快速排序
6.1基本思想：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
6.2划分方法与代码实现
快速排序中最重要的就是按照基准值将区间分为左右两部分这一关键步骤，有三种不同的划分方法：
在分割前先要在待分割区间中找一个元素作为基准值，基准值可以是区间中的任意一个元素，但是为了代码实现简单，一般都选择最左侧或者最右侧的元素作为基准值。
（1）hoare版本
代码实现：
// 快速排序递归实现
// 快速排序hoare版本
static int Mid(int begin,int mid, int end)
{
if (begin > mid)
{
if (mid > end)
{
return mid;
}
else if (end > begin)
{
return begin;
}
else
{
return end;
}
}
else //begin<mid
{
if (mid < end)
{
return mid;
}
else if (begin>end)
{
return begin;
}
else
{
return end;
}
}
}
int PartSort1(int* a, int left, int right)
{
int begin = left;
int end = right - 1;
//基准值的选取【数组的最后一个元素】
/*int key = a[end];*/
//key的选择优化【三值取中法】
int key = Mid(a[left], a[left + ((right - left) >> 1)], a[right - 1]);
while (begin < end)
{
//找到比基准值大的停下来
while (begin < end&&a[begin] < key)
{
begin++;
}
//找到比基准值小的停下来
while (begin < end&&a[end] > key)
{
end--;
}
//交换begin和end位置的值
Swap(&a[begin], &a[end]);
}
//如果begin不是最后一个位置则直接交换begin位置的值个基准值
if (begin + 1 != right)
{
Swap(&a[begin], &key);
}
return begin;
}上图选择区间最右侧的值作为基准值（key=6），然后left在区间从左往右找比基准值大的值，找到后停下来，right从右往左找比基准值小的值，找到后停下来，最后交换最大值和最小值。重复上述操作，直到left==right这时交换left所在位置的值和key的值。
（2）挖坑法
同理，先找到基准值并将基准值保存到key（假设这里的key=6）这个临时变量值中，这时就形成了一个坑位（基准值的位置），然后right从右往左找比基准值小的 ，找到后用来填key的坑（注意：这里是赋值不是交换），同理left从左往右找比基准值大的来填right的坑。重复上述，直到left==right，用key来填最后一个坑。
代码实现：
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int begin = left;
int end = right - 1;
int key = a[end];
while (begin < end)
{
//找到比基准值大的值
while (begin < end&&a[begin] < key)
{
begin++;
}
//用begin位置的值去填end位置的坑【end位置的值已经保存在了key】
a[end] = a[begin];
//找到比基准值小的值
while (begin<end&&a[end]>key)
{
end--;
}
//用end位置的值去填begin位置的坑
a[begin] = a[end];
}
//最后再用key的值去填begin/end位置的坑
a[begin] = key;
return begin;
}
代码实现：
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int cur = left;
int prev = cur - 1;
int key = a[right - 1];
while (cur < right)
{
if (a[cur] < key && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
if (++prev != right - 1)
{
Swap(&a[prev], &a[right - 1]);
}
return prev;
}6.3快速排序的递归实现（这里代码省略了划分的代码【上面的三种方式均可】）
//快排的递归实现
void QuickSort(int* a, int left, int right)
{
if (right-left <= 1)
{
return;
}
int div = PartSort1(a, left, right);
//递归排左侧
QuickSort(a, left, div);
//递归排右侧
QuickSort(a, div + 1, right);
}
快排的时间复杂度问题：
当基准值选取的比较好的话，每次都可以将序列分为左右相等的两部分
如果基准值取的不好，既基准值刚好是区间中最大或者最小的元素，按照该基准值划分好之后，基准值一侧有数据一侧没有数据
假设需要排升序，现在拿到的数据集合刚好是一个
基准值选的不同，时间复杂度也是不同的，不可能每次都选到最大或者最小的元素。
平均下来快排的时间复杂度就是O(NlogN)。
快排的空间复杂度： O(logN)
快排的优化：
1.基准值选择问题——->一般情况下不会直接拿区间最左侧或者最右侧的数据作为基准值，因为按照这种方式获取基准值，拿到最大值或者最小值的概率可能会非常高，严重影响快排的效率。
我们基准值的选取常常采用
三值取中法：最左侧，最中间，最右侧位置的数据，取这三个数据中最中间的数据作为基准值。
2.递归时区间中元素过少可以采用插入排序优化
假设：待排序集合中元素非常多，将来就会导致平衡二叉树的高度非常高（递归深度）：既递归到某个区间中只有一个元素时，递归才会回退。
问题：
1.递归深度达到一定程度—可能会导致栈溢出
2.越往下递归，区间中数据越来越少，当区间中元素越来越少时，快排就不是最理想的排序算法了。
3.待排序数据如果非常多，递归深度会非常深，在没有达到递归出口时，会有栈溢出问题。
解决方式一：
1.可以计算递归的深度—-n个元素，递归深度为h=logn
2.如果超多程序中涉及的递归总次数阈值，可以将快排转化为堆排序（因为二者时间复杂度是一样的）
解决方式二：
利用栈将递归快排转换为非递归
快排的非递归的实现【这里省略了堆的相关操作的代码实现】
/用栈来实现从递归到循环的转换
// 快速排序 非递归实现
#include"Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
Stack ps;
StackInit(&ps);
StackPush(&ps, right);
StackPush(&ps, left);
while (!StackEmpty(&ps))
{
int left = StackTop(&ps);
StackPop(&ps);
int right = StackTop(&ps);
StackPop(&ps);
if (right - left > 1)
{
int div = PartSort3(a, left, right);
//以基准值为分割点，形成左右两部分[left,div)和[div+1，right）
//基准值的左侧
StackPush(&ps, right);
StackPush(&ps, div + 1);
//基准值的右侧
StackPush(&ps, div);
StackPush(&ps, left);
}
}
StackDestroy(&ps);
}
7.归并排序
7.1基本思想：
归并排序（MERGE-SORT
）是建立在归并操作上的一种有效的排序算法
,
该算法是采用分治法（
Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
7.2归并排序流程图
归并排序动态图
7.3归并排序代码实现
//合并的方法
void MergeData(int *a,int left,int mid,int right,int temp[])
{
int begin1 = left;
int end1 = mid;
int begin2 = mid;
int end2 = right;
int index = left;
while (begin1 < end1&&begin2 < end2)
{
if (a[begin1] <= a[begin2])
{
temp[index++] = a[begin1++];
}
else
{
temp[index++] = a[begin2++];
}
}
while (begin1 < end1)
{
temp[index++] = a[begin1++];
}
while (begin2 < end2)
{
temp[index++] = a[begin2++];
}
}
// 归并排序递归（内部接口）
void _MergeSort(int *a,int left,int right,int temp[])
{
if (right - left>1)
{
//1.对区间进行均分
int mid = left + ((right - left) >> 1);
//2.将区间划分为
_MergeSort(a, left, mid, temp);
_MergeSort(a, mid, right, temp);
//3.归并
MergeData(a, left, mid, right, temp);
//4.数据的拷贝
memcpy(a + left, temp + left, sizeof(int)*(right - left));
}
}
//归并排序递归实现（外部接口）
void MergeSort(int *a, int n)
{
int *temp = (int *)malloc(sizeof(int)*n);
if (temp == NULL)
{
assert(0);
return;
}
_MergeSort(a, 0, n, temp);
free(temp);
}
// 归并排序非递归实现
void MergeSortNonR(int *a, int n)
{
//1.申请辅助空间
int *temp = (int *)malloc(sizeof(int)*n);
//2.区间的划分
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i+=gap*2)
{
int left = i;
int mid = i + gap;
int right = mid + gap;
//保证mid和right不会越界
if (mid>n)
{
mid = n;
}
if (right > n)
{
right = n;
}
//3.归并
MergeData(a, left, mid, right, temp);
}
//4.数据的拷贝
memcpy(a, temp, sizeof(int)*n);
gap = gap * 2;
}
free(temp);
}
时间复杂度：
O(N*logN)
空间复杂度：
O(N)
稳定性：稳定
四、非比较类型的排序
计数排序
1.思想：
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
2.操作步骤：
1.统计相同元素出现的次数
2.回收—–按照计数数组的下标来进行回收
3.流程图解
4.代码实现
//数据密集集中在某个范围中---一般会告诉范围
//如果没有告诉范围，先要统计出范围--->计算计数空间的大小--->申请计数空间--->统计元素出现的次数--->回收
//时间复杂度：O(N)
//空间复杂度：O(M)：M表示范围
//稳定性：稳定
void CountSort(int *a, int n)
{
//1.获取空间范围
int minValue = a[0];
int maxValue = a[0];
for (int i = 0; i < n; i++)
{
if (a[i]>maxValue)
{
maxValue = a[i];
}
if (a[i] < minValue)
{
minValue = a[i];
}
}
//2.计算计数空间大小
int range = maxValue - minValue + 1;
//3.申请新空间并置为0
int *count = (int *)malloc(sizeof(int)*range);
if (count == NULL)
{
assert(0);
return;
}
memset(count, 0, sizeof(int)*range);
//4.统计每个元素的个数
for (int i = 0; i < n; i++)
{
count[a[i]]++;
}
//5.对数据进行回收---按照count数组下标进行回收
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i])
{
a[index++] = i;
count[i]--;
}
}
}
时间复杂度：O(N)
空间复杂度：O(M)：M表示范围
稳定性：稳定
既然都看到这里了，不妨点个赞评论一下呗！！！！
