分治算法三（随機化快速排序）

1、快速排序對于輸入資料的順序比較敏感。主要在于每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分将得到最壞的結果。這個時候，時間複雜度将會退化到O(n^2)。

2、一種比較常見的優化方法是随機化算法，即随機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入資料，而是取決于随機函數随機數的選取。實際上，随機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。是以随機化快速排序可以對于絕大多數輸入資料達到O(n*logn）的期望時間複雜度。

3、随機化快速排序的唯一缺點在于，一旦輸入資料中有很多的相同資料，随機化的效果将直接減弱。對于極限情況，即對于n個相同的數排序，随機化快速排序的時間複雜度将毫無疑問的降低到O(n^2）。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。

/* file: random_quick_sort					*/
/* 1、find the pivot of the Array by using 
	  random algorithm						*/
/* 2、divide the Array into two subarrays	*/
/* 3、conquer the two subarrays				*/
/* 4、the Array is sorted,when conquer ended*/

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

/*=====================================
  swap:swap two numbers a and b
=======================================*/
inline void swap(int* a,int* b)
{
	int tmp;
	tmp  = *a;
	*a   = *b;
	*b   = tmp;
}
/*=====================================
  Partition:Partition the Array from start
			to end into two subarrays.
			Return the pivot of the element
			Array[start]
=======================================*/
int Partition(int* Array, int start, int end)
{
	//choose Array[start] as the pivot element 
	//divide the array into two subarrays.
	//left of the Array's elements <= Array[start]
	//right of the array's elements > Array[start]
	int pivot = start,j;
	for(j = start + 1; j <= end; j++)
		if(Array[j] <= Array[start])
		{
			pivot++;
			swap(&Array[pivot], &Array[j]);
		}
	swap(&Array[start], &Array[pivot]);
	return pivot;
}
/*=====================================
  RandomPartition:using random algorithm.partition the
				  Array into two subarrays.Return the 
				  pivot of the element Array[start] which
				  is already swaped
=======================================*/
int RandomPartition(int* Array, int start, int end)
{
	//generate the random index of the pivot
	int random_index = start + rand() % (end - start + 1);
	//swap the pivot with the random_index element
	swap(&Array[start], &Array[random_index]);
	//now random_index element act as the start element
	return Partition(Array,start,end);
}

/*=====================================
  RandomQuickSort:Sort the Array using QuickSort
				  algorithm.By partition an Array
				  into two subarrays and then 
				  conquer the two subarrays.
=======================================*/
void RandomQuickSort(int* Array, int start,int end)
{
	int pivot;
	if(start < end)
	{
		//find the pivot of the array
		pivot = RandomPartition(Array, start, end);
		//conquer the left subarray
		RandomQuickSort(Array, start, pivot - 1);
		//conquer the right subarray
		RandomQuickSort(Array, pivot + 1, end);
	}
}

void main()
{
	int n,i;

	printf("Please input the length of Array<0:exit>:\n");
	while(scanf("%d",&n),n)
	{	
		//create an arrays of length n
		int* Array = new int[n];
		//get the input integers
		printf("Please input %d integers:\n",n);
		for(i = 0; i < n; i++)
			scanf("%d",&Array[i]);
		//use QuickSort algorithom
		RandomQuickSort(Array,0,n-1);
		//print the sorted array
		printf("Sorted Array:\n");
		for(i = 0; i < n; i++)
			printf("%d ",Array[i]);
		system("pause");
		system("cls");
		//delete the array
		delete[] Array;
		printf("Please input the length of Array<0:exit>:\n");
	}
}