本文共 1264 字，大约阅读时间需要 4 分钟。

1.直接选择排序的算法思想

• 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。

2.简单总结直接选择排序的基本思路

• a.在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素.

• b.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换.

• c.在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素.

• 直接选择排序图解

  

• 以升序为例基本代码实现如下（为了更好优化直接选择排序，我在这里实现了同时找最大和最小的数据元素）：

void Slect_Sort(int* arr, int n){
   	int begin = 0;	int end = n - 1;	int min_num;	int max_num;	while (begin <= end)	{
   		min_num = max_num = begin;		for (int i = begin + 1; i <= end; i++)		{
   			if (arr[i] < arr[min_num])			{
   				min_num = i;			}			if (arr[i]>arr[max_num])			{
   				max_num = i;			}		}		Swap(&arr[begin], &arr[min_num]);		//记住这个条件不能丢，不然的话会出错！！！		//如果逆序的话没有这个条件就不对。		if (max_num == begin)		{
   			max_num = min_num;		}		Swap(&arr[end], &arr[max_num]);		begin++;		end--;	}}void SlectSort_test(){
   	int arr[] = {
    4, 3, 2, 8, 0, 9, 7, 8, 5, 4, 8, 9, 5, 6, 4 };	int n = sizeof(arr) / sizeof(int);	Slect_Sort(arr, n);	printf("选择排序结果：");	for (int i = 0; i < n; i++)	{
   		printf("%d ", arr[i]);	}	printf("\n");}int main(){
       slectSort_test();	system("pause");	return 0;}

3.直接选择排序的特性总结

• 时间复杂度分析

  ①：最优情况下时间复杂度：O( n^2 ).

  ②：最差情况下时间复杂度：O( n^2 ).

• 空间复杂度分析

  直接选择排序空间复杂度为：O( 1 ).

• 稳定性分析

  直接选择排序不是稳定的排序，同时直接选择排序非常好理解，但是效率不是很好，实际中很少使用。

转载地址：http://srwbb.baihongyu.com/