快速排序（Quick Sort）是基于二分思想，对冒泡排序的一种改进。主要思想是确立一个基数，将小于基数的数字放到基数的左边，大于基数的数字放到基数的右边，然后再对这两部分数字进一步排序，从而实现对数组的排序。
其优点是效率高，时间复杂度平均为O(nlogn)，顾名思义，快速排序是最快的排序算法，耗费的资源少，最佳情况下，空间复杂度为O(logn)，每一次都平分数组的情况，代码较为简单。
其缺点是不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。
例如：
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 | public class Main { //快排实现方法 public static void quickRow(int[] array,int low,int high) { int i,j,pivot; //结束条件 if(low >= high) { return; } i = low; j = high; //选择的节点，这里选择的数组的第一数作为节点 pivot = array[low]; while(i<j) { //从右往左找比节点小的数，循环结束要么找到了，要么i=j while(array[j] >= pivot && i<j) { j--; } //从左往右找比节点大的数，循环结束要么找到了，要么i=j while(array[i] <= pivot && i<j) { i++; } //如果i!=j说明都找到了，就交换这两个数 if(i<j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } //i==j一轮循环结束，交换节点的数和相遇点的数 array[low] = array[i]; array[i] = pivot; //数组“分两半”,再重复上面的操作 quickRow(array,low,i-1); quickRow(array,i+1,high); } public static void main(String[] args) { int[] array = {6,17,38,59,2,10}; int low = 0,high = array.length-1; quickRow(array,low,high); for (int i : array){ System.out.println(i); } }} |
运行结果如下：
1 2 3 4 5 6 | 2610173859 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程