简单选择排序

红太狼 2022-07-31 16:04 194阅读 0赞

**选择排序法的初步思想来源：**  
冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人类似。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢？  
/*这段话我挺喜欢的，好算法就是这样，一个玩股票的高手*/

**简单选择排序法（Simple Selection Sort）**就是通过 n - i 次关键字间的比较，从 n - i + 1 个记录中选出关键字最小 或 最大的记录，并和第 i（1 <= i <= n）个记录交换。

其时间复杂度为：O（n^2）  
其比较次数，无论最好还是最坏都是一样的，  
交换次数的话，最好，交换0次，最坏交换 n - 1次。

代码及结果如下：

#include <iostream>
    
    using namespace std;
    
    const int MAX_SIZE = 10;
    
    class Base{
    private:
        int r[MAX_SIZE];     /**待排序数列存放处**/
        int length;          /**顺序表长度，即数据元素个数**/
    public:
        Base()
        {
            r[0] = 1;
            r[1] = 2;
            r[2] = 0;
            r[3] = 5;
            r[4] = 8;
            r[5] = 9;
            r[6] = 7;
            r[7] = 3;
            r[8] = 6;
            r[9] = 4;
            length = 10;
        }
        void swap_data(Base &ob,int i,int j);
        void Show(const Base &ob);
        friend int Select_sort(Base &ob);    /**简单选择排序函数1**/
        friend int Select_sort1(Base &ob);   /**简单选择排序函数2**/
    };
    
    void Base::swap_data(Base &ob,int i,int j)  /**用于交换两个数据**/
    {
        int temp;
        temp = ob.r[i];
        ob.r[i] = ob.r[j];
        ob.r[j] = temp;
    }
    
    void Base::Show(const Base &ob)         /**用于输出数据**/
    {
        int i;
        for(i = 0;i < ob.length;i++)
            cout << ob.r[i] << ' ';
        cout << endl;
    }
    
    /**每一轮循环中都找到最小的那个数据，和 i 位置的数据交换**/
    int Select_sort(Base &ob)        /**将小的数据放前面**/
    {
        int i,j;
        int min;                     /**min的作用是保存一轮循环中最小的那个数据**/
        for(i = 0;i < ob.length - 1;i++)
        {
            min = i;
            for(j = i + 1;j < ob.length;j++)
            {
                if(ob.r[min] > ob.r[j])
                    min = j;        /**保存最小那个数的下标**/
            }
            if(i != min)
            {
                ob.swap_data(ob,i,min);  /**一轮下来只交换一个数据**/
            }
        }
        return 0;
    }
    
    /**每一轮循环中都找到最大的那个数据，和 i 位置的数据交换**/ 
    int Select_sort1(Base &ob)      /**将大的数据放前面**/
    {
        int i,j;
        int max;                    /**max的作用是保存一轮循环中最大的那个数据**/
        for(i = 0;i < ob.length - 1;i++)
        {
            max = i;
            for(j = i + 1;j < ob.length;j++)
            {
                if(ob.r[max] < ob.r[j])
                    max = j;        /**保存最大那个数的下标**/
            }
            if(i != max)
            {
                ob.swap_data(ob,i,max);  /**一轮下来只交换一个数据**/
            }
        }
        return 0;
    }
    
    int main()
    {
        Base ob1;
        cout << "排序前的数列: " << endl;
        ob1.Show(ob1);
    
        Select_sort(ob1);
        cout << "简单选择排序后的数列（小的放前面）: " << endl;
        ob1.Show(ob1);
    
        Select_sort1(ob1);
        cout << "简单选择排序后的数列（大的放前面）: " << endl;
        ob1.Show(ob1);
    
        return 0;
    }

![这里写图片描述][20150612142258375]  
/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150612142258375]: /images/20220801/07df7f9ab540457783f94da95c38c766.png