快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n²)次比较。

算法原理

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

步骤为：

1. 从数列中挑出一个元素，称为 "基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

问题：怎么找到基准？

无所谓，可以随机取，也可以取首元素。【具体想一想就明白了】

算法实现

Python版：

【PS，由于是算法，我不赞同更多利用Python特性来写，Pythonic的代码不超过10行就搞定了，最后附上！】

#-*- encoding: utf-8 -*-        

def quick_sort(st_bf):
    # 快速排序
    j = 0 # 标记哨兵位置
    if len(st_bf) > 1:
        tag = st_bf[0] # 设置哨兵
        for i in xrange(1, len(st_bf)):
            if st_bf[i] < tag:
                temp = st_bf[i]
                # 小于tag位置挪到tag前面,也就是tag和比tag大的整体后移
                for k in xrange(i, j, -1):
                    st_bf[k] = st_bf[k-1]
                st_bf[j] = temp # 小元素移到哨兵前面
                j += 1
            else:
                # 大于tag不用处理    
                pass
    else:
        return st_bf
    # 递归处理左右子区间
    print 'st_bf = ', st_bf
    left = quick_sort(st_bf[:j:])
    right = quick_sort(st_bf[j+1::])
    print left + [st_bf[j]] + right
    return left + [st_bf[j]] + right
            
st_bf = [4, 5, 9, 2, 6, 8, 1, 7, 3] 

print quick_sort(st_bf)

>>> ================================ RESTART ================================
>>> 
st_bf =  [2, 1, 3, 4, 5, 9, 6, 8, 7]
st_bf =  [1, 2, 3]
[1, 2, 3]
st_bf =  [5, 9, 6, 8, 7]
st_bf =  [6, 8, 7, 9]
st_bf =  [6, 8, 7]
st_bf =  [7, 8]
[7, 8]
[6, 7, 8]
[6, 7, 8, 9]
[5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 

Pythonic版：充分利用List Comprehensions（点击查看详细）

#-*- encoding: utf-8 -*-        

def quick_sort(st_bf):
    # 快速排序
    if len(st_bf) > 1:
        temp = st_bf[0]
        st_now = quick_sort([i for i in st_bf[1:] if i < temp]) +                 [temp] +                  quick_sort([j for j in st_bf[1:] if j >= temp])
        return st_now
    else:
        return st_bf
            
st_bf = [4, 5, 9, 2, 6, 8, 1, 7, 3] 

print quick_sort(st_bf)

C++实现：

#include <iostream>
using namespace std;

void print (int st_bf[], size_t size){
    for (size_t i = 0; i < size; i++)
    {
        cout<< st_bf[i] << " ";
    }
    cout<< endl;
}

void quick_sort(int *st_bf, size_t size){
    //快速排序
    size_t j = 0; // 标记哨兵位置
    if (size > 1){
        int tag = st_bf[0]; // 设置哨兵

        for (size_t i = 1; i < size; ++i){
            if (st_bf[i] < tag){
                int temp = st_bf[i];
                // 小于tag位置挪到tag前面,也就是tag和比tag大的整体后移
                for (size_t k = i; k > j; --k){
                    st_bf[k] = st_bf[k-1];
                }
                st_bf[j] = temp; // 小元素移到哨兵前面
                j += 1;
            } else {/*大于tag不用处理*/}
        }
    } else {/*空数组，无需处理*/}
    // 递归处理左右子区间
    if (j > 0) quick_sort(st_bf, j);
    size_t len_right = size-j-1;
    if (len_right > 0) quick_sort(st_bf+j+1, len_right);
}

int main(){
    int st_bf[] = {4, 5, 9, 2, 6, 8, 1, 7, 3};
    size_t size = sizeof(st_bf)/sizeof(st_bf[0]);
    quick_sort(st_bf, size);
    print(st_bf, size);
    return 0;
}

本文由@The_Third_Wave（Blog地址：http://blog.csdn.net/zhanh1218）原创。还有未涉及的，会不定期更新，有错误请指正。

如果你看到这篇博文时发现没有不完整，那是我为防止爬虫先发布一半的原因，请看原作者Blog。

如果这篇博文对您有帮助，为了好的网络环境，不建议转载，建议收藏！如果您一定要转载，请带上后缀和本文地址。

排序算法分析【六】：快速排序（附Python&C++代码）