（九）快速排序随機化版本

快速排序随機化版本

1、描述

       采用一種稱為随機抽樣（random sampling）的随機化技術，使得分析更加簡單。與始終采用A[r]作為主元的方法不同，随機抽樣是從子數組A[p…r]中随機選擇一個元素作為主元。首先将A[r]與從A[p…r]中随機選出的一個元素交換。通過對序列p,…,r的随機抽樣，可以保證主元元素x=A[r]是等機率地從子數組的r-p+1個元素中選取的。

PARTITION(A,p,r)
1	x=A[r]
2	i=p-1
3	for j=p to r-1
4	  if A[j]≤x
5	    i=i+1
6	    Exchange A[i] with A[j]
7	Exchange A[i+1] with A[r]
8	Return i+1
           

RANDOMIZED-PARTITION(A,p,r)
1	i=RADOM(p,r)
2	exchange A[r] with A[i]
3	return PARTITION(A,p,r)
           

RANDOMIZED-QUICKSORT(A,p,r)
1	if p<r
2	  q= RANDOMIZED-PARTITION(A,p,r)
3	  RANDOMIZED-QUICKSORT(A,p,q-1)
4	  RANDOMIZED-QUICKSORT(A,q+1,r)
           

2、具體實作

/*快速排序随機化版本*/
#include <iostream>
#include <time.h>
using namespace std;

//列印數組
void PrintRandomizedQuickSort(int *arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

//交換
void Swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

//劃分
int Partition(int *arr, int p, int r)
{
	int i, x;
	x = arr[r];
	i = p - 1;
	for (int j = p; j < r; j++)
	{
		if (arr[j] <= x)
		{
			i++;
			Swap(&arr[i], &arr[j]);
		}
	}
	Swap(&arr[i + 1], &arr[r]);
	return i+1;
}

//随機分治思想劃分
int RandomizedPartition(int *arr, int p, int r)
{
	int i;
	srand((unsigned)time(NULL));
	i = rand() % (r - p + 1) + p;
	Swap(&arr[r], &arr[i]);
	return Partition(arr, p, r);
}

//快速排序随機化版本
void RandomizedQuickSort(int *arr, int p, int r)
{
	int q;
	if (p < r)
	{
		q = RandomizedPartition(arr, p, r);
		RandomizedQuickSort(arr, p, q - 1);
		RandomizedQuickSort(arr, q + 1, r);
	}
}
int main()
{
	int len = 0;
	int array[] = { 3, 2, 9, 0, 7, 5, 4, 8, 6, 1 };

	//數組長度
	len = sizeof(array) / sizeof(int);
	//快排前的順序
	cout << "Before Randomized Quick Sort array:" << endl;
	PrintRandomizedQuickSort(array, len);
	//快速排序随機化版本
	RandomizedQuickSort(array, 0, len - 1);
	//快排後的順序
	cout << "After Randomized Quick Sort array:" << endl;
	PrintRandomizedQuickSort(array, len);

	system("pause");
	return 0;
}