快速排序在最壞的情況下時間復(fù)雜度Ω(nlgn)

1??在元素各異時或者少量相等（元素個數(shù)n>70)
時間復(fù)雜度Ω(nlgn)

void quick_sort_by_median(int *array,int start,int end) {if(start<end){int median = select(array,start,end,(end - start + 1)/2 + (end - start + 1) % 2);int middle = partition(array,start,end,median);quick_sort_by_median(array,start,middle-1);quick_sort_by_median(array,middle+1,end);} }

2??在有大量元素相同時（元素個數(shù)n>70)
時間復(fù)雜度Ω(nlgn)

KeyValuePair partition_contains_equal_elements(int *array,int start,int end,int key) {//line.key表示已排序中最后一個小于key的元素的位置//line.value表示已排序中最后一個等于key的元素的位置KeyValuePair line(start - 1,start - 1);for (int i = start; i < end + 1; ++i) {if(array[i]<key){line.key++;line.value++;int temp = array[i];array[i] = array[line.value];array[line.value] = array[line.key];array[line.key] = temp;}else if(array[i] == key){line.value++;array[i] = array[line.value];array[line.value] = key;}}return line; } void quick_sort_by_median_contains_equal_elements(int *array,int start,int end) {if(start<end){int median = select(array,start,end,(end - start + 1)/2 + (end - start + 1)%2);KeyValuePair middle_line = partition_contains_equal_elements(array,start,end,median);quick_sort_by_median(array,start,middle_line.key);quick_sort_by_median(array,middle_line.value + 1,end);} }

輔助函數(shù)select和partition
鏈接地址
輔助類KeyValuePair
鏈接地址

總結(jié)

以上是生活随笔為你收集整理的快速排序在最坏的情况下时间复杂度（Ω(nlgn)(算法导论第三版9.3-3））的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。