[C++知识库]快速排序 C++实现

快速排序有多种实现方法:

下面我就介绍一下hoare法
1.hoare法
就是定义必须先找到一个基准值，一般我们会选择第一个元素为基准值。
再定义两个指针begin，end，一个指向第一个位置，一个指向第二个位置。

然后先从后向前找第一个小于基准值5的元素，即上图中的3
然后再从前往后找第一个大于基准值5的元素，即上图中的8

然后将他们两个进行交换就得到了如下的排列方式

这时候继续上面的步骤先从后向前找小于基准值的元素，但是前提是begin必须<end;
当begin与end相遇时就将基准值与begin进行交换
交换之后就会变为下图

这个时候我们就能发现在我们的基准值与begin交换后，基准值5的左边全部都小于基准值，右边全部都大于基准值。
然后就是将这个数组按照基准值为中心，在划分成两个区间

然后再分别对左右两个区间按照上面的方法进行排列，最后当每个区间都等于一个元素时，就排好序了。

从上面我们可以发现，每一次快排都会确定区间中基准值元素的位置。

代码实现：

//快速排序
int partion4(vector<int>& arr, int begin, int end)
{
    //haore法
    int num = arr[begin];
    int start = begin;
    while (begin < end)
    {
        while (begin < end && arr[end] >= num)
            end--;
        while (begin < end && arr[begin] <= num)
            begin++;
        if (begin < end)
            swap(arr[begin], arr[end]);
    }
    swap(arr[start], arr[begin]);
    return begin;
}
int partion3(vector<int>& arr, int begin,int end) {
    //挖坑法
    int num = arr[begin];
    
    while (begin < end)
    { 
        while (begin < end && arr[end] >= num)
        {
            end--;  
        } 
        arr[begin] = arr[end];
        while (begin < end && arr[begin] <= num)
        {
            begin++;
        } 
        arr[end] = arr[begin];
    }
    arr[begin] = num;
    return begin;
}
//递归快排
void quicksort(vector<int>& arr, int begin,int end)
{
    if (begin >= end)
        return;
    int div = partion4(arr,begin, end);
    quicksort(arr, begin,div - 1);
    quicksort(arr, div + 1, end);
    
}
//非递归快速排序
void quicksort1(vector<int>& arr, int begin, int end)
{
    stack<int>st;
    st.push(end);
    st.push(begin);
    while (!st.empty())
    {
        int left = st.top();
        st.pop();
        int right = st.top();
        st.pop();
        int div = partion4(arr, left, right);
        if (div - 1 > left)
        {
            st.push(div - 1);
            st.push(begin);
        }
        if (div + 1 < right)
        {
            st.push(end);
            st.push(div + 1);
        }



    }
}