分治算法二（快速排序）

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的政策，通常稱其為分治法(Divide-and-ConquerMethod)。

該方法的基本思想是：

1．先從數列中取出一個數作為基準數。（選擇方式可以不同）

2．分區過程，将比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。

3．再對左右區間重複第二步，直到各區間隻有一個數。

/* file: quick_sort							*/
/* 1、find the pivot of the Array			*/
/* 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;
}

/*=====================================
  QuickSort:Sort the Array using QuickSort
			algorithm.By partition an Array
			into two subarrays and then 
			conquer the two subarrays.
=======================================*/
void QuickSort(int* Array, int start,int end)
{
	int pivot;
	if(start < end)
	{
		//find the pivot of the array
		pivot = Partition(Array, start, end);
		//conquer the left subarray
		QuickSort(Array, start, pivot - 1);
		//conquer the right subarray
		QuickSort(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
		QuickSort(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");
	}
}