排序算法c语言描述-快速排序随机化

墨蓝 2022-09-18 12:46 187阅读 0赞

**今天在做数据结构排序实验的时候，使用的快速排序。按理，我印象中快排是很高效的，不过，这次400w的数据，排了2659秒，有点意想不到，让我一度怀疑了算法是否写错了。**

**不过，认真分析，认真想想后， 也就释然了。**

**快排其实就是冒泡的升级版。**

**每次递归，把当前序列分成两部分，一个比枢纽元素大，一个比枢纽元素小。具体思想可以参见的之前写的一篇博客。**

**http://blog.csdn.net/hitwhylz/article/details/9968639**

**至于这次实验的低效，我看了下所给的数据，发现序列基本有序，从20-------3999997**

**排列的很有规则，就移动了些许位置， 但是保持递增趋势。**

**这样的序列使用常规快排，那就体现不出快排的优势了。 因为每次选取的时候都是 采用子序列的第一个元素为枢纽元素 int pivot = array\[low\];**

**这样导致每次比较，分出的序列差别都很大，以至于需要递归很多次。**

**为解决这问题，采用了快速排序随机化方法，即每次确定的枢纽元素都是随机找出的。**

**一般来说随机选取枢纽元这种策略非常安全，除非随机数生成器有问题（这不像你所想象的那么罕见），因为随机的枢纽元不可能总在接连不断地产生劣质的分割。**

**下面具体看代码了。**

#include "stdio.h"
    #include "math.h"
    #include "stdlib.h"
    
    int num = 10;
    
    void swap(int *a,int *b)
    {
        int tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    void PrintArray(int arr[])
    {
        int i;
    	for(i=0; i < num; ++i)
    	{
    	    printf("%d ", arr[i]);
    	}
    }
    
    int Partition(int *arr, int beg, int end)
    {
        int j;
    	int sentinel = arr[end];
    	int i = beg-1;
    	for(j=beg; j <= end-1; ++j)
    	{
    		if(arr[j] <= sentinel)
    		{
    			i++;
    			swap(&arr[i], &arr[j]);
    		}
    	}
    	swap(&arr[i+1], &arr[end]);
    
    	printf("\n排序过程:");
    	PrintArray(arr);
    	return i+1;
    }
    
    int RandomPartition(int *arr, int beg, int end)
    {
    	int i = beg + rand() % (end-beg+1);
    	swap(&arr[i], &arr[end]);
    	return Partition(arr, beg, end);
    }
    
    void RandomQuickSort(int *arr, int beg, int end)
    {
    	if(beg < end)
    	{
    		int pivot = RandomPartition(arr, beg, end);
    		printf("\n随机选择 arr[%d](%d)", pivot, arr[pivot]);
    		RandomQuickSort(arr, beg, pivot-1);
    		printf("\n随机选择 arr[%d](%d)", pivot, arr[pivot]);
    		RandomQuickSort(arr, pivot+1, end);
    	}
    }
    
    int main()
    {
    	int i;
    	int arr[10];
    
    	srand(time(0));
        for(i=0; i < 10; i++)
        {
            arr[i] = rand()%100+1;
            //printf("%d ", rand()%100+1);
        }
    
        printf("初始数组:");
        PrintArray(arr);
    
    	RandomQuickSort(arr, 0, num-1);
    
    	printf("\n最后结果:");
    	PrintArray(arr);
    
    	return 0;
    }

**学习的路上，与君共勉。**