直接选择排序详解编程语言

选择排序算法就是每一趟从待排序的记录中选出关键字最小（最大）的记录，顺序放在已排好序的子文件的最后（最前），直到全部记录排序完毕。常见的选择排序有直接选择排序（Selection Sort），堆排序（Heap Sort），平滑排序（Smooth Sort），笛卡尔树排序（Cartesian Sort），锦标赛排序（Tournament Sort），循环排序（Cycle）。

1、直接选择排序
直接选择排序（Selection Sort），这是一种简单直观的排序算法。它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序的序列元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素排序完毕。

2、排序性能
最差时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
稳定性：不稳定

3、算法示意图：

4、解题思路
1）遍历整个数组。
2）创建临时变量存放基点元素和下标（指向最小值）。
3）从遍历基点元素的下一个元素开始遍历，如果小于临时变量元素，则交换数据和下标，否则一直遍历下去。
4）基点元素与临时变量交换数据。

5、实现的代码：

void SetectSort(int arr[], int len) 
{ 
	int i = 0; 
	int j = 0; 
	int k = 0; 
	int key = 0; 
	int tmp = 0; 
    //遍历整个数组，因为最后一个元素已确定，所以不需要遍历 
	for (i = 0; i < len - 1; i++) 
	{ 
		k = i;//创建临时变量存储要选择排序的最小数的下标 
		key = arr[i];//创建临时变量存储要排序的最小数 
		//遍历需要比较的元素，每次都从已序数列的下一个元素开始比较 
		for (j = i + 1; j < len; j++) 
		{ 
			//求出最小数和下标 
			if (arr[j] < key) 
			{ 
				k = j; 
				key = arr[j]; 
			} 
		} 
		if (k != i)//避免数字自己与自己比较 
		{   //交换 
			tmp = arr[i]; 
			arr[i] = arr[k]; 
			arr[k] = tmp; 
		}  
	} 
} 

5、程序

#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h> 
#include<stdlib.h> 
 
void SetectSort(int arr[], int len) 
{ 
	int i = 0; 
	int j = 0; 
	int k = 0; 
	int key = 0; 
	int tmp = 0; 
    //遍历整个数组，因为最后一个元素已确定，所以不需要遍历 
	for (i = 0; i < len - 1; i++) 
	{ 
		k = i;//创建临时变量存储要选择排序的最小数的下标 
		key = arr[i];//创建临时变量存储要排序的最小数 
		//遍历需要比较的元素，每次都从已序数列的下一个元素开始比较 
		for (j = i + 1; j < len; j++) 
		{ 
			//求出最小数和下标 
			if (arr[j] < key) 
			{ 
				k = j; 
				key = arr[j]; 
			} 
		} 
		if (k != i)//避免数字自己与自己比较 
		{   //交换 
			tmp = arr[i]; 
			arr[i] = arr[k]; 
			arr[k] = tmp; 
		}  
	} 
} 
void test3() 
{ 
	int arr[] = { 2,3,1,6,4,5 }; 
	int len = sizeof(arr) / sizeof(arr[0]); 
	SetectSort(arr, len); 
	for (int i = 0; i < len; i++) 
	{ 
		printf("% d", arr[i]); 
	} 
	printf("/n"); 
} 
 
int main() 
{ 
	test3(); 
	system("pause"); 
	return 0; 
} 

运行结果为：