|
快速排序算法實(shí)現(xiàn)之（三路劃分遍歷，解決與劃分元素相等元素的問(wèn)題） 算法原理：使用三路劃分策略對(duì)數(shù)組進(jìn)行劃分（也就是荷蘭國(guó)旗問(wèn)題，dutch national flag problem）。這個(gè)實(shí)現(xiàn)是對(duì)實(shí)現(xiàn)二的改進(jìn)，它添加處理等于劃分元素的值的邏輯，將所有等于劃分元素的值集中在一起，并且以后都不會(huì)再對(duì)他們進(jìn)行劃分。本算法中使用四個(gè)標(biāo)示值進(jìn)行操作。使用left和right同時(shí)向中間遍歷時(shí)，當(dāng)left遇見(jiàn)等于劃分元素時(shí)，就與iflag指向的值進(jìn)行交換（iflag指向的當(dāng)前值到最左端表示left在過(guò)程中遇見(jiàn)的等于劃分元素的值部分），同理，右邊也使用同樣的邏輯完成對(duì)等于劃分元素的處理。最后分別交換左右部分的相等值（left和iflag對(duì)應(yīng)交換，right和rflag對(duì)應(yīng)交換），由于需要返回兩個(gè)標(biāo)記值，所以將partition和quicksort合并成一個(gè)方法。
算法代碼： void quickSort_3(int *array, int l, int r) { /** * 由于三路劃分中有可能有兩個(gè)不同的劃分點(diǎn)，所以不能 * 使用函數(shù)直接返回，這里將partition和quickSort驅(qū)動(dòng) * 程序結(jié)合成一個(gè)方法； * */ if(l>=r) return; /** * 選擇pivot劃分元素，并將其與array[r]交換 * */ int pivot, temp; pivot=l+rand()%(r-l+1); temp=array[pivot]; array[pivot]=array[r]; array[r]=temp; /** * 雙向掃描： * left和right都為主動(dòng)移動(dòng) * lflag和rflag為被動(dòng)移動(dòng) * */ int left=l, lflag=l; int right=r-1, rflag=r-1; while(true) { while(array[left]<=array[r] && left * 如果array[left]與pivot相等，則將其交換到 * lflag當(dāng)前指向的元素 * */ if(array[left]==array[r]) { temp=array[left]; array[left]=array[lflag]; array[lflag]=temp; lflag++; } left++; } while(array[right]>=array[r] && right>=l) { /** * 如果array[right]與pivot相等，則將其交換到 * rflag當(dāng)前指向的元素 * */ if(array[right]==array[r]) { temp=array[right]; array[right]=array[rflag]; array[rflag]=temp; rflag--; } right--; } if(left>=right) break; /** * 將左邊大于pivot的元素與右邊小于pivot的元素進(jìn)行 * 交換 * */ temp=array[left]; array[left]=array[right]; array[right]=temp; left++;right--; } /** * 由于left和lflag指向的當(dāng)前元素都是即將需要處理的元素， * 也就是當(dāng)處理結(jié)束之后，他們都需要左移一步才是已經(jīng)處理好的 * 元素； 將等于pivot的元素交換到中間 * */ lflag--;left--; while(lflag>=l) { temp=array[left]; array[left]=array[lflag]; array[lflag]=temp; left--;lflag--; } /** * 由于right和rflag指向的當(dāng)前元素都是即將需要處理的元素， * 也就是當(dāng)處理結(jié)束之后，他們都需要右移一步才是已經(jīng)處理好的 * 元素；將等于pivot的元素交換到中間 * 注意：由于pivot本身也需要移動(dòng)到中間，所以這里的判斷條件 * 包含r * */ rflag++;right++; while(rflag<=r) { temp=array[right]; array[right]=array[rflag]; array[rflag]=temp; right++;rflag++; } /** * 最終遞歸處理左右子序列部分 * */ quickSort_3(array, l, left); quickSort_3(array, right, r); } int main() { int array[]={2,5,8,2,1,6}; quickSort_3(array,0,5); for(int i=0;i<6;i++) printf("%d,",array[i]); return 1; } 算法說(shuō)明： 即使沒(méi)有重復(fù)鍵，最后的移動(dòng)開(kāi)銷(xiāo)就不需要，即使有也是線(xiàn)性問(wèn)題；較好的處理了劃分元素的相等值問(wèn)題，沒(méi)有多余的性能損耗，所以運(yùn)行時(shí)間為線(xiàn)性N。 此程序?qū)⑿蛄袆澐殖扇齻€(gè)部分：小于劃分元素的元素（放置于a[l]到a[left]）；等于劃分元素的元素（放置于a[left+1]到a[right-1]）；大于劃分元素的元素（放置于a[right]到a[r]）；由于直接進(jìn)行如此劃分不是特別方便，所以首先將left和right指針?lè)謩e遇到的等于pivot的元素放置到最左邊和最右邊，當(dāng)處理完所有元素之后才將兩邊等于pivot的元素拷貝到序列中間，并且分別遞歸處理left左邊的序列和right右邊的序列； 快速排序算法實(shí)現(xiàn)之（三元中值法，InsertSort處理小子文件，減少遞歸棧） 算法原理：此算法利用insert算法處理小子文件，從而有效減小系統(tǒng)?？臻g的耗用；使用三元中值（Median-of-Three-Method）劃分策略在數(shù)組的左，中，右抽樣，并使用他們的中值作為劃分元素，然后使用小子文件（放棄對(duì)小序列使用遞歸調(diào)用）策略對(duì)序列元素小于11的子序列放棄使用遞歸，而是使用插入排序。也就是將每一次遞歸之前進(jìn)行判斷的if(l>=r) return;修改為當(dāng)l和r相差一定大小的時(shí)候就調(diào)用Insertion Sort。使用Probabilistic Algorithm（隨機(jī)取值）獲取的劃分元素可以最高概率地獲得好性能。Median-of-Three Method（取頭，中，尾三處的中間大小元素）獲取的劃分元素可以更好地獲取高性能（減少算法平均時(shí)間的10%） 算法代碼： void insertSort(int *array, int l, int r); int partition_4(int *array, int l, int r) { int temp; int pivot; /** * 獲取array[l],array[(l+r)/2], array[r] * 的中間值 * */ if(array[l]<=array[(l+r)/2]<=array[r] || array[r]<=array[(l+r)/2]<=array[l]) pivot=array[(l+r)/2]; else if(array[(l+r)/2]<=array[r]<=array[l] || array[l]<=array[r]<=array[(l+r)/2]) pivot=array[r]; else if(array[(l+r)/2]<=array[l]<=array[r] || array[r]<=array[l]<=array[(l+r)/2]) pivot=array[l]; temp=array[pivot]; array[pivot]=array[r]; array[pivot]=temp; /** * 雙向掃描： * left從array的左邊l處開(kāi)始向右處理，直到r-1 * right從array的右邊r-1處開(kāi)始向左處理，直到l * left和right都是主動(dòng)移動(dòng) * */ int left=l, right=r-1; while(true) { /** * left左邊的元素為小于等于array[r]的元素 * 并注意array[r]為最大值的情況，left會(huì)一直 * 移動(dòng)到r * */ while(array[left]<=array[r] && left<> left++; /** * right右邊的元素為大于array[r]的元素 * 并注意array[r]為最小值的情況，right會(huì)一直 * 移動(dòng)到l-1 * 這里僅使用大于的邏輯關(guān)系還可以避免當(dāng)array * 都是相同元素的情況時(shí)指針交叉的發(fā)生 * */ while(array[right]>array[r] && right>=l) right--; /** * 有四種序列情況： * 1. 一般情況：left和right在序列中間的某個(gè)元素交叉 * 2. array[r]是最大值情況：left移動(dòng)到r,right在r-1 * 3. array[r]是最小值情況：left在l，right移動(dòng)到l-1 * 4. array所有元素為同一個(gè)值：left移動(dòng)到r，right在r-1 * */ if(left>=right) break; /** * 交換元素 * */ temp=array[left]; array[left]=array[right]; array[right]=temp; left++;right--; } /** * 最終將array[r]的pivot元素與array[left]進(jìn)行交換 * 由于此時(shí)的array[right]比array[r]小，所以只能交換 * array[left] * */ temp=array[left]; array[left]=array[r]; array[r]=temp; return left; } void quickSort_4(int *array, int l, int r) { /** * 當(dāng)序列大小小于11的時(shí)候，假設(shè)此時(shí)系統(tǒng)堆棧的開(kāi)銷(xiāo)已經(jīng) * 大于處理遞歸序列本身的開(kāi)銷(xiāo)，則遞歸調(diào)用具有低效率， * 所以直接使用插入排序進(jìn)行排序 * */ if(l-r>11) { insertSort(array, l, r); return; } /** * 利用partition方法獲取劃分元素 * */ int pivot=partition_4(array, l, r); /** * 劃分元素已經(jīng)到達(dá)最終位置，所以不用參與進(jìn)一步處理 * 分別遞歸處理左右部分的元素 * */ quickSort_4(array, l, pivot-1); quickSort_4(array, pivot+1, r); } int main() { int array[]={2,5,8,2,1,6}; quickSort_4(array,0,5); for(int i=0;i<6;i++) printf("%d,",array[i]); return 1; } 算法說(shuō)明： 優(yōu)勢(shì)：當(dāng)系統(tǒng)遞歸棧的開(kāi)銷(xiāo)所占遞歸處理本身的比例較高時(shí)，快速排序性能較低，從而可以使用直接排序而非遞歸處理小子文件； 三元中值劃分法表示一種抽樣估算的思想，也就是使得劃分元素盡量接近序列的中間值，具體的抽樣可不限于三個(gè)，并且在代碼實(shí)現(xiàn)的時(shí)候，需要考慮到循環(huán)內(nèi)部操作的優(yōu)化， 并且在實(shí)現(xiàn)過(guò)程中，為了優(yōu)化棧操作，有的較小序列直接使用插入排序，可以從系統(tǒng)的角度提升算法的性能。 時(shí)間：運(yùn)行時(shí)間可以在N㏒N的基礎(chǔ)上減少10%。小子文件大小在5-25之間的性能改善相似 |
|
|
來(lái)自： kingwenguang > 《排序》
