資料結構總結與實作：快速排序

快速排序種類有很多，但核心思想是分治法，過程大緻如下：

1. 找到第一個元素（作為基準數）的位置（通過首尾标志與基準數交換的方法）
2. 根據該基準數位置進行分塊，分成兩塊，用遞歸的思想改變首尾标志再次排序，直到分完。

代碼如下：

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
using namespace std;

void Quicksort(int *p, int a, int b)
{
	int a1 = a, b1 = b;
	while (a < b)
	{
		bool flag = false;				//注意這種标志位方法，想讓程式判斷是否進入過判斷，很常用的方法，
										//如果想讓程式判斷是否進入過循環,可以設定一個變量n在循環體内部，每次加一，最後看它為幾就是進入了幾次。

		while (!flag && a<b) {          //有時候分析不清條件的時候，就仔細想想是要兩個成立還是任意一個就可以，兩個就一定是&&，然後再考慮非不非的事情。
			if (p[a] > p[b])
			{
				flag = true;
				int temp = p[a];
				p[a] = p[b];
				p[b] = temp;
			}
			else
				b--;
		}
		flag = false;
		while (!flag && a<b) {
			if (p[a] > p[b])
			{
				flag = true;
				int temp = p[a];
				p[a] = p[b];
				p[b] = temp;
			}
			else
				a++;
		}
		if (a - 1 > a1)
			Quicksort(p, a1, a - 1);
		if (a + 1 < b1)
			Quicksort(p, a + 1, b1);
	}
}
int main()
{
	srand((int)time(0));
	int n, n1;
	cout << "輸入随機元素個數 ";
	cin >> n;
	cout << "輸入随機元素範圍 ";
	cin >> n1;
	vector<int> arr(n);

	int n2 = 1;
	for (int i = 0; i < n; i++)   //産生随機正負數
	{
		int n3 = (rand() % 2);
		for (int j = 0; j < n3; j++)  //感覺這種産生随機負數的方法很蠢，可以再想想
			n2 *= -1;
		arr[i] = (rand() * n2 % n1);
	}
	cout << endl << "随機産生的數為 " << endl;
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;

	Quicksort(&arr[0], 0, n - 1);	//第2個參數表示第1個元素下标，第3個參數表示第2個元素下标。vector本身的辨別符名雖然不是位址，但是可以通過取第一個元素位址得到首位址
	cout << endl << endl << "排序後的數為 " << endl;
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
	system("pause");

	return 0;
}