排序算法之简单选择排序

清疚 2022-08-20 14:19 174阅读 0赞

# 排序算法之简单选择排序 #

这一系列主要讲的是排序算法，首先会简单介绍各种排序算法的基本思想，然后会给出每种算法的Python实现和C++实现,代码中均有非常详细的注释。最后会给出不同算法的复杂度分析。

文中Python代码是在`Python3.4.3或 Python3.2`上实现的，C++代码是在`Dev-C++5.7.1`上实现的。如果有什么不清楚或者不对的地方，欢迎大家随时指正。

**简单选择排序的基本思想是**：通过`n-i`次关键字间的比较，从`n-i+1`个元素中选出值最小的元素，并和第`i(1<=i<=n)`个元素交换。  
**Python代码实现**：

import numpy as np
    
    def SimpleSelectionSort(unSortedArray):
        length = len(unSortedArray)    #获取待排序数组的长度
    
        for i in range(length):
            minIndex = i   #每层循环初始化较小值索引为当前元素索引
    
            for j in range(i+1, length):
    
                if unSortedArray[minIndex] > unSortedArray[j]:  #比较，得到较小值
                    minIndex = j   #记录较小值的索引
    
            if(i != minIndex):     #如果不相等，说明找到了比当前元素小的元素，交换
                temp = unSortedArray[i]
                unSortedArray[i] = unSortedArray[minIndex]
                unSortedArray[minIndex] = temp
    
        return unSortedArray
    
    #算法验证
    unSortedArray = np.array([2,7,1,5,9,3,10,18,6])
    print("The original data is: ",unSortedArray)
    print("The sorted data is: ",SimpleSelectionSort(unSortedArray))

运行结果为：

>>> ================================ RESTART ================================
    >>>
    The original data is: [ 2 7 1 5 9 3 10 18 6]
    The sorted data is: [ 1 2 3 5 6 7 9 10 18]

**C++代码实现**：

#include <iostream>
    
    using namespace std;
    
    //交换两个元素，形参为引用形参
    void swap(int &a, int &b)
    {
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
    
    //简单选择排序：输入待排序数组和数组长度，因为形参是指针，所以改变的是原数组
    void SimpleSelectionSort(int *a, int length)
    {
        for(int i = 0; i < length-1; ++i)
        {
            int minIndex = i;                    //每次初始化最小值索引为当前索引，从0开始
            for(int j = i+1; j <= length-1; ++j)
            {
                if(a[minIndex] > a[j])           //比较，找出较小值并记录其索引
                {
                    minIndex = j;
                }
            }
    
            if(i != minIndex)                     //如果不相等，说明找到了比当前元素小的元素，则交换
            {
                swap(a[i], a[minIndex]);
            }
        }
    }
    
    int main(int argc, char** argv) {
    
        int originalArray[] = {
       2,7,1,5,9,3,10,18,6};
        int length = sizeof(originalArray)/sizeof(int);          //计算数组长度
    
        cout << "The length of the array is " << length << endl;
        cout << "The original array is: ";
        for(int i = 0; i <= length-1; i++)                       //打印待排序数组元素
        {
            cout << originalArray[i] << static_cast<char>(32);   //32是空格的ASCII值，把它转换成空格输出
        }
        cout << endl;
    
        SimpleSelectionSort(originalArray,length);               //调用排序算法
        cout << "The sorted array is: ";
        for(int i = 0; i <= length-1; i++)                       //打印排序结束之后的数组元素
        {
            cout << originalArray[i] << static_cast<char>(32);
        }
        return 0;
    }

运行结果为：

The length of the array is 9
    The original array is: 2 7 1 5 9 3 10 18 6
    The sorted array is: 1 2 3 5 6 7 9 10 18

**简单选择排序的算法复杂度**：  
无论是最好还是最差的情况，简单选择排序的比较次数都是一样多，即`n(n-1)/2`次；对于交换次数，最好为0次，最差为`n-1`次。由于最终的排序时间是比较与交换的次数总和，因此，其总的时间复杂度为`O(n^2)`。

[排序算法之冒泡排序][Link 1]

[Link 1]: http://blog.csdn.net/qq_33256568/article/details/50760971