分冶法之快速排序

快速排序

快速排序是一种基于分冶思想的高效排序算法，按照元素的值对它们进行划分，对数组A[0~n],经过一次划分后
A[0_{s-1]均小于A[s],A[s+1}n]均大于A[s]
经过一次划分后，A[s]已经位于它在有序数组中的最终位置了，在对A[0_s-1]和A[s+1n]进行递归排序，最终得到有序数组，在快速排序中，主要工作在划分阶段(在合并排序中主要是合并子问题的解).

QuickSort(A[l~r])
//对子数组排序
//输入：数组A[0~n]的一个子序列A[l~r]，0<=l<=r<=n
//输出：非降序排列的子数组A[l~r];

if l<r
    s=Partition(A[l~r])
    QuickSort(l~s-1)
    QuickSort(s+1~r)

霍尔划分

HoarePartition(A[l~r])
//以第一个元素为中轴，将子数组划分
//输入：数组A[0~n]的一个子序列A[l~r]，0<=l<=r<=n
//输出：A[l~r]的划分，返回分裂点位置

i=l+1
j=r
while(i<=j)
    while(A[i]<A[l]&&i<=r)
        i++
    while(A[j]>A[l])
        j--

    swap(A[i],A[j])
swap(A[i],A[j]);//弥补1多交换的一次
swap(A[l],A[j]);
return j

霍尔划分将数组依据第一个元素的值p划分为两部分，小于p和大于p，并返回中轴位置s
以第一个元素作为中轴(p=A[l])，从数组的两端同时开始扫描，从左到右的扫描从第二个元素(i=l+1)开始，遇到大于等于p的元素停止；从右到左的元素从最后一个元素(j=r)开始,遇到小于等于p的元素停止这里两侧都是开区间，会有以下三种情况

1. i<j
   对于这种情况，只要交换A[i],A[j],然后继续扫描

i<j

2. i==j
   对于这种情况 s=i=j,扫描结束，数组已经被划分为两部分

   
   快速排序 (2).png

3. i>j
   对于这种情况只需要交换A[l]和A[j],s=j

   
   i>j

   2、3结合，当i>=j时，交换A[l]和A[j],s=j。

Lomuto划分

Lomuto将数组划分为<p,>=p和未知区域(刚开始是前两个都为空)，初始令s=l,表示<p的区域。

1. 从i=l+1开始循环，如果A[i]<p,s自增后A[s]与A[i]交换。
2. 循环结束后再交换A[s]和A[l]并返回s作为中轴位置。此时A[l_{s-1]为<p，A[s+1}r]
   为>=p

LomutoPartition(A[l~r])
//以第一个元素为中轴对子数组进行划分
//输入：数组A[0~n]的一个子序列A[l~r]，0<=l<=r<=n
//输出：A[l~r]的划分和中轴位置
s=l;
p=A[l];
for(i=l+1;i<=r;i++)
    if(A[i]<p)
        s++
        swap(A[i],A[s])
swap(A[l],A[s])
return s

code

#include <iostream>
using namespace std;
//加入模板后至少在int float double有效
template<typename T> 
void QuickSort(T A[], int l,int h);
template <typename T>
int LomutoPartition(T A[], int l,int h);
template <typename T>
int HoarePartation(T A[], int l,int h);



int main()
{
    int nArr[] = { 1,4,3,6,2,7,9 };
    QuickSort(nArr, 0, 7);
    for (int i = 0; i < 7; i++)
        cout << nArr[i] << "\t";
    cout << endl;
    system("pause");
    return 0;
}

template<typename T>
void QuickSort(T A[], int l, int h)
{
    if (h-l>1 )
    {
        int s = LomutoPartition(A, l, h);
        QuickSort(A, l, s);
        QuickSort(A,s + 1, h);
    }
}

template<typename T>
int LomutoPartition(T A[], int l, int h)
{
    T p = A[l];
    int s = l;
    for (int i = l + 1; i < h; i++)
    {
        if (A[i] < p)
        {
            s++;
            swap(A[i], A[s]);
        }
    }
    swap(A[s], A[l]);
    return s;
}

template<typename T>
int HoarePartation(T A[], int l, int h)
{
    int i = l + 1;
    int j = h - 1;
    T p = A[l];
    while (i <= j)
    {
        while (A[i] < p)
            i++;
        while (A[j] > p)
            j--;
        swap(A[i], A[j]);
    }
    swap(A[i], A[j]);
    swap(A[l], A[j]);
    return j;
}