算法笔记（第一部分）-- 排序之白话快速排序

记得今年暑假找实习的时候，去过一家小公司Xoopit做On-Site interview，里面有个工程师给我出了一道Hardcode的问题：给定一个无序数组，以及一个数组中的元素，要求输出的数组中小于这个数的数都有序的排在它之前，大于它的数都有序的排在它之后。当时想了半天才写出一个很烂的解法。最近重新复习排序，发现这不就是典型的Quick Sort的应用么。

快速排序的步骤：
1. 从数组中选出一个中枢数(pivot)
2. 重新排列该数组，让数组中比该数小的数都排在该数的前面，比该数大的数都排在该数的后面。经过这次排列，该数处于其最终位置，并将原数组分为了两个子数组（大于它的数组和小于它的数组），这就是分段的过程。
3. 递归的排列各个子数组，直至最后整个数组排序完成。

快速排序的平均时间复杂度为O(nlogn)，空间复杂度依据各种实现方式有所不同。

快速排序的动画：


快速排序代码－partition:

public int partition(int[] data, int left, int right, int pivotIndex){
           int pivotValue = data[pivotIndex];
           swap(data, pivotIndex, right);// Move pivot to end
           int storeIndex = left;
           for(int i=left; i<right; i++){
             if(data[i]<=pivotValue){
                   swap(data, i, storeIndex);
                   storeIndex = storeIndex + 1;
             }
           }
           swap(data, storeIndex, right);// Move pivot to its final place 
           return storeIndex;
      }

quickSort:

public void quick_sort(int[] data, int left, int right){
            if(right>left){
                  int pivotIndex = left;
                  int pivotNewIndex = partition(data, left,right, pivotIndex);
                  quicksort(data, left, pivotNewIndex - 1);
                  quicksort(data, pivotNewIndex + 1, right);
            }
      }

partition的过程（递增）：
1. 将中枢数移至数据集的最右边
2. 建立一个中枢数最终位置的下标值。从数据集的最左边循环至最右边，依次与该中枢数相比较，若该数小于中枢数，则将该数与中枢数最终位置值交换，最终位置的下标加一
3. 最终将中枢数移至最终位置，返回最终位置下标

这种实现方法的空间复杂度是O(nlogn)，它是in-place的算法，并且因为在一个partition的过程中可能会交换两数的位置，因此它是不稳定的。感觉初次理解快排有些难度，自己写出来就好多了。

评论

9 楼 sunspring 2008-09-02  

swap函数呢？？

8 楼 王者之剑 2008-09-01  

图片怎么做的

7 楼 backbase 2008-09-01  

谢谢楼主的分享， 希望楼主以后分享跟多的算法文章，

6 楼 25wanghai 2008-08-31  

我也喜欢这图片，谢谢哈

5 楼 isyull 2008-08-31  

引用

要求输出的数组中小于这个数的数都有序的排在它之前，大于它的数都有序的排在它之后

直接给数组排个序，任何一个数都满足上面这句话

4 楼 chamborghini 2008-08-31  

图片挺不错的!

3 楼 bnmcvzx 2008-08-29  

为什么不说它是2叉树的算法呢

2 楼 zpl3001 2008-08-29  

1 楼 congjl2002 2008-08-29  

这个图片到是非常的生动，谢谢分享