C语言实现选择排序

原文链接：C语言实现选择排序
发布时间：2021-10-13 23:11:52

文章目录

算法描述

  • 第一步，找到数组中最小的数据，把它和第一个数据交换位置
  • 第二步，在剩余数据中，找到最小的数据，把它和第二个数据交换位置
  • 如此不断地重复，直到所有的数据排好顺序

因为这种算法，总是在剩余数据中选择最小的数据，所以叫做选择排序。

C语言代码实现

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
#include <stdio.h>

void SelectSort(int data[], int len) {
	for (int i = 0; i < len; i++) {
		int min = i;
		for (int j = i + 1; j < len; j++) {
			if (data[j] < data[min]) {
				min = j;
			}
		}
		int temp = data[i];
		data[i] = data[min];
		data[min] = temp;
	}
	return;
}

int main()
{
	int arr[5] = { 4,5,10,3,20 };
	SelectSort(arr, 5);
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		printf("%d,", arr[i]);
	}
	printf("\n");
	return 0;
}

算法特点

  • 不稳定的排序算法 因为交换位置，打乱了相对顺序。
  • 运行时间和输入无关 没有利用数据的输入状态，就算输入是已经有序的数组，排序时间仍然不会缩短，却和无序数组所需要的时间一样长。
  • 数据移动最少 即总共使用N次交换。

时间复杂度

对于长度为N的数组，需要

  • 交换次数：N
  • 比较次数：(N-1) + (N-2) + … + 1 = N(N-1)/2

所以，时间复杂度是：O(N²)