快速排序
快速排序是一种基于分冶思想的高效排序算法，按照元素的值对它们进行划分，对数组A[0~n],经过一次划分后
A[0s-1]均小于A[s],A[s+1n]均大于A[s]
经过一次划分后，A[s]已经位于它在有序数组中的最终位置了，在对A[0s-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的元素停止这里两侧都是开区间，会有以下三种情况
- i<j
对于这种情况，只要交换A[i],A[j],然后继续扫描
i<j
-
i==j
对于这种情况 s=i=j,扫描结束，数组已经被划分为两部分
快速排序 (2).png -
i>j
对于这种情况只需要交换A[l]和A[j],s=j
i>j2、3结合，当i>=j时，交换A[l]和A[j],s=j。
Lomuto划分
Lomuto将数组划分为<p,>=p和未知区域(刚开始是前两个都为空)，初始令s=l,表示<p的区域。
- 从i=l+1开始循环，如果A[i]<p,s自增后A[s]与A[i]交换。
- 循环结束后再交换A[s]和A[l]并返回s作为中轴位置。此时A[ls-1]为<p，A[s+1r]
为>=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;
}
