算法导论：c++选择算法

╰+哭是因爲堅強的太久メ 2022-06-04 08:06 204阅读 0赞

选择算法即给定数组A，选出第i个大的元素，区别于排序后选择这种比较慢的方法，选择算法不需要排序即可选出第i个大元素

### 基于随机快排选择算法 ###

![这里写图片描述][SouthEast]

#### 首先实现随机快排： ####

![这里写图片描述][SouthEast 1]  
随机快排就是在快排的基础上主元用随机数产生。

// 随机快速排序之随机选择替代主元
    int random_partition(int array[], int p, int r)
    {
        int i=(rand() % (r - p + 1)) + p;   //产生[p,r]之间的一个随机数i
        int temp = array[r];                //交换a[i]和a[r]
        array[r] = array[i];
        array[i] = temp;
        return quick_partition(array, p, r);    //返回划分结果
    
    }
    // 随机快速排序
    void random_quicksort(int array[], int p, int r) {
        if (p < r) {
            int q = random_partition(array, p, r);
            random_quicksort(array, p, q - 1);
            random_quicksort(array, q + 1, r);
        }
    }

调用快速排序用到的划分函数：

/*快排分割,p首端，r尾端,i控制小于,j控制大于*/
    int quick_partition(int array[], int p, int r)
    {
        int x = array[r];
        int i = p - 1; //注意i和p的初始值
        for (int j=p; j<r;j++)
        {
            if (array[j] < x) //小于则发生交换
            {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //交换分割点和最尾元素
        int temp = array[i+1];
        array[i + 1] = array[r];
        array[r] = temp;
        return i + 1; //返回分割点
    }

#### 然后按照书上写的调用随机快排实现随机选择： ####

//基于随机快排选出第i个大的元素
    int random_select(int array[], int p, int r,int i) {
        if (p == r) //只有一个元素
        {
            return array[p];
        }
        int q = random_partition(array, p, r);
        int k = q - p + 1;
        if (i < k) //在前面
        {
            return random_select(array, p, q-1, i);
        }
        else if(i>k)    //在后面
        {
            return random_select(array, q + 1, r, i-k);
        }
        else
        {
            return array[q];
        }
    }

#### 测试 ####

int main()
    {
        int array[6] = { 4,7,1,2,0,9 };
        cout << random_select(array, 0, 5,6);
    }

> 输出：9

[SouthEast]: /images/20220604/14d3b97c669e4f5fa7857415d2f5ffdc.png
[SouthEast 1]: /images/20220604/de30b54974c04b32ab21725b6ef1df03.png