数据结构之快速排序

一、快速排序

? ? 快速排序是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);
}

?