😘个人主页：@Cx330❀

👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生

📖个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》

前言：在上篇博客的学习中，我们掌握了直接选择排序和堆排序，发现堆排序算法的优秀，那么今天我们就进入冒泡排序和快速排序的学习中

一、冒泡排序

代码实现：

测试结果：

复杂度分析:

二.快速排序(递归实现)

代码实现（框架）：

找基准值划分的三种实现方式：

1.hoare版本

2.挖坑法

3.lomuto前后指针

4.基准值的重要性

时间复杂度：

测试结果：

三.非递归实现快速排序

代码实现：

测试结果：

四.冒泡排序和快速排序性能对比

代码实现：

一、冒泡排序

冒泡排序大家肯定都不陌生了，我们直接来看代码吧

代码实现：

//冒泡排序
void BubbleSort(int* arr, int n)
{int change = 1;for (int i = 0; i < n-1; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);change = 0;}}if (change == 1){break;}}
}

图解：

test.c:

#include"Sort.h"
void printArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test01()
{int a[] = { 5,3,9,6,2,4,7,1,8 };//int a[] = { 6,1,2,7,9,3 };int n = sizeof(a) / sizeof(a[0]);printf("排序之前：");printArr(a, n);//InsertSort(a, n);//ShellSort(a, n);//SelectSort(a, n);//HeapSort(a, n);BubbleSort(a, n);//QuickSort(a, 0, n - 1);//QuickSortNorR(a, 0, n - 1);//MergeSort(a, n);//CountSort(a, n);//MergeSortNonR(a, n);printf("排序之后：");printArr(a, n);
}
int main()
{test01();return 0;
}

测试结果：

测试完成，打印没有问题，升序排列正确，退出码为0

复杂度分析:

时间复杂度：O(N^2)

冒泡排序比较简单，博主这里的冒泡排序是优化过的，当某一次已经有序了就会直接结束

二.快速排序(递归实现)

快速排序是Hoare于1962年提出的⼀种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

代码实现（框架）：

void QuickSort(int* arr, int left, int right)
{if (left >= right){return ;}//左【left, keyi - 1】   右【keyi+1,right】int keyi = _QuickSort(arr, left, right);QuickSort(arr, left, keyi - 1);QuickSort(arr,keyi+1,right);
}

图解：

采用递归的思想，有些类似二叉树的前序遍历，分组进行划分。

找基准值划分的三种实现方式：

将区间元素进行划分的_QuickSort方法主要有以下几种实现方法：

1.hoare版本

思路：

创建left和right指针
(升序)从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换。进入下次循环-------我们默认left初始位置的值为基准值，特别注意一下确定基准之后left要先++一次。
循环结束后，交换keyi和right位置的值，然后返回right下标

代码实现：

//找基准值--hoare版本
int _QuickSort1(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){//right从右往左找比基准值小的，如果大于基准值就--while (left <= right && arr[right] > arr[keyi]){--right;}//left从左往右找比基准值大的，如果小于基准值就++while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交换if(left<=right)Swap(&arr[left++], &arr[right--]);}//right位置就是基准值的位置Swap(&arr[right], &arr[keyi]);return right;
}

注意事项：

1.为什么跳出循环后right位置的值一定不大于key？

答：当left>right时，即right走到left的左侧，而left扫过的数据均不大于key，所有right此时所指向的数据一定不大于key

三种情况都在图中有所讲解，大家可以仔细的看一下

2.内层循环不能等于，数据重复的情况下会造成时间复杂度变为O(n^2)

2.挖坑法

思路：

创建右指针，（这个思路left不用先++）首先从右向左找出比基准小的，找到后立即放入坑中，当前位置变为新的坑。
然后从左到右找出比基准大的数据，找到后立即放到右边坑中，当前位置变为新的坑
结束循环后将最开始存储的分界值放入当前的坑中，返回当前坑的下标

代码实现：

//找基准值--挖坑法
int _QuickSort(int* arr, int left, int right)
{int hole = left;int key = arr[hole];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;
}

图解：

3.lomuto前后指针

思路：

创建左右指针prev和cur，cur从左往右找比基准值要小的数据
cur指向的数据比基准值要小的话，++prev,（且++prev！=cur）,交换cur和prev位置的值。再++cur
cur指向的数据不比基准值小的话，直接++cur
循环结束后，交换keyi位置和prev位置的值，返回prev下标

代码实现：

//找基准值--lumoto双指针法
int _QuickSort2(int* arr, int left, int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur < right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}++cur;}Swap(&arr[prev], &arr[keyi]);return prev;
}

图解：

4.基准值的重要性

我们一般默认最左边就是我们要找的基准值，但其实我们是有特定方法求出比较好的基准值的，这个在后续的提升篇中会有讲解

时间复杂度：

O(n*logn)

递归时间复杂度=单次递归时间复杂度(n)*递归次数(树的最大高度，logn)=n*logn

test.c：

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//快速排序QuickSort(a, 0, size - 1);printf("排序后:");PrintArr(a, size);
}int main()
{test1();return 0;
}

测试结果：

三种找基准的方法结合快速排序主体最后测试都没有问题，这里就放一个图了，升序排列正确，退出码为0

三.非递归实现快速排序

我们非递归实现快速排序需要借助数据结构栈，直接使用我们之前自己实现过的就行了，然后在.c文件里面引入一下栈的.h文件。具体操作和之前我们借助队列实现二叉树的层序遍历和判断二叉树是否为完全二叉树差不多，但是不用修改数据类型

思路：

1.初始化栈：首先将整个数组的起始索引（如 0）和结束索引（如 n-1）作为初始区间推入栈中，先推结束的再推起始的。

2.循环处理栈中区间：当栈不为空时，执行以下操作：

弹出区间：从栈顶取出一个待排序区间的起始索引 begin 和结束索引 end。
划分区间：调用划分函数（与递归版相同），选择基准元素，将区间 [begin, end] 划分为左子区间 [begin, keyi-1]（元素均小于基准）和右子区间 [keyi+1, end]（元素均大于基准），返回基准元素的最终位置 keyi。
推入子区间：若左子区间存在（即 begin < keyi-1），将其边界 (begin, keyi-1) 推入栈；若右子区间存在（即 keyi+1 < end），将其边界 (keyi+1, end) 推入栈。

3.结束条件：当栈为空时，所有子区间均已排序完成，整个数组排序结束。

需要注意的时栈先进后出，所以我们一般都是先推右再推左，不管是左子区间右子区间还是左边范围右边范围都是这样的

代码实现：

//找基准值非递归版--栈
int QuickSortNorR(int* arr, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){//取栈顶两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//[begin,end]--找基准值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDesTroy(&st);
}

图解：

test.c：

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//非递归快速排序QuickSortNoare(a, 0, size - 1);printf("排序后:");PrintArr(a, size);
}
int main()
{test1();return 0;
}

测试结果：

测试完成，打印没有问题，非递归版本升序排序正确，退出码为0

四.冒泡排序和快速排序性能对比

我们还是通过测试来对比一下这两种排序的性能，大家也可以看看和之前实现过的排序的对比

代码实现：

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//直接插入排序//InsertSort(a, size);//希尔排序//ShellSort(a, size);//直接选择排序//SelectSort(a, size);//堆排序//HeapSort(a, size);//冒泡排序//BubbleSort(a, size);//快速排序//QuickSort(a, 0, size - 1);//非递归快速排序QuickSortNoare(a, 0, size - 1);printf("排序后:");PrintArr(a, size);
}// 测试排序的性能对比
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();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();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();//test1();return 0;
}

我们可以看出快速排序要比冒泡快很多，和其它排序相比的情况下，快速排序也是很快的