分治法实验-寻找第k小元素

梦里梦外; 2022-07-16 00:18 181阅读 0赞

# 问题描述 #

随机生成含有n个不同元素的数组L（n≥10000），要求找出第k小的元素（k≤n），完成下面的任务：  
（1）设计一个基于排序选择算法程序，编程调试正确（排序算法自己确定）。  
（2）设计一个时间复杂度为O(n)的选择算法，编程调试正确。  
（3）从理论上分析上述两种算法的时间复杂度，并且通过实际数据计算验证理论分析结果。  
（4）写出实验报告。

# 问题分析 #

1、找出序列中的第k小元素，并将时间复杂度降低到O(n)，我们首先想到的方法是利用排序，比如冒泡排序、选择排序，只排到第k小就截止，此时时间复杂度应为O(n^2 )，并不符合要求。  
2、根据分治法思想，有如下思路：  
对于集合A\[1…n\]中的元素，用其中某元素V进行划分:  
![A\_1=\{a|a<V & a∈A\},][A_1_a_a_V _ a_A]  
![A\_2=\{a|a=V & a∈A\},][A_2_a_a_V _ a_A]  
![A\_3=\{a>V &a∈A\}。][A_3_a_V _a_A]  
if ![|A\_1 |>k][A_1 _k] ，问题归结为在A\_1中找第k小元素  
else if ![|A\_1 |+|A\_2 |≥k][A_1 _A_2 _k] ，V就是第K小元素  
else if ![|A\_1 |+|A\_2 |<k][A_1 _A_2 _k 1] ，问题归结为在A\_3中寻找第 ![k-|A\_1 |-|A\_2 |][k-_A_1 _-_A_2] 小元素。  
对于第一、三中情况，只需要进行递归即可。  
3、时间复杂度分析，设T(n)为n元数组的时间复杂度  
最坏情况下:  
T(n)=T(n-1)+n-1  
解得：T(n)=O(n^2 )  
一般情况下：  
T(n)=T(n/2)+n-1  
解得：T(n)=O(n)

# 相关代码 #

int quickOnce(int *theArray, int left, int right)       // 快排的单次划分过程
    {
        int value = theArray[left];
        int l = left, r = right;
        while (l < r)
        {
            while (l<r && theArray[r]>value)
                r--;
            if (l < r)
            {
                theArray[l] = theArray[r];
                l++;
            }
            while (l < r && theArray[l] < value)
                l++;
            if (l < r)
            {
                theArray[r] = theArray[l];
                r--;
            }
        }
        theArray[l] = value;
        return l;
    }
    
    int quickFind(int * theArray, int left, int right, int k)   //参数均为下标
    {
        int index = quickOnce(theArray, left, right);   // 执行一次划分操作
        if (index < k)          // |A1|+|A2|<k 情况
        {
            return quickFind(theArray, index+1, right, k);
        }
        else if (index > k)     // |A1|>=k情况
        {
            return quickFind(theArray, left, index, k);
        }
        else                    // index正好是分界时
        {
            return theArray[index];
        }
    
    }

[A_1_a_a_V _ a_A]: /images/20220716/7311e5871f6f46a78f0f8108b73105dc.png
[A_2_a_a_V _ a_A]: /images/20220716/76a2e60ac42a4fb48df26fdd9fd46889.png
[A_3_a_V _a_A]: /images/20220716/bad8ce559e5a497ca5d5884a4e183ca1.png
[A_1 _k]: /images/20220716/d8a950e5a6bb4eca98d6d9ab4bde38b9.png
[A_1 _A_2 _k]: /images/20220716/d592ad82c5814ab0b4a93517db45c0b0.png
[A_1 _A_2 _k 1]: https://img-blog.csdn.net/20160924180100847
[k-_A_1 _-_A_2]: /images/20220716/004d73fe6c4e498886ec939d741c2b53.png