最近在学习排序，学到快速排序的时候，发现快排的优化貌似很多

尝试了一下书上的三数中值分割和小数组的方法，发现效果真是好，但是我又从网上看到了另外两种方法，一种是九数中值(Median-of-nine)和splitend，却发现一些很奇怪的问题
（http://www.blogjava.net/killme2008/archive/2010/09/08/quicksort_optimized.html这是我参考的地方）

应该说，理论上九数中值的方法应该比三数中值要快（数字全是随机的情况下，前者应该能更好的划分中值）但是我排序一千万数据的时候前者要比后者快50ms以内，但是一个亿数据的时候前者却比后者慢200ms左右（可能存在误差，但不至于每次都是这样吧？），速率上快不了多少，至于参考量的问题我也是选了很久，但是还是存在这个差距

另外splitend应该是最快的，但是我自己写了一下，发现事实上却慢很多，稍微分析了一下应该是因为考虑相等元素的时候splitend是一直往后搜索的，当元素大量重复的时候会退化为0(N^2)，还有交换的时候换了两次，可是这个博客说的那个，Arraysort会很快，但是事实上却慢了很多，我看了一下，好像和我写的没什么区别呀，难道是我理解问题？

好了不多说，贴代码：

//split_end.cpp
#include "quick_sort_plug.h"

int main()//快速排序的几种优化
{
	ElementType *A = (ElementType *)malloc(sizeof(ElementType)*MAX);
	ElementType *B = (ElementType *)malloc(sizeof(ElementType)*MAX);
	int i = 1;
	time_t c1, c2;
	for (A[0] = 1; i < MAX; i++)
	{
		srand((unsigned)(time(NULL)*i*A[i-1]));
		A[i] = rand();
	}
	CopyArray(A, B);
	CopyArray(A, C);

	puts("Quicksort_median_of_nine");
	c1 = clock();quicksort_median_of_nine(B, 0, MAX - 1);c2 = clock();
	printf("%ldms\n\n\n", c2 - c1);

	puts("Quicksort_normal");
	c1 = clock(); quicksort(A, 0, MAX - 1); c2 = clock();
	printf("%ldms\n\n\n", c2 - c1);

	free(A); free(B); free(C); free(tmp);
	system("pause"); return 0;
}

void quicksort_median_of_nine(ElementType *A, Position left, Position right)
{
	if (left >= right) return;//判断递归结束的标志

	int len = right - left;
	ElementType pivot;
	Position i, j, min = (left + right) / 2;
	if (len < CUTOFF) { Insertionsort(A, left, len + 1); return; } //如果len小于CUTOFF则为小数组，采用插入排序,记得return

	if (len > MCUTOFF)//大数组，median-of-nine
	{
		Position ln, rn;
		ln = SelectPivot_s(A, left, left + OFFSET, left + OFFSET * 2);
		rn = SelectPivot_s(A, right - OFFSET * 2, right - OFFSET, right);

		min = SelectPivot_s(A, ln, min, rn);
	}
	pivot = A[SelectPivot(A, left, min, right)];

	for (i = left, j = right;;)
	{
		while (A[++i] < pivot){};
		while (A[--j] > pivot){};
		if (i < j) swap(&A[i], &A[j]);
		else break;
	}
	swap(&A[i], &A[right]);

	quicksort_median_of_nine(A, left, i - 1);
	quicksort_median_of_nine(A, i + 1, right);
}

void quicksort(ElementType *A, Position left, Position right)
{
	if (right <= left)return;
	Position i, j;
	ElementType pivot;
	if (right - left > CUTOFF)
	{
		pivot = A[SelectPivot(A, left, (left + right) /2, right)];

		for (i = left, j = right;;)
		{
			while (A[++i] < pivot){};
			while (A[--j] > pivot){};
			if (i < j) swap(&A[i], &A[j]);
			else break;
		}
		swap(&A[i], &A[right]);

		quicksort(A, left, i - 1);
		quicksort(A, i + 1, right);
	}
	else Insertionsort(A, left, right - left + 1);//转插入排序
}

void Insertionsort(ElementType *A, Position left,int len)
{
	ElementType tmp;
	int i = left, j, sum = i + len;
	for (; i < sum; i++)
	{
		tmp = A[i];
		for (j = i; j > 0 && A[j - 1] > tmp; A[j] = A[j - 1], j--);
		A[j] = tmp;
	}
}

Position SelectPivot(ElementType *A, Position a, Position b, Position c)//三数取中值函数,我们要排序成从小到大的顺序,隐藏枢纽元
{
	if (A[a] > A[b]) swap(&A[a], &A[b]);
	if (A[a] > A[c]) swap(&A[a], &A[c]);
	if (A[b] > A[c]) swap(&A[b], &A[c]);
	swap(&A[b], &A[c]);//交换中值点和末尾点(隐藏尾结点)
	return c;
}

Position SelectPivot_s(ElementType *A, Position a, Position b, Position c)//三数取中值函数,我们要排序成从小到大的顺序,不隐藏结点
{
	return A[a] < A[b] ? (A[b] < A[c] ? b : A[a] < A[c] ? c : a): A[b] > A[c] ? b : A[a] > A[c] ? c : a;
}
void swap(ElementType *A, ElementType *B)
{
	ElementType tmp = *A;
	*A = *B; *B = tmp;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElementType;
typedef int Position;

#define MAX 100000000
#define CUTOFF 500
#define MCUTOFF 35000
#define OFFSET 4000

void swap(ElementType *, ElementType *);
void quicksort_median_of_nine(ElementType *, Position, Position);
void Insertionsort(ElementType *, Position,int);
Position SelectPivot(ElementType *, Position, Position, Position);
Position SelectPivot_s(ElementType *A, Position a, Position b, Position c);
void CopyArray(ElementType *, ElementType *);