快速排序法 Quick Sort

2016-06-03

12587
0
C++

快速排序法(Quick Sort)是排序演算法的一種，是使用Divide and Conquer(分而治之)的策略來執行。其作法是從數列中挑選一個基準點(Pivot)，大於基準點的放在一邊(右邊)，小於基準點的放另一邊(左邊)，之後再反覆對序列執行此動作至左子數列和右子數列只剩一個數值或沒有數值即可完成排序。

本文以C++實作執行。

快速排序法實際執行狀況如下(假設需要將資料由小排到大):

1.從數列中挑選一個元素，稱為基準值(Pivot)
快速排序法的效率和所選取的基準值(Pivot)有很大的關係，可以每次選取中位數或是第一個數值或是最後一個數值或是亂數選擇。

2.將所有比基準值小的元素擺在基準點左邊形成左子序列。將所有比基準值大的元素擺在基準值右邊形成右子序列。

3.分別對左子序列和右子序列重複上述兩個步驟直到左子序列或右子序列只剩一個數值或沒有數值。

範例: 排序 3 7 1 2 9 4(pivot:4)

(3 1 2) 4 (9 7) (pivot: 1 7 ，4已排序)

1 (32) 4 7 (9) (pivot: 2 9; 1，4，7已排序)

1 2 (3) 4 7 9 (已完成排序)

時間複雜度如下:

最佳時間複雜度：O(nlogn) :第一個基準值剛好是中位數，剛好將資料分成兩部分。

平均時間複雜度：O(nlogn)

最差時間複雜度：O(n^2):當資料的順序剛好為由大到小或由小到大的時候，也就是發生在數列剛好是相反方樣排序好的情況下。

假設每次選取的pivot都是在第一個位置:

實作程式碼如下:

#include <iostream>
#include <ctime>
using namespace std;
#define MAX 10

void quickSort(int[], int, int);
void swap(int&, int&);

int main()
{
	int sortArray[MAX] = { 0 };
	srand(time(NULL));

	cout << "排序前:" << endl;

	for (int i = 0; i < MAX; i++)
	{
		sortArray[i] = rand() % 100;
		cout << *(sortArray + i) << " ";// 
	}

	quickSort(sortArray, 0, MAX - 1);
	cout << endl;
	cout << "排序後:" << endl;

	for (int i = 0; i < MAX; i++)
	{
		cout << *(sortArray + i) << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

void quickSort(int arr[], int left, int right)
{
	int temp;
	if (left < right)
	{
		int pivot = arr[left];//假設pivot在第一個的位置
		int l = left;
		int r = right + 1;
		
		while (1)
		{
			while (l < right && arr[++l] < pivot);//向右找小於pivot的數值的位置
			while (r > 0 && arr[--r] > pivot);//向左找大於pivot的數值的位置

			if (l >= r)//範圍內pivot右邊沒有比pivot小的數,反之亦然
			{
				break;
			}
		
			swap(arr[l], arr[r]);//比pivot大的數移到右邊，比pivot小的數換到左邊
		}

		swap(arr[left], arr[r]);//將pivot移到中間

		quickSort(arr, left, r - 1);//左子數列做遞迴
		quickSort(arr, r + 1, right);//右子數列做遞迴
	}
	
}

void swap(int&a, int&b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}

執行結果如下:

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

回首頁