排序算法——直接选择排序

一、直接选择排序

1.1.选择排序介绍

• 直接选择排序又称简单选择排序
• 整个过程就是每一趟都将无序区中的所有元素进行逐一比较，找到最小的元素，与无序区中的首个元素进行交换，有序区长度加1，无序区长度减1。
• 重复以上步骤，直到所有的元素均已排好。

1.2.选择排序思路

​
💡💡思路：

1. 将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录
2. 在第一趟无序区找到最小的一个数，排到有序区第一个，此时有序区加一个数字，无序区减少一个数字
3. 重复上述操作，直到无序区只剩下一个数字为止。

1.3.时间复杂度

• 第一次内循环比较n - 1次，然后是n-2次，n-3次，……，最后一次内循环比较1次。
• 共比较的次数是 (n - 1) + (n - 2) + … + 1，求等差数列和，得 (n - 1 + 1)* n / 2 = n^2 / 2。
• 舍去最高项系数，其时间复杂度为 O(n^2)。

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都是O(n^2)

1.4.空间复杂度

简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)

1.5.代码实现

C++代码：

void selectSort(vector<int>& sortVector)            
//选择排序，每一趟选择最小的元素从前往后放置
{
    for (int i = 0; i < sortVector.size(); i++)
    {
        int target = i;
        for (int j = i; j < sortVector.size(); j++)
        {
            if (sortVector[target] > sortVector[j])
            {
                target = j;
            }
            int temp = sortVector[target];
            sortVector[target] = sortVector[i];
            sortVector[i] = temp;
        }
    }
}

 
#include"pch.h"
#include<iostream>
#include<list>
#define N 10
using namespace std;
 
 
void SelectSort(int arr[], int n)
{
    int min, i, j;
    //每次循环，选择出一个最小键值
    for (i = 1; i < n-1; i++)
    {
        //假设第i个记录键值最小
        min = i;
        for (j = i+1; j <= n; j++)  
            if (arr[j]< arr[min])
               //记录下键值较小记录的下标
                min = j;
            if (min != i)
                   // 将最小键值记录和第i个记录交换
                swap(arr[min], arr[i]);         
    }
}
int main()
{
    //初始化
    int nums[N+1] = {5,8,2,24,1,9,4,27,11,6};
    //简单选择排序
    SelectSort(nums,10);
    //打印排序结果
    for (int i = 1; i <= N; i++)
    {
        cout << nums[i] << endl;
    }
    
}
 
 

python代码：

def selection_sort(array):
    # 外循环 选择出一个最小键值
    for i in range(len(array)-1):
        # 假设第i个记录键值最小
        min_index = i
        # 内层循环
        for j in range(i+1, len(array)):
            if array[j] < array[min_index]:
                min_index = j
        if min_index != i:
            # 交换
            array[i], array[min_index] = array[min_index], array[i]
    return array
 
 
if __name__ == '__main__':
    array = [5,8,2,24,1,9,4,27,11,6]
    print(selection_sort(array))

1.6.优缺点

优点：

移动数据的次数已知（n-1次)

缺点：

比较次数多