CC++实现快速排序算法的思路及原理解析⽬录快速排序2. 实现原理3. 动态演⽰4. 完整代码5. 结果展⽰6. 算法分析快速排序1. 算法思想快速排序的基本思想：通过⼀趟排序将待排记录分隔成独⽴的两部分，其中⼀部分记录的关键字均⽐另⼀部分的关键字⼩，则可分别对这两部分记录继续进⾏排序，以达到整个序列有序。
2. 实现原理2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
2.2、整个数组找基准正确位置，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯默认数组的第⼀个数为基准数据，赋值给key，即key=array[low]。
因为默认数组的第⼀个数为基准，所以从后⾯开始向前搜索（high–），找到第⼀个⼩于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。
（循环条件是 array[high] >= key；结束时 array[high] < key）此时从前⾯开始向后搜索（low++），找到第⼀个⼤于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。
（循环条件是 array[low] <= key；结束时 array[low] > key）循环 2-3 步骤，直到 low=high，该位置就是基准位置。
把基准数据赋给当前位置。
2.3、第⼀趟找到的基准位置，作为下⼀趟的分界点。
2.4、递归调⽤（recursive）分界点前和分界点后的⼦数组排序，重复2.2、2.3、2.4的步骤。
2.5、最终就会得到排序好的数组。
3. 动态演⽰4. 完整代码三个函数基准插⼊函数：int getStandard(int array[],int low,int high)（返回基准位置下标）递归排序函数：void quickSort(int array[],int low,int high)主函数：int main()#include <stdio.h>#include <stdlib.h>void display(int* array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");}int getStandard(int array[], int i, int j) {// 基准数据int key = array[i];while (i < j) {// 因为默认基准是从左边开始，所以从右边开始⽐较// 当队尾的元素⼤于等于基准数据时,就⼀直向前挪动 j 指针while (i < j && array[j] >= key) {j--;}// 当找到⽐ array[i] ⼩的时，就把后⾯的值 array[j] 赋给它if (i < j) {array[i] = array[j];}// 当队⾸元素⼩于等于基准数据时,就⼀直向后挪动 i 指针while (i < j && array[i] <= key) {i++;}// 当找到⽐ array[j] ⼤的时，就把前⾯的值 array[i] 赋给它if (i < j) {array[j] = array[i];}}// 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置// 把基准数据赋给正确位置array[i] = key;return i;}void QuickSort(int array[], int low, int high) {// 开始默认基准为 lowif (low < high) {// 分段位置下标int standard = getStandard(array, low, high);// 递归调⽤排序// 左边排序QuickSort(array, low, standard - 1);// 右边排序QuickSort(array, standard + 1, high);}}// 合并到⼀起快速排序// void QuickSort(int array[], int low, int high) {// if (low < high) {// int i = low;// int j = high;// int key = array[i];// while (i < j) {// while (i < j && array[j] >= key) {// j--;// }// if (i < j) {// array[i] = array[j];// }// while (i < j && array[i] <= key) {// i++;// }// if (i < j) {// array[j] = array[i];// }// }// array[i] = key;// QuickSort(array, low, i - 1);// QuickSort(array, i + 1, high);// }// }int main() {int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};int size = sizeof(array) / sizeof(int);// 打印数据printf("%d \n", size);QuickSort(array, 0, size - 1);display(array, size);// int size = 20;// int array[20] = {0}; // 数组初始化// for (int i = 0; i < 10; i++) { // 数组个数// for (int j = 0; j < size; j++) { // 数组⼤⼩// array[j] = rand() % 1000; // 随机⽣成数⼤⼩ 0~999// }// printf("原来的数组：");// display(array, size);// QuickSort(array, 0, size - 1);// printf("排序后数组：");// display(array, size);// printf("\n");// }return 0;}5. 结果展⽰（递归调⽤，不好展⽰每次排序结果）6. 算法分析时间复杂度：最好： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)最坏： O ( n 2 ) O(n^2) O(n2)平均： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)空间复杂度： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)稳定性：不稳定到此这篇关于C/C++实现快速排序算法的思路及原理解析的⽂章就介绍到这了,更多相关C++实现快速排序算法内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！。
