快速排序

快速排序,說(shuō)白了就是給基準(zhǔn)數(shù)據(jù)找其正確索引位置的過(guò)程

1.1快速排序引入

希爾排序相當(dāng)于直接插入排序的升級(jí)，他們屬于插入排序類(lèi)；堆排序相當(dāng)于簡(jiǎn)單選擇排序的升級(jí)，他們同屬于選擇排序類(lèi)；而對(duì)于交換排序類(lèi)的冒泡排序升級(jí)版本就是快速排序。

1.2快速排序的基本思想

通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)排序的目的。

1.3快速排序的排序流程

• 首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分。
• 將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
• 然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類(lèi)似處理。
• 重復(fù)上述過(guò)程，可以看出，這是一個(gè)遞歸定義。通過(guò)遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。

總結(jié)來(lái)說(shuō)：就是分治+填數(shù)

1.4實(shí)例說(shuō)明

以12、10、8、22、5、13、28、21、11我們要將它按從小到大排序排序過(guò)程：

詳細(xì)過(guò)程：

設(shè)定兩個(gè)指針 left 和 right，它們初始分別指向待排序序列的左端和右端；此外還要附設(shè)一個(gè)基準(zhǔn)元素 tmp（一般選取第一個(gè)，本例中基準(zhǔn)tmp的值為 20）。

首先從 right 所指的位置從右向左搜索找到第一個(gè)小于 tmp 的元素，然后將其記錄在基準(zhǔn)元素所在的位置。

接著從 left 所指的位置從左向右搜索找到第一個(gè)大于 tmp的元素，然后將其記錄在 right 所指向的位置。

然后再?gòu)?right 所指向的位置繼續(xù)從右向左搜索找到第一個(gè)小于 tmp 的元素，然后將其記錄在 left 所指向的位置。

接著，left 繼續(xù)從左向右搜索第一個(gè)大于 tmp的元素，如果在搜索過(guò)程中出現(xiàn)了 left == right ，則說(shuō)明一趟快速排序結(jié)束。此時(shí)將 tmp 記錄在 left 和 right 共同指向的位置即可。

以上便是一輪快速排序的詳細(xì)過(guò)程

注意：

1. 向下劃分至少需要這個(gè)組兩個(gè)數(shù)據(jù)，才有必要?jiǎng)澐郑?個(gè)或者1個(gè)都沒(méi)有必要
2. 劃分時(shí)：從右向左找比基準(zhǔn)小的（相等）
3. 從左向右找比基準(zhǔn)值大的

1.5代碼實(shí)現(xiàn)

//一次劃分函數(shù)  核心函數(shù)  //返回基準(zhǔn)值最終所在下標(biāo)
int Partition(int *arr, int left, int right)
{
	//先講arr數(shù)組里的[left， right]的第一個(gè)值 作為基準(zhǔn)值
	int tmp = arr[left];
	while(left < right)
	{
		while(left<right && arr[right] > tmp)//左右邊界沒(méi)有相遇且當(dāng)前右邊的值大于基準(zhǔn)值tmp
		right--;
		if(left < right)//如果此時(shí)，左右邊界沒(méi)有相遇，那就只能證明右邊right找到了一個(gè)小于等于基準(zhǔn)值tmp的值
		{
			arr[left] = arr[right];
		}
		else
		{
			break;
		}
		while(left<right && arr[left] <= tmp)//左右邊界沒(méi)有相遇且當(dāng)前左邊的值小于等于基準(zhǔn)值tmp
		left++;
		if(left < right)//如果此時(shí)，左右邊界沒(méi)有相遇，那就只能證明左邊left找到了一個(gè)大于基準(zhǔn)值tmp的值
		{
			arr[right] = arr[left];
		}
		else
		{
			break;
		}
	}
	arr[left] = tmp;//此時(shí) 因?yàn)?left == right
	return left;//return right ok
}
void Quick(int *arr, int left, int right)
{
	if(left < right)//通過(guò)left <right  保證[left, right]這個(gè)范圍內(nèi)至少兩個(gè)數(shù)據(jù)
	{
		int par = Partition(arr, left, right);
		if(left < par-1)//基準(zhǔn)值左半部分  至少有兩個(gè)值才有必要去遞歸
		{
			Quick(arr, left, par-1);
		}
		if(par+1 < right)//基準(zhǔn)值右半部分  至少有兩個(gè)值才有必要去遞歸
		{
			Quick(arr, par+1, right);
		}
	}
}
void QuickSort(int *arr, int len)
{
	Quick(arr, 0, len-1);
}

1.6性能分析

越亂越快，越有序越慢

時(shí)間復(fù)雜度：

最優(yōu)情況：O（nlogn）每次數(shù)據(jù)元素都能平均的分成兩個(gè)部分。得到一個(gè)完全二叉樹(shù)；

最壞情況： O（n^2）這個(gè)數(shù)僅有右子樹(shù)或左子樹(shù)，比較次數(shù)為 （n-1）+（n-2) + (n-3) + … +1=n*(n-1)/2 ；

平均情況：O（nlogn）。

空間復(fù)雜度：O（1）。

穩(wěn)定性：因?yàn)殛P(guān)鍵字的比較和交換是跳躍進(jìn)行的，會(huì)改變數(shù)據(jù)元素的相對(duì)位置；因此，快速排序是一種不穩(wěn)定的排序方法，但是也是內(nèi)排序中平均效率最高的排序算法。

（小白一位，如有錯(cuò)誤歡迎指正）