找出數(shù)組中第i小元素

期望時間復雜度：Θ(n)
最壞情況的時間復雜度Θ(n^2)

int randomized_select(int *array,int start,int end,int index){if(start == end)return array[start];int middle = randomized_partition(array,start,end);int position = middle - start + 1;if(index == position)return array[middle];else if(index < position)return randomized_select(array,start,middle-1,index);elsereturn randomized_select(array,middle + 1,end,index - position); }

快速排序的隨機劃分函數(shù):randomized_partition
>>鏈接地址

本版本為錯誤版本，中間的中位數(shù)求中位數(shù)排序用了插入排序，用插入算法，在最壞的情況下，時間復雜度Ω(n^2)

int select(int *array,int start,int end,int index) {//if(start == end) return array[start];const int constant_num = 5;int remainder = (end - start + 1) % constant_num;int zero = remainder == 0 ? 0 : 1;int num = (end - start + 1) / constant_num + zero;int *median = new int[num];if(remainder){insertion_sort(array,start + (num - 1 ) * constant_num,start + (num - 1 ) * constant_num + remainder-1);median[num-1] = array[start + (num - 1 ) * constant_num + (remainder - 1)/2];}for (int i = 0; i < num - zero; ++i) {insertion_sort(array,start + i * constant_num,start + (i+1) * constant_num - 1);median[i] = array[start + i * constant_num + constant_num / 2];}insertion_sort(median,0,num-1);int key = median[(num-1) / 2];delete[] median;//劃分int middle = partition(array,start,end,key);//遞歸求解int position = middle - start + 1;if(index == position){return array[middle];}else if(index < position){return select(array,start,middle-1,index);}else{return select(array,middle + 1,end,index - position);} }

下面是最壞情況的（當n>70時）時間復雜度Θ(n)
以下是正確版本

int select(int *array,int start,int end,int index) {if(start == end) return array[start];const int constant_num = 5;int remainder = (end - start + 1) % constant_num;int zero = remainder == 0 ? 0 : 1;int num = (end - start + 1) / constant_num + zero;int *median = new int[num];if(remainder){insertion_sort(array,start + (num - 1 ) * constant_num,start + (num - 1 ) * constant_num + remainder-1);median[num-1] = array[start + (num - 1 ) * constant_num + (remainder-1)/2];}for (int i = 0; i < num - zero; ++i) {insertion_sort(array,start + i * constant_num,start + (i+1) * constant_num - 1);median[i] = array[start + i * constant_num + constant_num / 2];}int key = select(median,0,num-1,num/2 + (num % 2 == 0 ? 0 : 1));delete[] median;//劃分int middle = partition(array,start,end,key);//遞歸求解int position = middle - start + 1;if(index == position){return array[middle];}else if(index < position){return select(array,start,middle-1,index);}else{return select(array,middle + 1,end,index - position);} }

輔助函數(shù)partition

int partition(int *array,int start,int end,int key) {for (int i = start; i < end + 1; ++i) {if(array[i] == key){int temp = array[i];array[i] = array[end];array[end] = temp;break;}}int middle = start - 1;for (int i = start; i < end; ++i) {if(array[i] <= key){middle++;int temp = array[i];array[i] = array[middle];array[middle] = temp;}}array[end] = array[middle+1];array[middle+1] = key;return middle + 1; }

總結

以上是生活随笔為你收集整理的找出数组中第i小元素(时间复杂度Θ(n)--最坏情况为线性的选择算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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