求一个数组中第k大的数方法

忘是亡心i 2022-09-26 02:24 133阅读 0赞

求一个数组中第k大的数，我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn),n为数组长度。但是我们都知道快速排序是对冒泡的改进，降低冒泡的递归深度，使时间复杂度降低到O(nlgn)，为什么不用快排呢？那么快排的时间复杂度又是多少呢？

因为快排每次将数组划分为两组加一个枢纽元素，每一趟划分你只需要将k与枢纽元素的下标进行比较，如果比枢纽元素下标大就从右边的子数组中找，如果比枢纽元素下标小从左边的子数组中找，如果一样则就是枢纽元素，找到，如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

最差情况如下：假设快排每次都平均划分，但是都不在枢纽元素上找到第k大

第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，。。。。。，第k趟找到，时间复杂度为O(n/2k)，所以总的时间复杂度为

O(n(1+1/2+....+1/2k))=O(n)，明显比冒泡快，虽然递归深度是一样的，但是每一趟时间复杂度降低。

快排求第k大数代码如下：

![复制代码][copycode.gif]

/*
    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]; //这里每次的枢纽元素都取了待排数组的第一个元素，记住是a[low],而不是a[0]
        if(low < high)  //时间复杂度是O(n),n是数组长度
        {
            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); //划分子递归数组
            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为数组长度
            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;
    }

![复制代码][copycode.gif]

[copycode.gif]: /images/20220717/e6eefede14664780ad2a1512a5d0d850.png