排序算法之「选择排序(SelectionSort) 」

介绍

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
选择排序算法是在一组数中有选择的从大到小或者小到大进行排序,其逻辑是:

逻辑

在一组数据中从第一个数开始比较出该组数据中最小数,然后将其与第一个数互换位置,然后第二个数再依次从后面的数再进行比较,找出全数组中第二小的数,再与第二个数互换位置,剩余的数依次类推,即可得出数组的排序。列如:

数组{6,3, 5, 9, 4, 7, 8}

首先以[0 , 7)分别为上列数组元素的索引

第一次比较以i = 0(就是6的索引)将6与{3, 5, 9, 4, 7, 8}中的元素进行比较(如:6大于3,则将比较索引1赋值给i,再将 i = 1的数与后面的数进行比较),找出的最小值为3,则将3与6位置互换,依次就完成了选择排序算法的整个逻辑。

代码实现

Golnag:

func SelectionSort(arr []int) []int {
    for i := 0; i < len(arr); i++ {
        tag := i
        for j := i + 1; j < len(arr); j++ {
            if arr[tag] > arr[j] {
                tag = j
            }
        }
        arr[i], arr[tag] = arr[tag], arr[i]
    }
    return arr
}

测试:

func main() {
    arr := []int{2, 0, 44, 1, 2, 34, 32, 10}
    fmt.Println(SelectionSort(arr))  //打印:[0 1 2 2 10 32 34 44]

}

C++:

#include <iostream>

using namespace std;

template<typename T>
void selectionSort(T arr[], int n){

    for(int i = 0 ; i < n ; i ++){

        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

如下是测试:

int main() {

    // 测试模板函数,传入整型数组
    int a[10] = {2,6,12,32,54,77,53,45,31,200};
    selectionSort( a , 10 );
    for( int i = 0 ; i < 10 ; i ++ )
        cout<<a[i]<<" ";
    cout<<endl;

    // 测试模板函数,传入浮点数数组
    float b[4] = {4.4,3.3,2.2,1.1};
    selectionSort(b,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<b[i]<<" ";
    cout<<endl;

    // 测试模板函数,传入字符串数组
    string c[4] = {"D","C","B","A"};
    selectionSort(c,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<c[i]<<" ";
    cout<<endl;
    return 0;
}

其输出结果为:

selection_Sort(选择排序算法)

本作品采用《CC 协议》,转载必须注明作者和本文链接
刻意学习
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
118
粉丝
88
喜欢
173
收藏
245
排名:367
访问:2.6 万
私信
所有博文
社区赞助商