整数数组中取第k小的

方法1：升序排序之后取第k个
            排序算法用归并排序、插入排序对应的时间复杂度分别为O(nlgn)、O(n²)
方法2：用归并排序的思想，类似二分法
          假设针对int arr[]在[l, h)区间取第k小的数
          
         步骤1、保证h-l>=k
         步骤2、取arr[l]，将其移动到位置m，使m的左边都小于arr[l]，右边都大于arr[l]
         步骤3、如m-l+1==k，则a[m]即是
                    若m-l+1>k，则在[l, m)区间找第k小的
                    若m-l+1在[m+1, h)区间找第k-(m-l+1)小的
        可见，这是一个递归过程，代码如下：
        int arr[] = {8,1,3,6,9,0,4,7,5,2}; 
        int len = sizeof(arr)/sizeof(arr[0]);
        int find(int l, int h, int k) //l和h确定区间，k指定第几个       
        {
            if( (h-l) < k ) cout<<"error"<             int m = l, falg = 0, key = arr[l], t = 0;
            for(int i = l; i             {
                if( flag == 0)
                {
                    if( arr[i] < key)
                        ++m;
                    else
                        flag = 1; //表示接下来 arr[i] < key的要交换了
                }
                else
                {
                    if( arr[i] < key) 
                    {
                        ++m;
                        t = arr[i]; arr[i] = arr[m]; arr[m] = t;
                    }
                }
            }
            arr[l] = arr[m]; arr[m] = key;
            if( (m-l+1) == k) 
                cout<             else if( (m-l+1) > k)
                find(l, m, k);
            else
                find(m+1, h, k-(m-l+1)); //左边已经有m-l+1个小的了
        }

注意点：确定接下来在哪个部分查找，以及要找第几小的