排序(5)

繼shell發明了shell排序過後呢，各位計算機界的大牛們又開始不爽了，為什麼他能發明，我就不能發明呢。於是又有個哥們蹦出來了。哎。。。那麼多排序，就木有一個排序是中國人發明的。順便吐槽一下，一百年的天朝的歷史書裡還在吹，祖沖之第一個發現圓周率，領先世界一千多年......

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
步驟為：

1，從數列中挑出一個元素，稱為 "基准"，
2，重新排序數列，所有元素比基准值小的擺放在基准前面，所有元素比基准值大的擺在基准的後面（相同的數可以到任一邊）。在這個分區退出之後，該基准就處於數列的中間位置。這個稱為分區操作。
3，遞歸地把小於基准值元素的子數列和大於基准值元素的子數列排序。
4，遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代中，它至少會把一個元素擺到它最後的位置去。

①先假定序列的第一個元素為標志位，從第一位到最後一直與標志位進行比較，比標志位小的全部移到標志位的左邊，比標志位大的全部移到標志位的右邊

②對標志位左邊的進行步驟①操作，右邊亦是，形成新的兩個標志位，依次遞歸下去

源代碼：

#include "stdafx.h"
#include 

void swap(int arr[],int i, int j) //交換
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}


int getPoint(int arr[],int low ,int  high)
{
	int res = arr[low];   //第一次假定第一個元素即為標志點
	while (low < high)
	{
		while ((low < high) && (arr[high] >= res))
		{
			high--;
		}
		swap(arr,low,high);
		
		while ((low < high) && (arr[low] <= res))
		{
			low++;
		}
		swap(arr,low,high);
	}

	return low;
}

void QSort(int arr[],int low ,int high)
{
	if (low < high)
	{
		int lowIndex = getPoint(arr, low, high);

		QSort(arr, low,lowIndex-1);
		QSort(arr, lowIndex+1,high);
	}
}

void Quick_Sort(int arr[], int low, int high)
{
	QSort(arr, low, high-1);
}


int main(void)
{
	int arr[10];
	
	for ( int i=0; i<10; i++)  //初始化數據
	{
		arr[i] = rand()%33;  //隨機生成數據
	}
	printf("Before sort:\n");  //打印排序前的數據
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}

	//開始排序
	Quick_Sort(arr,0,10);


	printf("\nAfter sort:\n"); //打印排序後的數據
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}
	system("pause");
	return 0;
}

Before sort:
8 20 31 1 29 16 27 21 1 11
After sort:
1 1 8 11 16 20 21 27 29 31 請按任意鍵繼續. . .

如有錯誤，望不吝指出。