快捷導(dǎo)航

C++快速排序算法簡(jiǎn)明理解

更新時(shí)間：2022年05月27日 08:57:03 作者：m78星云杰克

快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實(shí)實(shí)用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個(gè)，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影

一、問(wèn)題描述

[問(wèn)題] 應(yīng)用快速排序方法對(duì)一個(gè)記錄序列進(jìn)行升序排列。快速排序(quick sort)的分治策略如下。

(1)劃分:選定一個(gè)記錄作為軸值，以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列r（1）… r（i-1）)和r（i+1）…r（n）,軸值的位置i在劃分的過(guò)程中確定,并且前一個(gè)子序列中的記錄均小于或等于軸值,后一個(gè)子序列中的記錄均大于或等于軸值；

(2)求解子問(wèn)題:分別對(duì)劃分后的每一個(gè)子序列造歸處理；

(3)合并：由于子序列排序是就地進(jìn)行的，所以合并不需要任何操作。

二、想法

[想法] 首先對(duì)待排序記錄序列進(jìn)行劃分，劃分的軸值應(yīng)該遵循平衡子問(wèn)題的原則,使劃分后的兩個(gè)子序列的長(zhǎng)度盡量相等，這是決定快速排序算法時(shí)間性能的關(guān)鍵。軸值的選擇有很多方法,例如，可以隨機(jī)選出一個(gè)記錄作為軸值，從而期望劃分是較平衡的。

第一次劃分過(guò)程：

后續(xù)排序結(jié)果：

三、算法實(shí)現(xiàn)

int Partition(int r[],int start,int end) {        
	int i=start,j=end;
	while(i<j) {
		while (i<j&&r[i]<=r[j])    //對(duì)右側(cè)掃描，即r[i] 與右側(cè)的r[j...i+1]比較，升序排序，如果有小于r[i]的值，即右小于左則跳出循環(huán)，還有i>=j也跳出循環(huán)，即比較完，沒(méi)有比它小的，必須兩個(gè)條件同時(shí)滿足。
			j--;
		if(i<j) {      //在i<j的情況下滿足r[j]<r[i]
			r[i]=r[i]^r[j];    //交換值
			r[j]=r[i]^r[j];		//注意：如果位置一樣不可以使用異或交換值，即r[1]不能異或r[1];
			r[i]=r[i]^r[j];    //也可以定義中間值，進(jìn)行交換
			i++;
		}
	}
	while (i<j&&r[i]<=r[j])//對(duì)左側(cè)掃描，即r[j] 與左側(cè)的r[i...j-1]比較，升序排序，如果有大于r[j]的值，即左側(cè)值大于右側(cè)值則跳出循環(huán)，還有i>=j也跳出循環(huán)，即比較完，沒(méi)有比它大的，必須兩個(gè)條件同時(shí)滿足。
		i++;
	if(i<j) {    //在i<j的情況下滿足r[i]>r[j]
		r[i]=r[i]^r[j];
		r[j]=r[i]^r[j];
		r[i]=r[i]^r[j];
		j--;
	}
	return i;     //返回軸值
}
void Quicksort(int r[],int start ,int end) {     //快速排序 
	int pivot;      //記錄軸值
	if(start<end) {     //界限值
		pivot=Partition(r,start,end);    //排序并獲得軸值
		Quicksort(r,start,pivot-1);      //對(duì)軸值左側(cè)遞歸
		Quicksort(r,pivot+1,end);		//對(duì)軸值右側(cè)遞歸
	}
}