快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
(1)算法步骤
1. 从数列中挑出一个元素,称为 “基准”(pivot);
2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
(2)动图演示
(3)C语言代码实现如下:
#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; }
如果我们编译并运行上述程序,那么它应该产生以下结果:
-10 -1 0 12 13 15 20 100
1716 | 数据结构-快速排序 |
2020 | 快速排序练习 |
2214 | 蓝桥杯算法提高-快速排序 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程