一个快速排序的实现 An Algorithm for QuickSort

参考：Datastructures and Algorithm Analysis in C

Mark Allen Weiss

一个快速排序的实现。

快排的基本思路是

1. 寻找枢纽(pivot)

书上讨论了各种方案，生成有随机数，寻找首元素等等；并分析了优劣。由于随机数的开销很大， 首元素在最坏的情况下时间复杂度高达O(n^2)。最后确定了使用3分法

也就是left， center ， right   其中center = (left + right)/2

然后将中值作为pivot 且把中值和right - 1替换隐藏中值。

代码实现如下：

// Return median of Left, center and right
// order these and hide the pivot
int median3(int *a, int left, int right) {int center = (left + right) / 2;if(a[left] > a[center])swap(a, left, center);if(a[left] > a[right])swap(a, left, right);if(a[center] > a [right])swap(a, center, right);// Invariant: a[left] <= a[center] <= a[right]swap(a, center, right - 1); // hide pivotreturn a[right - 1];
}

2.接着是主要的核心代码，递归方式快排。

分别区两个下标i, j   其中i = left,   j = right - 1

首先从i开始递增寻找出第一个大于pivot的元素。

接着从j开始递减寻找出第一个小于pivot的元素。

若i < j则交换两个元素的值。

继续循环，直到i >= j 

作者提出了优化（在Algs4中有非常详细的讨论，在元素数量较小时InserttionSort由于递归带来的开销性能将高于快排）

最后完的实现代码如下：

#define CUTOFF  (1)
void qsort(int *a, int left, int right) {int i , j;int pivot;if(left + CUTOFF <= right) {pivot = median3(a, left, right);i = left; j = right - 1;while(i < j) {while(a[++i] < pivot && i < j);while(a[--j] > pivot && i < j);if(i < j)swap(a, i, j);}// restore pivotswap(a, i, right - 1);qsort(a, left, i - 1);qsort(a, i + 1, right);} else {// do an insertion sort on the subarray.}
}

最后只需要将递归函数进行一层封装即可：

代码实现如下：

void quicksort(int *a, int nCount) {qsort(a, 0, nCount - 1);
}

以上代码中用到的一个辅助函数：

void swap(int *v, int i, int j) {if(i == j)return;int temp;temp = v[i];v[i] = v[j];v[j] = temp;
}

如果不使用median。最坏情况下快速排序的一个例子。

#define PIVOT_OFFSET (0)int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
#define ARRAY_SIZE	10void printfArray() {for (int i = 0; i < _countof(array); i++)printf("%d ", array[i]);printf("\n");
}void swap(int a[], int i, int j) {if (i == j)return;int temp = a[i];a[i] = a[j];a[j] = temp;printf("swap %d %d\n", a[i], a[j]);
}int partition(int a[], int begin, int end){int pivot = begin + PIVOT_OFFSET;swap(a, pivot, end);pivot = end;int k = a[pivot];	// the value of the pivot.int i = begin;int j = end - 1;while (i < j) {while (a[i] < k && i < j)i++;while (a[j] > k && i < j)j--;if (i < j)swap(a, i, j);}swap(a, i, pivot);return i;
}void qsort(int a[], int begin, int end) {if (begin >= end)return;int pivot = partition(a, begin, end);// record the times of calling of the sub routine the qsort.static int nQsort = 0;	printf("The %d:", ++nQsort);printfArray();qsort(a, begin, pivot - 1);qsort(a, pivot + 1, end);
}void QuickSort(int a[], int nSize) {qsort(a, 0, nSize - 1);
}int _tmain(int argc, TCHAR* argv[], TCHAR * env[])
{QuickSort(array, _countof(array));return 0;
}