問題描述

查找數組中第k小的值，(中位數)。

算法思路

執行一次快排，然后查找下標即可，所需要的時間復雜度接近\(O(n\log n)\)

通過觀察發現子問題不需要合并，只需要分解，跟快速排序的思想一致。

1. 選取標志，使用快速排序的方法，將大于數據的放右，小于放左。

2. 取標志的坐標，跟k比較，有如下三種情況。
   如果這個數據前有s個數據，根據如下表達式可計算第k小的數

3. 對于不同情況繼續遞歸

算法的時間復雜度接近于\(O(n)\)

python偽代碼表示

def findKMaxNum(array: [] as a, start: int, end: int, k: int):
	# 這里start和end都是計算機從0開始的索引
	pivot = randChooseIndex(array) # 隨機選取一個下標
	quickSortSub(a, pivot, start, end) # 以主元進行一個快速排序的子程序，把大于主元的放前面，小于的放后面
	if k > pivot - start + 1:
		return findKMaxNum(a, pivot + 1, end, k-(mid-start+1))
	elif k < pivot - start + 1:
		return findKMaxNum(a, start, pivot - 1, k)
	else: return array[pivot]

實際代碼演示（以C++為例）

/// @brief 隨機選取坐標，然后進行初次排序
/// @param a 數組
/// @param start 開始
/// @param end 結束位置
/// @return 排序后的標志位置
int randon_choose(int array[], int start, int end)
{
    if(start == end)
        return start;
    int pivot_pos = rand() % (end - start) + start;
    swap(array[end], array[pivot_pos]);

    int left = start;
    int right = end;
    int pivot_value = array[end];
    while (left < right)
    {
        while (left < right && array[left] < pivot_value)
        {
            left++;
        }
        array[right] = array[left];
        while (left < right && array[right] > pivot_value)
        {
            right--;
        }
        array[left] = array[right];
    }
    array[right] = pivot_value;
    return right;
}

/// @brief 隨機選擇, 找到第k個小的元素
/// @param array 數組
/// @param start 開始位置
/// @param end 結束位置
/// @return 第k個小的元素
int randon_selection(int array[], int start, int end, int k)
{
    int pivot_index = 0;
    int mid = randon_choose(array, start, end);
    if (k == (mid - start + 1))
    {
        return array[mid];
    }
    else if (k < (mid - start + 1))
    {
        return randon_selection(array, start, mid - 1, k);
    }
    else if (k > (mid - start + 1))
    {
        return randon_selection(array, mid + 1, end, k - (mid - start + 1));
    }
    return -1;
}

int main()
{
    int a[9] = {1, 5, 4, 2, 3, 9, 10, 22, 11};
    for (int i = 0; i < 9; i++)
    {
        printf("其中第%d個小的元素為%d\n", i, randon_selection(a, 0, 8, i));
    }

    return 0;
}

代碼運行的結果為

其中第0個大的元素為1
其中第1個大的元素為2
其中第2個大的元素為3
其中第3個大的元素為4
其中第4個大的元素為5
其中第5個大的元素為9
其中第6個大的元素為10
其中第7個大的元素為11
其中第8個大的元素為22

注：這段代碼每次運行的結果不同，因為每次運行的時候，計算過快，會導致部分數據值沒有計算出來，為了效率直接打印結果，所以需要在每次循環結束后加上system("pause")，但是這樣會導致程序運行時間變長，所以這里就不加了。

部分可能的結果如下

其中第0個大的元素為1
其中第1個大的元素為-1500844437
其中第2個大的元素為2
其中第3個大的元素為3
其中第4個大的元素為4
其中第5個大的元素為5
其中第6個大的元素為9
其中第7個大的元素為10
其中第8個大的元素為11