博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
八大排序之选择排序
阅读量:2242 次
发布时间:2019-05-09

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

思想:

每一趟都从待排序的数列中选择一个最大(最小)的,放在数列的最后一个位置(或起始位置)直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

图解:

例:9 5 3 4 6 2 8 1 7 0

这里写图片描述

#include 
#include
void Swap(int *p1, int *p2){ int tmp = *p1; *p1 = *p2; *p2 = tmp;}void select_sort(int arr[], int len){ for (int i = 0; i < len - 1; i++) //表示趟数 { int maxPos = 0; for (int j = 1; j < len - i; j++) { if (arr[j] > arr[maxPos]) { maxPos = j; } } if (maxPos != len - 1 - i) //如果最大的元素就是在最后位置,就不用交换 { Swap(arr + maxPos, arr + (len - 1 - i)); } }}int main(){ int arr[] = { 9,5,3,4,6,2,8,1,7,0 }; int len = sizeof(arr) / sizeof(arr[0]); select_sort(arr, len); for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } system("pause"); return 0;}
优化:

选择排序的每一趟记录最大值,我们是不是可以在一趟中,把最小值和最大值都记录下来,这样就可以只完成一半的工作

这里写图片描述

void Swap(int *p1, int *p2)	{		int tmp = *p1;		*p1 = *p2;		*p2 = tmp;	}		void select_sort(int arr[], int len)	{		int left = 0;		int right = len - 1;		while (left < right)		{			int minPos = left;			int maxPos = left;			for (int i = left; i < len - left; i++)			{				if (arr[i] < arr[minPos])				{					minPos = i;				}				if (arr[i] > arr[maxPos])				{					maxPos = i;				}			}			//这个if是为了判断第一个元素是不是最大的,因为如果第一个元素是最大的,会将最大的元素换位置			//比如,上述中的第一步,9是最大的,如果9和0换位置,但maxPos仍然是0,这是第一个元素就变为了0,			//maxPos却没有发生变化,再将最大的元素和最后一个元素换位置,就会是0和最后一个元素换位置,而不是最大的元素			//所以这种情况就要先将换后的位置赋值给maxPos			Swap(arr + minPos, arr + left);			if (maxPos == left)			{				maxPos = minPos;			}			Swap(arr + maxPos, arr + right);			left++;			right--;		}	}
时间复杂度: O(n^2)
你可能感兴趣的文章
Oracle_spatial的空间操作符
查看>>
SDO_GEOMETRY结构说明
查看>>
oracle 的 SDO_GEOMETRY
查看>>
往oracle中插入geometry的两种方式
查看>>
Oracle Spatial中的Operator操作子 详细说明
查看>>
Oracle Spatial中SDO_Geometry详细说明
查看>>
oracle 聚合函数 LISTAGG ,将多行结果合并成一行
查看>>
Oracle列转行函数 Listagg() 语法详解及应用实例
查看>>
LISTAGG函数的用法
查看>>
Oracle Spatial操作geometry方法
查看>>
IDEA类和方法注释模板设置(非常详细)
查看>>
Java程序初始化的顺序
查看>>
Dubbo和Spring结合配置文件内容解析为bean的过程
查看>>
fastJson注解@JSONField使用的一个实例
查看>>
fastjson的@JSONField注解的一点问题
查看>>
fastjson使用(三) -- 序列化
查看>>
浅谈使用单元素的枚举类型实现单例模式
查看>>
Java 利用枚举实现单例模式
查看>>
Java 动态代理作用是什么?
查看>>
Java动态代理机制详解(JDK 和CGLIB,Javassist,ASM) (清晰,浅显)
查看>>