插入排序交換排序選擇排序歸并排序基數排序(編輯修改稿)
2025-08-15 02:58 本頁面
【文章內容簡介】 49 65 76 97四趟排序結果： 38 13 27 49 49 65 76 97五趟排序結果： 13 27 38 49 49 65 76 97 最快 正序 比較 n1次 不交換最慢 逆序 n(n1)/2次比較 同樣多次交換基本思想： 通過一趟排序將待排紀錄分成上下兩個子列，上子列大于下子列。再對兩個子列繼續(xù)排序。理論依據 ：排序序列 越短越好 ，源序列的排序度越好效率越高?？焖倥判? 49 38 65 97 76 13 27 49 pivot low high將 pivot和 high比較 下行 找到小于 pivot的紀錄交換一次交換后： 27 38 65 97 76 13 49將 pivot和 low比較 上行 找到 大于 pivot的紀錄交換二 次交換后： 27 38 97 76 13 65 49highlow 三 次交換后： 27 38 13 97 76 65 49四 次交換后： 27 38 13 49 76 97 65 49low highLow和 high相遇結束快速排序 27 38 13 49 76 97 65 49第一輪后 由 pivot49分成兩個子列，分別再進行快速排序 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時間復雜性 O(knlogn)一趟快速排序算法的實現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。 }時間復雜度快速排序算法的實現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)。 }}快速排序算法復雜性分析假設 T(n)為對 n個紀錄進行快速排序所需時間，對 n個紀錄進行一趟快速排序 Patition(L,1,n)所需時間為 ,則 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)評公示相關推薦
鄂ICP備17016276號-1