算法導論 第7章 高速排序

高速排序在最壞情況下的時間複雜度為O(n^2)，盡管在最壞情況下執行時間比較差，可是高速排序一般是用于排序的最佳選擇。由于其平均性能相當好，期望的執行時間為O(nlgn)，且在O(nlgn)的記号中隐含的常數因子非常小。

高速排序和合并排序有相似之處，都是須要劃分序列，在合并排序中。劃分的過程非常easy。直接選擇元素序列的中間位劃分位置，排序是在合并的過程中實作的，是以合并排序的合并過程非常重要。相比合并排序，高速排序就沒有合并的過程。僅僅有劃分，高速排序的劃分過程非常重要，排序是在劃分的過程中實作的。

/*
 *	算法導論 第七章 高速排序
 *	最壞情況下時間複雜度為O(n^2)，這樣的情況出如今每次選擇pivot的時候
 *	都選到了最大或者最小的元素。即每次劃分都有一邊為空。      

* 其平均時間複雜度為O(nlgn)，僅僅要每次劃分，每一邊的元素都至少有一個即可

*/

#include <iostream>

#include <ctime>

using namespace std;

void printArray(int arr[], int len)

{

for (int i=0; i<len; i++)

{

cout << arr[i] << " ";

}

cout << endl;

}

void quickSort(int arr[], int p, int r);

int partition(int arr[], int p, int r);

void exchange(int arr[], int i, int j);

int randomizedPartition(int *arr, int p, int r);

void randomizedQuickSort(int *arr, int p, int r);

int main()

int arr[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};

int len = sizeof(arr) / sizeof(arr[0]);

cout << "原數組：" << endl;

printArray(arr, len);

//quickSort(arr, 0, len-1);

randomizedQuickSort(arr, 0, len-1);

cout << "高速排序後的數組：" << endl;

void quickSort(int arr[], int p, int r)

if (p < r)

int q = partition(arr, p, r);

quickSort(arr, p, q-1);

quickSort(arr, q+1, r);

int partition(int arr[], int p, int r)

int pivot = arr[r];

int i = p - 1;//i前面的（包含i）的元素都是不大于pivot的。i後面的都是大于pivot的元素

int j;//j後面的（包含j）都是還沒有劃分的

for (j=p; j<=r-1; j++)

if (arr[j] <= pivot)

{

i++;

exchange(arr, i, j);

}

i++;

exchange(arr, i, r);

return i;

void exchange(int arr[], int i, int j)

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

/*

* 随機化劃分

int randomizedPartition(int *arr, int p, int r)

srand(time(NULL));

int i = p + rand() % (r-p+1);

return partition(arr, p, r);

* 随機化高速排序

* 期望時間複雜度為O(nlgn)

void randomizedQuickSort(int *arr, int p, int r)

int q = randomizedPartition(arr, p, r);

randomizedQuickSort(arr, p, q-1);

randomizedQuickSort(arr, q+1, r);

習題7-6 對區間的模糊排序。算法思想見 javascript:void(0)，代碼例如以下：

/*
 *	算法導論 第七章 習題7-6
 *	算法思想跟高速排序相似，僅僅是對于區間的劃分處理有點差别
 *	時間複雜度也為O(nlgn)，
 *	在全部區間都有重疊時，就僅僅會進行一次劃分，時間複雜度為O(n)
 */

#include <iostream>
#include <ctime>
using namespace std;

typedef struct Interval 
{
	int a;//左端點
	int b;//右端點

	Interval(){}

	Interval(int x, int y)
	{
		a = x;
		b = y;
	}

	bool operator<(const Interval &interval)
	{
		return b < interval.a;
	}

	bool operator>(const Interval &interval)
	{
		return a > interval.b;
	}

	bool operator==(const Interval &interval)
	{
		return a<=interval.b && b>=interval.a;
	}

}Interval;

void printArray(Interval arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << "[" << arr[i].a << ", " << arr[i].b << "]" << " ";
	}
	cout << endl;
}

void quickSort(Interval arr[], int p, int r);
Interval partition(Interval arr[], int p, int r);
void exchange(Interval arr[], int i, int j);

int main()
{
	cout << "請輸入區間個數：" << endl;
	int len;
	cin >> len;
	Interval *arr = new Interval[len];
	srand(time(NULL));
	for (int i=0; i<len; i++)
	{
		arr[i].a = rand() % 100;
		arr[i].b = rand() % 100;
		if (arr[i].a > arr[i].b)
		{
			int temp = arr[i].a;
			arr[i].a = arr[i].b;
			arr[i].b = temp;
		}
	}

	cout << "原區間數組：" << endl;
	printArray(arr, len);

	quickSort(arr, 0, len-1);

	cout << "模糊排序後的區間數組：" << endl;
	printArray(arr, len);

	return 0;
}


void quickSort(Interval arr[], int p, int r)
{
	if (p < r)
	{
		Interval q = partition(arr, p, r);
		if (q.a > p)
		{
			quickSort(arr, p, q.a);
		}

		if (q.b < r)
		{
			quickSort(arr, q.b, r);
		}
	}
}

Interval partition(Interval arr[], int p, int r)
{
	Interval pivot = arr[r];
	int i = p - 1;//i前面的（包含i）元素都是小于pivot的
	int j = r + 1;//j後面的（包含j）的元素都是大于pivot的
	int k = p;//i和k之間的元素師和pivot相等的，k和j之間的元素是還未比較的
	Interval divider(i, j);
	while (k<j & k<=r)
	{
		if (arr[k] < pivot)
		{
			i++;
			exchange(arr, i, k);
			k++;
		} else if (arr[k] > pivot) {
			j--;
			exchange(arr, k, j);
		} else {
			/*
			 *	假設相等，說明arr[k]和pivot的區間有重疊，則必須将樞紐點區間縮小，取arr[k]和pivot的重疊區間
			 *	否則就不能保證劃分的準确性
			 *	比如區間[5, 9], [1, 7], [0, 3]，假設去pivot=[1, 7]。則[5, 9]和[0, 3]的順序不會被交換。這是錯誤的
			 *	必須每次遇到重疊區間，就更新pivot
			 */
			pivot.a = max(pivot.a, arr[k].a);
			pivot.b = min(pivot.b, arr[k].b);
			k++;
		}
	}

	if (i > divider.a)
	{
		divider.a = i;
	}

	if (j < divider.b)
	{
		divider.b = j;
	}

	return divider;
}

void exchange(Interval arr[], int i, int j)
{
	Interval temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}