一、快速排序

? ? 快速排序是Hoare于1962年提出的一種二叉樹(shù)結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。

快排中心思想代碼演示：

// 假設(shè)按照升序?qū)rray數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void QuickSort(int array[], int left, int right)
{
?if(right - left <= 1)
?return;
?
?// 按照基準(zhǔn)值對(duì)array數(shù)組的 [left, right)區(qū)間中的元素進(jìn)行劃分
?int div = partion(array, left, right);
?
?// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)
?// 遞歸排[left, div)
?QuickSort(array, left, div);
?
?// 遞歸排[div+1, right)
?QuickSort(array, div+1, right);
}

代碼實(shí)現(xiàn)：

// 三數(shù)取中
int GetMidi(int* a, int left, int right)
{
? ? int mid = (left + right) / 2;
? ? // left mid right
? ? if (a[left] < a[mid])
? ? {
? ? ? ? if (a[mid] < a[right])
? ? ? ? {
? ? ? ? ? ? return mid;
? ? ? ? }
? ? ? ? else if (a[left] > a[right]) ?// mid是最大值
? ? ? ? {
? ? ? ? ? ? return left;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? return right;
? ? ? ? }
? ? }
? ? else // a[left] > a[mid]
? ? {
? ? ? ? if (a[mid] > a[right])
? ? ? ? {
? ? ? ? ? ? return mid;
? ? ? ? }
? ? ? ? else if (a[left] < a[right]) // mid是最小
? ? ? ? {
? ? ? ? ? ? return left;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? return right;
? ? ? ? }
? ? }
}

//hoare
int PartSort1(int* a, int left, int right)
{
? ? int midi = GetMidi(a, left, right);
? ? Swap(&a[left], &a[midi]);

? ? int keyi = left;
? ? while (left < right)
? ? {
? ? ? ? // 找小
? ? ? ? while (left < right && a[right] >= a[keyi])
? ? ? ? {
? ? ? ? ? ? --right;
? ? ? ? }

? ? ? ? // 找大
? ? ? ? while (left < right && a[left] <= a[keyi])
? ? ? ? {
? ? ? ? ? ? ++left;
? ? ? ? }

? ? ? ? Swap(&a[left], &a[right]);
? ? }

? ? Swap(&a[keyi], &a[left]);
? ? return left;
};

代碼實(shí)現(xiàn)：

int PartSort2(int* a, int left, int right)
{
? ? int midi = GetMidi(a, left, right);
? ? Swap(&a[left], &a[midi]);

? ? int key = a[left];
? ? // 保存key值以后，左邊形成第一個(gè)坑
? ? int hole = left;

? ? while (left < right)
? ? {
? ? ? ? // 右邊先走，找小，填到左邊的坑，右邊形成新的坑位
? ? ? ? while (left < right && a[right] >= key)
? ? ? ? {
? ? ? ? ? ? --right;
? ? ? ? }
? ? ? ? a[hole] = a[right];
? ? ? ? hole = right;

? ? ? ? // 左邊再走，找大，填到右邊的坑，左邊形成新的坑位
? ? ? ? while (left < right && a[left] <= key)
? ? ? ? {
? ? ? ? ? ? ++left;
? ? ? ? }
? ? ? ? a[hole] = a[left];
? ? ? ? hole = left;
? ? }

? ? a[hole] = key;
? ? return hole;
}

代碼實(shí)現(xiàn)：

int PartSort3(int* a, int left, int right)
{
? ? int midi = GetMidi(a, left, right);
? ? Swap(&a[left], &a[midi]);

? ? int prev = left;
? ? int cur = prev + 1;

? ? int keyi = left;
? ? while (cur <= right)
? ? {
? ? ? ? if (a[cur] < a[keyi] && ++prev != cur)
? ? ? ? {
? ? ? ? ? ? Swap(&a[prev], &a[cur]);
? ? ? ? }

? ? ? ? ++cur;
? ? }

? ? Swap(&a[prev], &a[keyi]);
? ? return prev;
}

快速排序遞歸代碼：

void QuickSort(int* a, int begin, int end)
{
? ? if (begin >= end)
? ? ? ? return;

? ? int keyi = PartSort3(a, begin, end);//此處調(diào)用前后指針快排，也可調(diào)用其他兩種排序方法
? ? // [begin, keyi-1] keyi [keyi+1, end]
? ? QuickSort(a, begin, keyi - 1);
? ? QuickSort(a, keyi+1, end);
}

?