深入快速排序

sort排序很多Acmer都不陌生，甚至经常使用，那么它是怎样实现的呢❔

可视化快速排序算法

原理

在序列中任意选择一个数(通常为第一个数),然后把序列分成比这个数大的和比这个数小的两个子序列。不断重复以上步骤完成排序

为了方便,以下统称 比 基准值小的序列元素 为 小元素,比基准值大的序列元素为 大元素

举例

方法一

选定a[0]为基准，理想情况是后面都是大元素，不交换
可见，交换策略为:后面出现小元素
具体实现：

1. 确定待排序序列的基准pivot = a[0]
2. 遍历来划分剩余序列，通过比较和交换，使得左半边都为小元素，右半边为大元素
3. 最后交换基准和最后一位小元素,即可完成对序列的一次快排操作
4. 即
   • 开始->基准-剩余序列
   • -> 基准-小元素-大元素
   • -> 小元素-基准-大元素`

对原数组a[5] = {4,5,7,3,6} 进行第一轮快速排序

beg = 0;
end = 4;

取枢轴元素 pivot = a[beg] = a[0]
设定索引 index = beg + 1

接下来遍历[beg+1,end]即[1,4]内的元素
按照策略，每当出现 a[i] < pivot 的情况时
交换 index 和 a[i] 的值，确保小的值都会被换到前面
并且index++,继续寻找是否有下一个可交换的小元素
如果没有找到，那么不做处理

直到[beg+1,end]区间遍历结束，小元素和大元素都已经划分完毕，此时交换枢轴和最后一位小元素
完成一轮快速排序

pivot = a[0] = 4
index = 1
4 5 7 3 6
遍历[1,4]区间
//找到3小于4，交换a[i] 和 index
4 3 7 5 6
index = 2   //index++
4 3 7 5 6   //遍历结束没有再找到
//此时确定最后一位小元素的下标为index - 1 = 1
index = 1 //pivot与其交换
//交换完成后即完成一轮快速排序
3 4 7 5 6

方法二

选定a[0]为枢轴pivot,设定索引 left 和 right
分别指定left,right除去pivot后剩余序列的起始位置
主要思想和方法一相同，不过由于有两个游标，写法上有些微区别

最终局面:
    需要索引 left 的左边全都是`小元素`
    需要索引 right 的右边全都是`大元素`

交换策略: 索引 left 指向大元素，索引 right 指向小元素，两者同时发生时执行交换，如果只有一方达成交换条件，那么继续循环直到另一方也达成交换条件

4 5 7 3 6
pivot = a[0] = 4
left = 1,right = 4
4 5 7 3 6
遍历[1,4]区间
left = 1 -> 5 > 4 ,left出现大元素,满足交换条件
right = 3 -> 3 < 4 ,right出现小元素,满足交换条件
执行交换,得到
4 3 7 5 6
此时left++ 后 left = 2, right-- 后 right = 2
while(left < right) 满足，继续循环
>如果在left == right 时退出循环,会不确定left和right的值指向的值是否大于pivot，从而>导致交换后产生不必要的错误(当然也可以交换 (right - 1)的值，和上个方法一个思路)

继续循环: right-- 后right = 1,left++ 后left = 3
接着交换pivot 和 right的值swap(0,1)
得到一轮快排后的序列
3 4 7 5 6

代码实现

C++代码实现

#include <iostream>
#include <vector>
using namespace std;

int quick_method_1(vector<int> &v,int beg,int end){
    int pivot = v[beg];
    int index = beg + 1;
    for(int i = index;i <= end;++i){
        if(v[i] <= pivot){
            swap(v[i],v[index++]);
        }
    }
    swap(v[beg],v[index-1]);
    return index - 1;
}
int quick_method_2(vector<int> &v,int beg,int end){
    int pivot = v[beg];
    int left = beg + 1;
    int right = end;
    while(left <= right){
        if(v[left] < pivot) left++;
        else if(v[right] > pivot) right--;
        else if(v[left] >= pivot && v[right] <= pivot){
            swap(v[left++],v[right--]);
        }
    }
    swap(v[beg],v[right]);
    return right;
}
void quick_sort(vector<int> &v,int beg,int end){
    if(beg < end){
        int pivot = quick_method_1(v,beg,end);
        quick_sort(v,beg,pivot-1);
        quick_sort(v,pivot+1,end);
    }
};
int main()
{
    vector<int> v;
    v.push_back(5);
    v.push_back(2);
    v.push_back(9);
    v.push_back(4);
    quick_sort(v,0,3);
    for(int i = 0;i < 4;i++){
        cout << "v[" << i << "] = " << v[i] << endl;
    }
    return 0;
}

Python代码实现

def quick_method_1(seq,beg,end):
    pivot = seq[beg]    # 枢轴
    index = beg + 1
    for i in range(beg+1,end+1):    # 剩余序列的起始位置
        if(seq[i] <= pivot):
            seq[i],seq[index] = seq[index],seq[i]
            index += 1  # Python中没有++和--
    seq[beg],seq[index-1] = seq[index-1],seq[beg]
    return index - 1
def quick_method_2(seq,beg,end):
    pivot  = seq[beg]
    left = beg + 1  # 左索引
    right = end # 右索引
    while(left <= right):   # 注意等于
        if(seq[left] < pivot):
            left += 1
        elif(seq[right] > pivot):
            right -= 1
        elif(seq[left] >= pivot and seq[right] <= pivot):
            seq[left],seq[right] = seq[right],seq[left]
            left += 1
            right -= 1
    seq[beg],seq[right] = seq[right],seq[beg]
    return right
def quick_sort(seq,beg,end):
    if(beg < end):
        # 方法一
        # pivot = quick_method_1(seq,beg,end)
        # 方法二
        pivot = quick_method_2(seq,beg,end) 
        quick_sort(seq,beg,pivot-1) # 快排枢轴左边序列
        quick_sort(seq,pivot+1,end) # 快排枢轴右边序列
if __name__ == "__main__":
    seq = [4,44,58,63,11,34,75,5,30,6]
    quick_sort(seq,0,9)
    print(seq)