快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
快速排序原理示意图：
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。
以上内容来自：
JAVA版参考源码：
- package algorithm;
- public class Sort_quick {
- //打印数组
- public static void printArr(int[] arr) {
- for (int i:arr)
- System.out.print(i+" ");
- System.out.println();
- }
- //获得基准位的位置
- public static int partition(int []arr,int left,int right){
- //固定的切分方式
- int key=arr[left],temp;
- while(left<right){//两个哨兵相遇则停止
- while(left<right&&arr[right]>=key){//从右边开始找,找一个小于基准数的,找到则停止
- right--;
- }
- arr[left]=arr[right];
- while(left<right&&arr[left]<=key){//从左边开始找,找一个大于基准数的，找到则停止
- left++;
- }
- arr[right]=arr[left];
- }
- //这时候arr[left]和arr[right]很可能相等,且还差key的值没排进去
- arr[right]=key;
- //打印每一轮排序的结果
- printArr(arr);
- return right;
- }
- public static void quickSort(int[] arr,int left ,int right){
- if(left>=right){
- return ;
- }
- int index=partition(arr,left,right);
- quickSort(arr,left,index-1);
- quickSort(arr,index+1,right);
- }
- public static void main(String args[]) {
- int[] arr = {6,1,2,7,9,3,4,5,10,8};
- quickSort(arr,0,arr.length-1);
- }
- }
在这篇日志，包含后期的日志中，对于一个算法，波波分享的侧重点会放在原理上，争取刚入门的小白们都能看得懂。可能不会针对一个算法再写多种不同版本的了，毕竟网上有很多源码可以参考。写程序本身也应该触类旁通。
