三种方法实现选择问题

深碍√TFBOYSˉ_ 2022-12-13 11:24 105阅读 0赞

一、选择问题  
选择问题（selection problem）是求一数组(n个数)中第k(k <= n)个最小元素的问题。

二、三种方法实现  
1.确定算法  
①Lomuto划分  
②Hoare划分  
2.非确定算法(概率算法)  
③sherwood算法

三、Lomuto划分1  
代码：

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    void swap(int* a, int* b) {
        
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int Lomuto(int _array[], int l, int r) {
        
        int i = l;
        for(int j = l + 1; j <= r; j++) {
        
            if(_array[j] < _array[l]) swap(&_array[++i], &_array[j]);
        }
        swap(&_array[i], &_array[l]);
        return i;
    }
    
    int Selection(int _array[], int l, int r, int _k) {
        
        int mid = Lomuto(_array, l, r);
        if(mid == (l + _k - 1)) return _array[mid];
        else if(mid > (l + _k - 1)) Selection(_array, l, mid - 1, _k);
        else Selection(_array, mid + 1, r, _k - (mid - l + 1));
    }
    
    int main() {
        
        //input
        int array[] = {
        4, 5, 2, 3, 6, 1, 7}, k = 3;
        int len = sizeof(array) / sizeof(array[0]);
    
        //选出第k个最小元素
        int ans = Selection(array, 0, len - 1, k);
    
        //output
        printf("第%d个最小元素：%d", k, ans);
        return 0;
    }

结果：  
![在这里插入图片描述][20201011095643799.png_pic_center]  
四、Hoare划分2  
代码：

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    void swap(int* a, int* b) {
        
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int Hoare(int _array[], int l, int r) {
        
        int temp = _array[l];
        while(l < r) {
        
            while(l < r && _array[r] > temp) r--;
            _array[l] = _array[r];
            while(l < r && _array[l] <= temp) l++;
            _array[r] = _array[l];
        }
        _array[l] = temp;
        return l;
    }
    
    
    int Selection(int _array[], int l, int r, int _k) {
        
        int mid = Hoare(_array, l, r);
        if(mid == (l + _k - 1)) return _array[mid];
        else if(mid > (l + _k - 1)) Selection(_array, l, mid - 1, _k);
        else Selection(_array, mid + 1, r, _k - (mid - l + 1));
    }
    
    int main() {
        
        //input
        int array[] = {
        4, 5, 2, 3, 6, 1, 7}, k = 3;
        int len = sizeof(array) / sizeof(array[0]);
    
        //选出第k个最小元素
        int ans = Selection(array, 0, len - 1, k);
    
        //output
        printf("第%d个最小元素：%d", k, ans);
        return 0;
    }

> 和“三、Lomuto划分”的代码相比，仅仅改变**划分的代码**即可

五、sherwood算法  
动机：以上两种划分方式，都是选择第一个数作为划分元，但是如果初始数组已经是递增或递减的顺序，则时间复杂度就增大了。

为解决这一问题，在划分之前打乱数组的初始顺序，即洗牌(shuffle)

#include <iostream>
    #include <cstdio>
    #include <random>
    #include <ctime>
    using namespace std;
    
    void Print(int _array[], int _len) {
        
        for(int i = 0; i < _len; i++) {
        
            printf("%d", _array[i]);
            if(i != _len - 1) printf(" ");
            else printf("\n");
        }
    
    }
    
    void swap(int* a, int* b) {
        
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int uniform(int n) {
        
        return rand() % n;
    }
    
    void Shuffle(int _array[], int _len) {
        
        for(int i = 0; i < _len; i++) {
        
            int j = uniform(_len);
            swap(&_array[i], &_array[j]);
        }
    }
    
    int main() {
        
        //input
        int array[] = {
        1, 2, 3, 4, 5, 6, 7};
        int len = sizeof(array) / sizeof(array[0]);
        printf("数组的初始序列：");
        Print(array, len);
    
        //洗牌
        srand((unsigned)time(NULL));
        Shuffle(array, len);
    
        //output
        printf("数组的洗牌后序列：");
        Print(array, len);
        return 0;
    }

结果：  
![在这里插入图片描述][20201011105401886.png_pic_center]  
六、扩展阅读

--------------------

1.  [选择问题（求第k个最小元素）][k] ↩︎
2.  [hoare划分][hoare] ↩︎

[20201011095643799.png_pic_center]: /images/20221123/5604d55d5f8f432284031b6476abfff1.png
[20201011105401886.png_pic_center]: /images/20221123/23d81fbc25964d41881c0fb222911c94.png
[k]: https://blog.csdn.net/longintchar/article/details/80470407
[hoare]: https://www.cnblogs.com/littlepage/p/11662266.html