目录
// 插入排序
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)
稳定性：稳定
应用场景：序列接近有序或者元素个数比较少
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然 后取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
// 希尔排序
//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;
}
}
}gap的取值是有多种方法的，不同的gap取值不同则会有不同的时间复杂度。我们这里gap的选取原则是gap = gap / 3 + 1
时间复杂度：
空间复杂度：O(1)
稳定性：不稳定
应用场景：数据比较随机，数据量比较大。（分组之后减少了数据量）
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的 起始位 置，直到全部待排序的数据元素排完 。
上图每次找到序列中最小数的一个位置，将位置标记起来，将一次遍历完成之后将最小值的 位置和区间最前面的一个值交换。（每次找到一个最小值）
// 选择排序
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]);
}
}
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)
稳定性：不稳定
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
// 堆排序
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);
}
注意：排升序的时候是建小堆，排降序的时候是建大堆
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]);
}
}
}
}代码实现：
// 快速排序递归实现
// 快速排序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);
}
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
//合并的方法
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)
//空间复杂度：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表示范围
稳定性：稳定
既然都看到这里了，不妨点个赞评论一下呗！！！！
