//快速排序
void Swap(int &a, int &b)
{
//a ^= b;
//b ^= a;
//a ^= b;
int temp;
temp = a;
a= b;
b = temp;
}
int Median3(int a[], int Left, int Right)
{
int Center = (Left+Right)/2;
//将左中右三个值排序
if(a[Left] > a[Center])
{
Swap(a[Left], a[Center]);
}
if(a[Left] > a[Right])
{
Swap(a[Left], a[Right]);
}
if(a[Center] > a[Right])
{
Swap(a[Center], a[Right]);
}
//将中值放在倒数第二个位置并作为枢纽元返回
Swap(a[Center], a[Right-1]);
return a[Right-1];
}
void InsertionSort(int a[], int n)
{
int temp ;
for(int i = 1; i < n; ++i)
{
int j;
temp = a[i];
for(j = i; j >0 && temp < a[j-1]; --j) //a[j]前的序列都是排好序的,在找到那个比a[j]小的值前,遍历过的值都向后挪1位
{
a[j] = a[j-1];
}
a[j] = temp;
}
}
void quickSort(int a[], int Left, int Right)
{
int i, j, Pivot;
if(Left +3 <= Right) //当元素个数较少时,使用插入排序比快速排序要快,
{
Pivot = Median3(a, Left, Right);
/* int m = a[0];
int n = a[7];*/
i = Left;
j = Right-1;
for(;;) //找到a[i]大于枢纽元的位置和a[j]小于枢纽元的位置并交换两个位置,一直进行直到i大于j退出
{
while(a[++i] < Pivot) {}
while(a[--j] > Pivot) {}
if(i < j)
Swap(a[i], a[j]);
else
break;
}
//退出for循环时,a[i]的值大于枢纽元并且位置在a[j]左边,故a[i]与枢纽元交换, 则此时枢纽元左边的都是较小值,右边都是较大值.
Swap(a[i], a[Right-1]);
quickSort(a, Left, i-1);
quickSort(a, i+1, Right);
}
else
{
InsertionSort(a+Left, Right-Left+1);
}
}
void QuickSort(int a[], int n)
{
quickSort(a, 0, n-1);
}
优化的快速排序
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 本文有七千字，阅读大约需要占用你10分钟时间。 好吧。。随便写的，我也不知道会花多久看完。因为写的比较烂，而且只是...
