快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
（1）算法步骤
1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
（2）动图演示
（3）C语言代码实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include <stdio.h>#include <stdlib.h>/*快速排序算法学习*/void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;}void quickSort(int arr[] ,int start, int end){ int arrBase, arrMiddle; int tempStart = start, tempEnd = end; //对于这种递归的函数，内部必须要有一个函数返回的条件 if(tempStart >= tempEnd) return; //拷贝一个基准值作为后面比较的参数 arrBase = arr[start]; while(start < end) { while(start < end && arr[end] > arrBase) end--; if(start < end) { swap(&arr[start], &arr[end]); start++; } while(start < end && arr[start] < arrBase) start++; if(start < end) { swap(&arr[start], &arr[end]); end--; } } arr[start] = arrBase; arrMiddle = start; //分治方法进行递归 quickSort(arr,tempStart,arrMiddle-1); quickSort(arr,arrMiddle+1,tempEnd);}int main(){ int myArr[] = {12,13,15,20,0,-1,-10,100}; int arrLength = sizeof(myArr)/sizeof(int); quickSort(myArr,0,arrLength-1); for(int i = 0; i<arrLength; i++) printf("%5d",myArr[i]); return 0;} |
如果我们编译并运行上述程序，那么它应该产生以下结果：
1 | -10 -1 0 12 13 15 20 100 |
作业：
| 1716 | 数据结构-快速排序 |
| 2020 | 快速排序练习 |
| 2214 | 蓝桥杯算法提高-快速排序 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程