hello，好久不见！ 云边有个稻草人-CSDN博客
上篇内容，回顾一下吧【数据结构初阶第十八节】八大排序系列(上篇)—[详细动态图解+代码解析]-CSDN博客
今天我们来学习下篇
目录
———————————————《剧终The End》———————————————
续接上篇，正文开始——
（2）快速排序
【挖坑法】
—思路
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
—思路图解
—代码
//挖坑法
int _QuickSort(int* arr, int left, int right)
{
int hole = left;
int key = arr[left];
while (left < right)
{
//从右往左找比基准值小的
while (left < right && arr[right] > key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
//从左往右找比基准值大的
while (left < right && arr[left] < key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
//快排
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//1.找基准值
int key = _QuickSort(arr,left,right);
//2.左子序列进行排序
QuickSort(arr, left, key - 1);
//3.右子序列进行排序
QuickSort(arr, key + 1, right);
}【lomuto前后指针法】
—思路
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。
—思路图解
—代码
//lomuto前后指针
int _QuickSort(int* arr, int left, int right)
{
int key = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)//这里的等号加不加都一样，
//对于全是重复的数据时间复杂度很高
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[key]);
return prev;
}
//快排
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//1.找基准值
int key = _QuickSort(arr,left,right);
//2.左子序列进行排序
QuickSort(arr, left, key - 1);
//3.右子序列进行排序
QuickSort(arr, key + 1, right);
}—效果展示
—快速排序特性总结
1. 时间复杂度： O ( nlogn )2. 空间复杂度： O ( logn )
【非递归版本快排】
—思路
非递归版本的快速排序需要借助数据结构：栈。主要思路就是利用循环来模拟递归。将区间进行入栈，两次取栈顶数据（不要忘记出栈，取栈顶数据前判断栈是否为空）作为一个区间，在这个区间内通过前面学到的某种方法得到基准值，再根据基准值得到新的左右区间再入栈，入栈前要判断要入栈的区间是否是有效区间，再两次取栈顶数据循环前面操作。
—思路图解
—代码
这里我们采用lomuto方法进行取基准值
//非递归版本的快排
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
//首先将left和right进行入栈
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素--取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//找基准值
int keyi = begin;
int cur = begin + 1;
int prev = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
keyi = prev;//找到了基准值
//根据基准值再去找新的左右区间再入栈
//左区间:[begin,keyi-1]
//右区间:[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}4.归并排序
—大致思路
利用二叉树递归的思想先将数组进行递归分解，直到每个区间分的只有一个数据此时不能再分，分解之后就是合并，注意合并的是一个数组里面两个区间里的数据并不是真的新的两个数组，合并的方法是利用我们前面学到的算法题—合并两个数组；我们是将合并之后有序的数据先存放到一个新创建的tmp数组里面，再将tmp里面的数据拷贝给原数组arr，这样方便操作一些；就这样在不断递归的过程中完成排序操作。
—大致思路图解
—代码
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//先递归分解
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
//合并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp里面的数据拷贝回arr里面
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
//归并排序
void MergeSort(int* arr, int n)
{
//重新创建一块空间来存放数据
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1,tmp);
free(tmp);
}—归并排序特性总结
1. 时间复杂度： O ( nlogn )2. 空间复杂度： O ( n )
—效果展示
对于同样的10W个数据，不同的排序分别用了多久
5.测试代码：排序性能对比
前面我们讲过的，这里再发一下，看一下代码就可以明白其中的道理。
// 测试排序的性能对⽐
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSortNonR(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
TestOP();
return 0;
}6.非比较排序—计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：1）统计相同元素出现次数2）根据统计的结果将序列回收到原来的序列中
—图解
—代码
//计数排序
void CountSort(int* arr, int n)
{
//根据最大值和最小值来确定数组的大小
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc file!");
exit(1);
}
//初始化range数组里面的数据都为0
memset(count, 0, range * sizeof(int));
//统计原数组中每个数据出现的次数,将次数存放对应的在count数组里面
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//将count里面的数据往arr里面去放
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}—计数排序的特性
计数排序在数据范围集中时，效率很高，但是适⽤范围及场景有限，只适用于整数排序，无法对小数进行排序。时间复杂度： O(N + range) —遍历一遍 count 数组，里面的 while 循环执行了N次，就是有多少个数据就执行多少次空间复杂度： O(range) —开辟了range个空间稳定性：稳定
—效果展示
这么强 ？！！！
0 ？！真假的
三、排序算法复杂度及稳定性分析
稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。（就是相同的数据排序之后的相对次序保持不变）
自己把前面的所有排序算法都理解透彻并能自己实现出来，自己理解下面的表格就会很轻松，不然都忘记了就会很痛苦。。。对于稳定性自己找出实例后独立分析
四、两节课代码汇总
Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int capacity; //栈的容量
int top; //栈顶
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入数据
void StackPush(ST* ps, STDataType x);
//出数据
void StackPop(ST* st);
//取栈顶元素
STDataType StackTop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//获取栈中有效的数据个数
int STsize(ST* ps);sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<memory.h>
void Print(int* arr, int n);
void BubbleSort(int* arr, int n);
void HeapSort(int* arr, int n);
void InsertSort(int* arr, int n);
void ShellSort(int* arr, int n);
void SelectSort(int* arr, int n);
void QuickSort(int* arr, int left, int right);
//非递归版本的快排
void QuickSortNonR(int* arr, int left, int right);
//归并排序
void MergeSort(int* arr, int n);
//计数排序
void CouuntSort(int* arr, int n);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0; //此时栈为空，栈顶=栈底
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//入数据
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->capacity == ps->top)
{
//申请空间
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc file!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}
//出数据
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
//获取栈中有效的数据个数
int STsize(ST* ps)
{
assert(ps);
return ps->top;
}sort.c
#include"sort.h"
#include"Stack.h"
void Print(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] < arr[j + 1])
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
//向下调整数据
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//找出左右孩子中最小的->小堆 >
//找出左右孩子中最大的->大堆 <
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
// < 建小堆
// > 建大堆
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* arr, int n)
{
//向下调整算法建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
//堆排序
int end = n - 1;
while (end > 0)
{
//end指向的是最后一个数据
Swap(&arr[0], &arr[end]);
//有效的数据个数减了1
AdjustDown(arr, 0, end);
end--;
}
}
//直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;//--是为了让tmp与区间前面的元素进行挨个比较，最后找到合适的位置
}
else
{
break;
}
}
//此时end可能等于-1，或者是因为end指向的元素 < tmp，此时我们还没有进行最后的赋值，
//这时我们都要把tmp里面的数据赋值给arr[end+1]
arr[end + 1] = tmp;
}
}
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
//用来控制gap，当gap==1时就是直接插入排序
while (gap > 1)//不能等于1，等于1的话最后会死循环
{
gap = gap / 3 + 1;//保证最后一次gap一定为1，/3,是为了让每组数据个数较恰当
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = end;
end-=gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
直接选择排序
//void SelectSort(int* arr, int n)
//{
// for (int i = 0; i < n; i++)
// {
// int mini = i;
// //找后面区间里最小值的下标
// for (int j = i; j < n; j++)
// {
// if (arr[j] < arr[mini])
// {
// mini = j;
// }
// }
// Swap(&arr[i], &arr[mini]);
// }
//}
//直接插入排序
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
//在后面区间内找maxi，mini
for (int j = begin+1; j <= end; j++)
{
if (arr[j] < arr[mini])
{
mini = j;
}
if (arr[j] > arr[maxi])
{
maxi = j;
}
}
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
Hoare版本找基准值
//int _QuickSort(int* arr, int left, int right)
//{
// int key = left;
// left++;
// while (left <= right)
// {
// //找比基准值大的
// while (left <= right && arr[left] < arr[key])
// {
// left++;
// }
// //找比基准值小的
// while (left <= right && arr[right] > arr[key])
// {
// right--;
// }
// if (left <= right)
// {
// Swap(&arr[right--], &arr[left++]);
// }
// }
// //将right指向的数据和key指向的数据进行交换
// Swap(&arr[key], &arr[right]);
//
// return right;
//}
挖坑法
//int _QuickSort(int* arr, int left, int right)
//{
// int hole = left;
// int key = arr[left];
// while (left < right)
// {
// //从右往左找比基准值小的
// while (left < right && arr[right] > key)
// {
// right--;
// }
// arr[hole] = arr[right];
// hole = right;
//
// //从左往右找比基准值大的
// while (left < right && arr[left] < key)
// {
// left++;
// }
// arr[hole] = arr[left];
// hole = left;
// }
// arr[hole] = key;
// return hole;
//}
//lomuto前后指针
int _QuickSort(int* arr, int left, int right)
{
int key = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[key]);
return prev;
}
//快排
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//1.找基准值
int key = _QuickSort(arr,left,right);
//2.左子序列进行排序
QuickSort(arr, left, key - 1);
//3.右子序列进行排序
QuickSort(arr, key + 1, right);
}
//非递归版本的快排
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
//首先将left和right进行入栈
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素--取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//找基准值
int keyi = begin;
int cur = begin + 1;
int prev = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
keyi = prev;//找到了基准值
//根据基准值再去找新的左右区间再入栈
//左区间:[begin,keyi-1]
//右区间:[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//先递归分解
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
//合并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp里面的数据拷贝回arr里面
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
//归并排序
void MergeSort(int* arr, int n)
{
//重新创建一块空间来存放数据
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1,tmp);
free(tmp);
}
//计数排序
void CountSort(int* arr, int n)
{
//根据最大值和最小值来确定数组的大小
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc file!");
exit(1);
}
//初始化range数组里面的数据都为0
memset(count, 0, range * sizeof(int));
//统计原数组中每个数据出现的次数,将次数存放对应的在count数组里面
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//将count里面的数据往arr里面去放
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}test.c
#include"sort.h"
void test()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(int);
printf("排序前：");
Print(arr, n);
/*InsertSort(arr, n);*/
/*BubbleSort(arr, n);*/
CountSort(arr,n);
printf("排序后：");
Print(arr, n);
}
// 测试排序的性能对⽐
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
int begin8 = clock();
CountSort(a8, N);
int end8 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
printf("CountSort:%d\n", end8 - begin8);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
int main()
{
//TestOP();
test();
return 0;
}数据结构初阶的所有内容就更新完了，后面还有一些加餐内容。下面我们正式开启C++和Linux的内容。。。
完——
未完待续——
———————————————《剧终The End》———————————————
（放学骑车的路上随机播放到了这首歌，感觉挺应景的，就它喽。看到一条评论：比起剧终，我更喜欢未完待续）
（你相信星座吗，我一开始不相信，后来发现真的有点像，说实话现在也不咋相信，但是这是巧合吗还是，疑惑）
至此结束！
我是云边有个稻草人。。。
期待与你的下一次相遇，再见！