快速排序

上链接

http://blog.csdn.net/vayne_xiao/article/details/53508973
快速排序的话，这篇图文的，讲的很清晰，容易理解

代码加了一些注释

void split(int left, int right)
{
    // 首先将不要的东西先return 掉
    if (left > right) return;
    
    // 这里为什么不在下面直接用left和right，是因为left和right的值等下要递归用，所以不能操作他
    int i = left;
    int j = right;
    
    // 基准数位置
    int baseIndex = left;
    // 基准数
    int base = array[left];
    // 最外部的循环，就是两个哨兵一直在找想要的值，然后交换，直到这两个哨兵站到一起(相遇)i和j就代表了两个哨兵的位置
    // 排序后的结果，从左到右是从小到大
    while (i != j) {
        // 右边的哨兵找比基准数小的值的位置
        // 当右边哨兵的值大于基准书&&i<j(如果i>j就不对了，i哨兵站到j哨兵的右边了)，
        // 就继续j--，往左边走，直到找到小于基准书的值或者遇见哨兵
        while (array[j] >= base && i < j) {
            j--;
        }
        // 当右边的哨兵找到小于基准数的值后，就停下来，轮到右边的i哨兵找大于基准数
        
        // 左边的哨兵找比基准数大的值的位置
        while (array[i] <= base && i < j) {
            i++;
        }
        
        // 这时候的i和j对应的位置就是要来交换的了
        if (array[i] != array[j]) {
            swap(array[i], array[j]);
        }
    }
    
    // 结束循环后，基准数要归位，就是将基准数和两个哨兵相遇的数交换
    swap(array[baseIndex], array[i]);
    
    // 走完一次后，这时候基准数将数组分隔成两个部分
    split(left, i-1);
    split(i+1, right);
    // 因为是递归的，所以这也就是为什么一开始要加 while (i != j) { }
    // 就是为了结束递归，当i = j的时候，也就是split(i,j)这两个哨兵相遇的时候，就可以结束递归了
}

时间复杂度

第一次while循环为n

然后切割成两个子问题，这种为logN

所以总的为 nlogN