【21t天算法挑战赛】排序算法——直接选择排序

​​💬💬作者有话想说：

💟作者简介：我目前是一个准大二学生，现在不敢说自己擅长什么，但是我想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜
 
☂️兴趣领域：目前偏向于前端学习 算法学习💜💜💜
 
🎬> 活动地址：CSDN21天学习挑战赛
 
💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜
 
🪀语言说明：代码实现我会用Python/C++~

一、直接选择排序

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;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 
#include"pch.h"
#include
#include
#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;
	}
	
}
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.6.优缺点

优点：

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

缺点：

比较次数多

持续更新中~~💜💜💜