关于快排优化的问题

C++语言 码拜 6年前 (2015-05-11) 475次浏览 0个评论
 

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

尝试了一下书上的三数中值分割和小数组的方法,发现效果真是好,但是我又从网上看到了另外两种方法,一种是九数中值(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 *);
另外这是我的splitend代码,感觉应该是有一个错误

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 quicksort_split_end(ElementType *A, Position left, Position right)
{
	if (left >= right) return;//判断递归结束的标志

	int len = right - left;
	ElementType pivot;
	Position i, j, a, b, min = (left + right) / 2, s1, s2;
	if (len < CUTOFF) { Insertionsort(A, left, len + 1); return; } //如果len小于7则为小数组,采用插入排序,记得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)];

	a = left, b = right - 1, i = left, j = right;
	//其中a与b保留相等元素的最高/低位,c和d和快排的两个因子作用一样

	for (;;)
	{
		for (; i < j&&A[++i] <= pivot;) { if (A[i] == pivot){ swap(&A[a++], &A[i]); } }//这里为什么要加i<j因为换元素的时候是不包括相等元素的,可能会冲出限制
		for (; i < j&&A[--j] >= pivot;) { if (A[j] == pivot){ swap(&A[b--], &A[j]); } }
		//这里虽然多了一步判断,但是总体来讲能让整体数据偏向中心,影响减少
		if (i >= j)break;
		else swap(&A[i], &A[j]);
	}
	swap(&A[i], &A[right]);//最后一个值和枢纽元交换,此时j==i

	s1 = SelectMin(a - left, i - a);//i千万不要-1,不然会出现-1这种坑爹的情况
	Exchange_data(A, left, i - s1, s1);
	s2 = SelectMin(right - b - 1, b - j);//right记得-1,不包括被隐藏的枢纽元
	Exchange_data(A, j, right - 1 - s2, s2);

	quicksort_split_end(A, left, i - 1 - s1);
	quicksort_split_end(A, i + s2 + 1, right);
}
int SelectMin(int A , int B)//选择最小的数的函数
{
	return A >= B ? B : A;
}

void Exchange_data(ElementType *A, Position a, Position b, Position sum)//交换整批数据
{
	for (int i = 0; i < sum; swap(&A[a], &A[b]), i++, a++, b++);
}
因为楼主不太会用srand和rand函数,我猜。

...
unsigned long ulrand(void) {
    return (
     (((unsigned long)rand()<<24)&0xFF000000ul)
    |(((unsigned long)rand()<<12)&0x00FFF000ul)
    |(((unsigned long)rand()    )&0x00000FFFul));
}
int main()//快速排序的几种优化
{

    ElementType *A = (ElementType *)malloc(sizeof(ElementType)*MAX);
    ElementType *B = (ElementType *)malloc(sizeof(ElementType)*MAX);
    int i = 1;
    time_t c1, c2;
    srand((unsigned)time(NULL));
    for (A[0] = 1; i < MAX; i++)
    {
        A[i] = ulrand();
    }
...
额。。。我对rand和srand的认识仅限于他可以产生随机数。。。

试了一下赵老师的随机数产生法,发现我的快排的速度明显减慢了,归并的速度没有发生多大的变化

但是稍微调整下序列,貌似又回到了原来的样子,看来快排真的很依赖序列啊

现在给我的感觉就是那两个快排的优化方法差不了多少。

引用 3 楼 zhao4zhong1 的回复:

因为楼主不太会用srand和rand函数,我猜。

...
unsigned long ulrand(void) {
    return (
     (((unsigned long)rand()<<24)&0xFF000000ul)
    |(((unsigned long)rand()<<12)&0x00FFF000ul)
    |(((unsigned long)rand()    )&0x00000FFFul));
}
int main()//快速排序的几种优化
{

    ElementType *A = (ElementType *)malloc(sizeof(ElementType)*MAX);
    ElementType *B = (ElementType *)malloc(sizeof(ElementType)*MAX);
    int i = 1;
    time_t c1, c2;
    srand((unsigned)time(NULL));
    for (A[0] = 1; i < MAX; i++)
    {
        A[i] = ulrand();
    }
...

赵老师对快排有什么好的优化方法可以介绍一下吗,或者说你对随机数列的排序是怎么处理的?

80分
搜“B+树”
引用 6 楼 zhao4zhong1 的回复:

搜“B+树”

看到了,比较了下B+做索引真强。。。。

<1000个元素,冒泡排序
<100000个元素,qsort函数
<10000000个元素,放数据库中,建索引,(B+树排序)
≥10000000个元素,没用到过。
引用 8 楼 zhao4zhong1 的回复:

<1000个元素,冒泡排序
<100000个元素,qsort函数
<10000000个元素,放数据库中,建索引,(B+树排序)
≥10000000个元素,没用到过。

可是冒泡排序不是交换的次数最小是逆序个数吗,插入排序直接就是逆序个数。。直接用插入排序效果不是更好?

对了赵老师我最后再问个问题。。。其实我不懂你为什么要选用那样的随机数列。。。这样写数据会更随机一点吗?

rand函数返回值的范围是0..32767
各种排序算法动画演示http://www.webhek.com/misc/comparison-sort/
http://en.wikipedia.org/wiki/Sorting_algorithm
引用 10 楼 zhao4zhong1 的回复:

rand函数返回值的范围是0..32767

明白了,原来如此

C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src\rand.c

/***
*rand.c - random number generator
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
*       defines rand(), srand() - random number generator
*
*******************************************************************************/

#include <cruntime.h>
#include <mtdll.h>
#include <stddef.h>
#include <stdlib.h>

/***
*void srand(seed) - seed the random number generator
*
*Purpose:
*       Seeds the random number generator with the int given.  Adapted from the
*       BASIC random number generator.
*
*Entry:
*       unsigned seed - seed to seed rand # generator with
*
*Exit:
*       None.
*
*Exceptions:
*
*******************************************************************************/

void __cdecl srand (
        unsigned int seed
        )
{
        _getptd()->_holdrand = (unsigned long)seed;
}


/***
*int rand() - returns a random number
*
*Purpose:
*       returns a pseudo-random number 0 through 32767.
*
*Entry:
*       None.
*
*Exit:
*       Returns a pseudo-random number 0 through 32767.
*
*Exceptions:
*
*******************************************************************************/

int __cdecl rand (
        void
        )
{
        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );
}
顶一下吧,感觉学习了

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明关于快排优化的问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!