十大经典排序算法之三--选择排序

1、选择排序

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2、算法描述

选择排序算法通过选择和交换来实现排序，其排序流程如下：

• 首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
• 接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换
• 然后，这样不断重复，直到最后两个数据完成交换。最后，便完成了对原始数组的从小到大的排序。

3、动画演示

4、过程实例

假如给定初始数据：（118，101，105，127，112）

一次排序：101，118，105，127，112

二次排序：101，105，118，127，112

三次排序：101，105，112，127，118

四次排序：101，105，112，118，127

每一趟在 n-i+1(i=1,2,...,n-1) 个记录中选取关键字最小的记录作为有序序列中第i个记录。具体来说，假设长度为 n 的数组 arr，要按照从小到大排序，那么先从 n 个数字中找到最小值 min1，如果最小值 min1 的位置不在数组的最左端(也就是 min1 不等于 arr[0] )，则将最小值 min1 和 arr[0] 交换，接着在剩下的 n-1 个数字中找到最小值 min2，如果最小值 min2 不等于 arr[1]，则交换这两个数字，依次类推，直到数组 arr 有序排列。算法的时间复杂度为 O(n^2)。

5、算法实例

#include "stdio.h"

void select_sort(int* arr, int e)
{
	int k = 0, temp = 0;
	for (int i = 0; i < e - 1; i++)
	{
		k = i;
		for (int j = i + 1; j < e; j++)
		{
			if (arr[j] < arr[k])
			{
				k = j;
			}
		}
		if (k != i)
		{
			temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}

	}
}

void print(int* arr, int e)
{
	for (int i = 0; i < e; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[10] = { 25,8,79,5,4,15,3,88,14,56 };

	select_sort(arr, 10);
	print(arr, 10);

	return 0;
}