/*快速排序(分治法)原理：是對(duì)冒泡排序的一種改進(jìn)，基本思想是通過一趟排序以待排第一個(gè)數(shù)據(jù)(或最后一個(gè)數(shù)據(jù))為支點(diǎn)，將待排數(shù)據(jù)分割成獨(dú)立的兩部分，其中一部分?jǐn)?shù)據(jù)均比另一部分?jǐn)?shù)據(jù)小，則可分別對(duì)這兩部分?jǐn)?shù)據(jù)繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。時(shí)間復(fù)雜度：平均：O（nlogn）,最壞：O（n^2）,空間復(fù)雜度：O(logn)*/#include <iostream>using namespace std;int partition(int*L, int low, int high){	int temp = L[low];//以第一個(gè)數(shù)據(jù)為支點(diǎn)	while (low < high)//完成一趟排序	{		while (low<high&&L[high] >= temp)			--high;		L[low] = L[high];//比支點(diǎn)小的移到低端		while (low < high && L[low] <= temp)			++low;		L[high] = L[low];//比支點(diǎn)大的移到高端	}//終止循環(huán)之后low和high一定相等	 //int temp=L[high];//以最后一個(gè)數(shù)據(jù)為支點(diǎn)	 //while (low < high)//完成一趟排序	 //{	 //	while(low<high&&L[low]<=temp)//從左往右移動(dòng)，比支點(diǎn)小就不交換	 //		++low;	 //	L[high]=L[low];	 //	while(low<high&&L[high]>=temp)	 //		--high;	 //	L[low]=L[high];	 //}	L[low] = temp;//支點(diǎn)	return low;}void quik_sort(int*L, int low, int high){	if (low < high)	{		int pl = partition(L, low, high);		quik_sort(L, low, pl - 1);		quik_sort(L, pl + 1, high);	}}int main(){	int narry[100], addr[100];	int sum = 1, t;	cout << "Input number:" << endl;	cin >> t;	while (t != -1)//輸入-1則停止輸入數(shù)組元素	{		narry[sum] = t;		addr[sum - 1] = t;		sum++;		cin >> t;	}	sum -= 1;	quik_sort(narry, 1, sum);	for (int i = 1; i <= sum;i++)		cout << narry[i] << '/t';	cout << endl;	int k;	cout << "Please input place you want:" << endl;	cin >> k;	int aa = 1;	int kk = 0;	for (;;)	{		if (aa == k)			break;		if (narry[kk] != narry[kk + 1])//找到第一個(gè)開始重復(fù)的數(shù)字的位置		{			aa += 1;			kk++;		}	}	cout << "The NO." << k << "number is:" << narry[sum - kk] << endl;	cout << "And it's place is:";	for (int i = 0;i < sum;i++)	{		if (addr[i] == narry[sum - kk])			cout << i << '/t';	}	return 0;}