插入排序交換排序選擇排序歸并排序基數(shù)排序(編輯修改稿)
2025-08-15 02:58 本頁面
【文章內(nèi)容簡介】 49 65 76 97四趟排序結(jié)果： 38 13 27 49 49 65 76 97五趟排序結(jié)果： 13 27 38 49 49 65 76 97 最快 正序 比較 n1次 不交換最慢 逆序 n(n1)/2次比較 同樣多次交換基本思想： 通過一趟排序?qū)⒋偶o(jì)錄分成上下兩個(gè)子列，上子列大于下子列。再對兩個(gè)子列繼續(xù)排序。理論依據(jù) ：排序序列 越短越好 ，源序列的排序度越好效率越高?？焖倥判? 49 38 65 97 76 13 27 49 pivot low high將 pivot和 high比較 下行 找到小于 pivot的紀(jì)錄交換一次交換后： 27 38 65 97 76 13 49將 pivot和 low比較 上行 找到 大于 pivot的紀(jì)錄交換二 次交換后： 27 38 97 76 13 65 49highlow 三 次交換后： 27 38 13 97 76 65 49四 次交換后： 27 38 13 49 76 97 65 49low highLow和 high相遇結(jié)束快速排序 27 38 13 49 76 97 65 49第一輪后 由 pivot49分成兩個(gè)子列，分別再進(jìn)行快速排序 27 38 13 49 76 97 65 49一次 13 38 49 49 97 65 二次 13 38 49 49 65 97 三次 13 27 38 49 49 65 76 97時(shí)間復(fù)雜性 O(knlogn)一趟快速排序算法的實(shí)現(xiàn)templateclass Tint Partition(ArrayDataTamp。L,const int low, const int high){ DataT pivot=L[low]。 L[0]=L[low]。 while(lowhigh) {while(lowhighamp。amp。L[high]=pivot) high。 L[low]=L[high]。 while(lowhighamp。amp。L[low]=pivot) low++。 L[high]=L[low]。 } L[low]=L[0]。 return low。 }時(shí)間復(fù)雜度快速排序算法的實(shí)現(xiàn)templateclass Tvoid QickSort(ArrayDataTamp。L, int low, int high){ if(lowhigh) { int pivotpos=Patition(L,low,high)。 QickSort(L,low,pivotpos1)。 QickSort(L,pivotpos+1,high)。 }}快速排序算法復(fù)雜性分析假設(shè) T(n)為對 n個(gè)紀(jì)錄進(jìn)行快速排序所需時(shí)間，對 n個(gè)紀(jì)錄進(jìn)行一趟快速排序 Patition(L,1,n)所需時(shí)間為 ,則 T(n)=+T(k1)+T(nk) =+2T(n/2) //理想化每次都分成相等的兩部分 =2+2(/2+2T(n/4))=3+4T(n/4) =4+8T(n/8)= =log2n+nT(1)=O(nlog2n)最壞 O(n2) 平均 O(nlog2n) 比較排序算法的下界
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1