|
求一個數(shù)組中第k大的數(shù)，我第一印象是冒泡,，因為只要冒泡k趟即可,，第一趟冒泡第一大，第二次冒泡第二大,，第k次冒泡第k大,，時間復(fù)雜度為O(kn),n為數(shù)組長度。但是我們都知道快速排序是對冒泡的改進(jìn),，降低冒泡的遞歸深度,，使時間復(fù)雜度降低到O(nlgn),，為什么不用快排呢？那么快排的時間復(fù)雜度又是多少呢,？ 因為快排每次將數(shù)組劃分為兩組加一個樞紐元素,，每一趟劃分你只需要將k與樞紐元素的下標(biāo)進(jìn)行比較，如果比樞紐元素下標(biāo)大就從右邊的子數(shù)組中找,，如果比樞紐元素下標(biāo)小從左邊的子數(shù)組中找,，如果一樣則就是樞紐元素，找到,，如果需要從左邊或者右邊的子數(shù)組中再查找的話,，只需要遞歸一邊查找即可，無需像快排一樣兩邊都需要遞歸,，所以復(fù)雜度必然降低,。 最差情況如下：假設(shè)快排每次都平均劃分，但是都不在樞紐元素上找到第k大 第一趟快排沒找到,，時間復(fù)雜度為O(n),，第二趟也沒找到，時間復(fù)雜度為O(n/2),，,。。,。,。。,，第k趟找到,，時間復(fù)雜度為O(n/2k)，所以總的時間復(fù)雜度為 O(n(1+1/2+....+1/2k))=O(n),，明顯比冒泡快,，雖然遞歸深度是一樣的，但是每一趟時間復(fù)雜度降低,。 快排求第k大數(shù)代碼如下：  /* Description: Get K large number in a array for example: a={3,1,4,7,5,8,0}, 5 large number is 5 the most optimal algorithm is QuickSort or BubbleSort, or there is a better algorithm for this question. */ #include <stdio.h> #define length(array) sizeof(array)/sizeof(array[0]) #define true 1 #define false 0 int Sort(int *a, int low, int high) { int pivot = a[low]; //這里每次的樞紐元素都取了待排數(shù)組的第一個元素,，記住是a[low],而不是a[0] if(low < high) //時間復(fù)雜度是O(n),n是數(shù)組長度 { while(a[high] >= pivot && low < high) high --; a[low] = a[high]; while(a[low] <= pivot && low <high) low ++; a[high] = a[low]; } a[low] = pivot; return low; } int QuickSort_K_MAX(int *a, int low, int high, int k) { if(low >= high) return a[low]; else { int mid = Sort(a,low,high); //劃分子遞歸數(shù)組 if(mid > k) QuickSort_K_MAX(a,low,mid-1,k); //左遞歸 else if(mid < k) QuickSort_K_MAX(a,mid+1,high,k); //右遞歸，一旦右遞歸mid+1=high,，將退化成冒泡,，遞歸深度將變成n，n為數(shù)組長度 else return a[mid]; } } int main() { int a[10] = {10,7,8,6,3,1,5,2,4,9}; int k =6; int len = length(a); printf("%d",QuickSort_K_MAX(a,0,len-1,len-k)); return 0; }
|
|
|
