/*快速排序(分治法)原理：是對冒泡排序的一種改進，基本思想是通過一趟排序以待排第一個數據(或最后一個數據)為支點，將待排數據分割成獨立的兩部分，其中一部分數據均比另一部分數據小，則可分別對這兩部分數據繼續進行排序，以達到整個序列有序。時間復雜度：平均：O（nlogn）,最壞：O（n^2）,空間復雜度：O(logn)*/#include <iostream>using namespace std;int partition(int*L, int low, int high){	int temp = L[low];//以第一個數據為支點	while (low < high)//完成一趟排序	{		while (low<high&&L[high] >= temp)			--high;		L[low] = L[high];//比支點小的移到低端		while (low < high && L[low] <= temp)			++low;		L[high] = L[low];//比支點大的移到高端	}//終止循環之后low和high一定相等	 //int temp=L[high];//以最后一個數據為支點	 //while (low < high)//完成一趟排序	 //{	 //	while(low<high&&L[low]<=temp)//從左往右移動，比支點小就不交換	 //		++low;	 //	L[high]=L[low];	 //	while(low<high&&L[high]>=temp)	 //		--high;	 //	L[low]=L[high];	 //}	L[low] = temp;//支點	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則停止輸入數組元素	{		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])//找到第一個開始重復的數字的位置		{			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;}