人工智能排序算法(5):简单选择排序 人工智能算法大全_AI算法 第1张

一、前言

简单选择排序是一种选择排序

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

二、算法思想

简单排序很简单,它的大致处理流程为:

  • 从待排序序列中,找到关键字最小的元素;

  • 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;

  • 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。

动态效果示意图:

 人工智能排序算法(5):简单选择排序 人工智能算法大全_AI算法 第2张

举例说明,处理过程示意图如下所示:

 人工智能排序算法(5):简单选择排序 人工智能算法大全_AI算法 第3张

如图所示,每趟排序中,将当前 i 小的元素放在位置 i 上。

1、代码

C++:

C++


#include <iostream>#include <vector> using namespace std; // 简单选择排序vector<int> SelectSort(vector<int> list){    // 需要遍历获得最小值的次数    // 要注意一点,当要排序 N 个数,已经经过 N-1 次遍历后,已经是有序数列    vector<int> result = list;    for (int i = 0; i < result.size(); i++){        // 用来保存最小值得索引        int index = i;        // 用来保存最小值得索引        for (int j = i + 1; j < result.size(); j++){            if (result[index] > result[j]){                index = j;            }        }        if (index == i){            continue;        }        // 将找到的第i个小的数值放在第i个位置上        swap(result[i], result[index]);        cout << "第" << i + 1<< "趟:\t";        for (int i = 0; i < result.size(); i++){            cout << result[i] << " ";        }        cout << endl;    }    return result;} void main(){    int arr[] = { 6, 4, 8, 9, 2, 3, 1 };    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));    cout << "排序前" << endl;    for (int i = 0; i < test.size(); i++){        cout << test[i] << " ";    }        cout << endl;    vector<int> result;    result = SelectSort(test);    cout << "排序后" << endl;    for (int i = 0; i < result.size(); i++){        cout << result[i] << " ";    }    cout << endl;     system("pause");}


运行结果:

 人工智能排序算法(5):简单选择排序 人工智能算法大全_AI算法 第4张

Python:

Python


# -*- coding:utf-8 -*- def SelectSort(input_list):    '''    函数说明:简单选择排序(升序)    Author:        www.cuijiahua.com    Parameters:        input_list - 待排序列表    Returns:        sorted_list - 升序排序好的列表    '''        if len(input_list) == 0:        return []    sorted_list = input_list    length = len(sorted_list)    for i in range(length):        min_index = i        for j in range(i + 1, length):            if sorted_list[min_index] > sorted_list[j]:                min_index = j        if min_index == i:            continue        temp = sorted_list[i]        sorted_list[i] = sorted_list[min_index]        sorted_list[min_index] = temp    return sorted_list if __name__ == '__main__':    input_list = [6, 4, 8, 9, 2, 3, 1]    print('排序前:', input_list)    sorted_list = SelectSort(input_list)    print('排序后:', sorted_list)

运行结果同上。

三、算法分析

1、简单算法排序性能

 人工智能排序算法(5):简单选择排序 人工智能算法大全_AI算法 第5张

其中,N2为N^2。

2、时间复杂度

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数总是N (N - 1) / 2

而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0.

当序列反序时,移动次数最多,为3N (N - 1) /  2。

所以,综合以上,简单排序的时间复杂度为 O(N^2)

3、空间复杂度

简单选择排序需要占用 1 个临时空间,用于保存最小值得索引。