【21天算法学习】直接选择排序

作者简介：
🍀姓姜，字君竹。
🍁浅薄观点：科以载文，文以载道
🌱软件技术升计科，计划考研
🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡​​​

1. 概念及介绍
     直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

2. 时间空间复杂度
     在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n - i次比较 (1 <= i <= n-1)，而每次交换最多需要3次移动，因此，总的比较次数C = (n*n - n)/2；
     总的移动次数3(n-1)，由此可知，直接选择排序的时间复杂度为 O(n2) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些；
     对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)；
     由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

3. 图解
   

4. 代码实现

int main() {
	int a[] = { 22,45,21,23,54,76,8,67,67 };
	int sz = sizeof(a) / sizeof(a[0]);
	int i = 0;
	for(i = 0; i < sz - 1; i++){
		int k = i;
		int j = 0;
		for (j = i + 1; j < sz; j++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		if (k != i) {
			int tmp = a[i];
			a[i] = a[k];
			a[k] = tmp;
		}
	}
	for (i = 0; i < sz; i++) {
		printf("%d ", a[i]);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。