一、快速排序

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

快排中心思想代碼演示：

// 假設按照升序對array數組中[left, right)區間中的元素進行排序
void QuickSort(int array[], int left, int right)
{
?if(right - left <= 1)
?return;
?
?// 按照基準值對array數組的 [left, right)區間中的元素進行劃分
?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);
}

代碼實現：

// 三數取中
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;
};

代碼實現：

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

? ? int key = a[left];
? ? // 保存key值以后，左邊形成第一個坑
? ? 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;
}

代碼實現：

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);//此處調用前后指針快排，也可調用其他兩種排序方法
? ? // [begin, keyi-1] keyi [keyi+1, end]
? ? QuickSort(a, begin, keyi - 1);
? ? QuickSort(a, keyi+1, end);
}

?