求数组中第k大的数

求一个数组中第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大数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
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;
}
algorithm
algorithm，Array