1.介绍
选择排序算法属于内部排序算法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置达到排序的目的
时间复杂度:O(n^2) 双层for
2.思想
选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[0]~arr[n-1]中选取最小值,
与arr[0]交换,第二次从arr[1]~arr[n-1]中选取最小值,与arr[1]交换,第三次从arr[2]~arr[n-1]中选取最小值,与arr[2]交换,…,
第i次从arr[i-1]~arr[n-1]中选取最小值,与arr[i-1]交换,…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,
总共通过n-1次,得到一个按排序码从小到大排列的有序序列。
3.思路分析图
4.代码实现
namespace DataStructure { public class SelectSort { /// <summary> /// 测试 /// </summary> public static void Test() { int[] arr = { 101, 34, 119, 1 }; System.Console.WriteLine("排序的数组:" + ArrayToString(arr)); System.Console.WriteLine("\n优化后的数组排序"); Sort(arr); System.Console.WriteLine("\n优化前的数组排序"); arr = new int[] { 101, 34, 119, 1 }; { int minIndex = 0; int minValue = arr[minIndex]; for (int i = 1; i < arr.Length; i++) { if (minValue > arr[i]) { minIndex = i; minValue = arr[i]; } } if (minIndex != 0) { arr[minIndex] = arr[0]; arr[0] = minValue; } System.Console.WriteLine("\n第一次排序后的结果:" + ArrayToString(arr)); } { int minIndex = 1; int minValue = arr[minIndex]; for (int i = 1 + 1; i < arr.Length; i++) { if (minValue > arr[i]) { minIndex = i; minValue = arr[i]; } } if (minIndex != 1) { arr[minIndex] = arr[1]; arr[1] = minValue; } System.Console.WriteLine("\n第二次排序后的结果:" + ArrayToString(arr)); } { int minIndex = 2; int minValue = arr[minIndex]; for (int i = 1 + 2; i < arr.Length; i++) { if (minValue > arr[i]) { minIndex = i; minValue = arr[i]; } } if (minIndex != 2) { arr[minIndex] = arr[2]; arr[2] = minValue; } System.Console.WriteLine("\n第三次排序后的结果:" + ArrayToString(arr)); } } /// <summary> /// 将数组转换成String /// </summary> /// <param name="arr"></param> /// <returns></returns> public static string ArrayToString(int[] arr) { string result = ""; for (int i = 0; i < arr.Length; i++) { result += arr[i] + ","; } return result; } /// <summary> /// 选择排序算法封装 /// </summary> /// <param name="arr"></param> private static void Sort(int[] arr) { //要循环几次 for (int i = 0; i < arr.Length - 1; i++) { //假定最小值索引 int minIndex = i; //假定最小值 int minValue = arr[minIndex]; for (int j = i + 1; j < arr.Length; j++) { //说明假定的最小值不是最小 if (minValue > arr[j]) { //重置最小值索引 minIndex = j; //重置最小值 minValue = arr[j]; } } //如果最小值索引不是等于当前索引,即交换 if (minIndex != i) { //将原本最小值索引的值,交换成当前索引的值 arr[minIndex] = arr[i]; //将当前索引的值交换成最小值 arr[i] = minValue; } System.Console.WriteLine($"\n第{i + 1}次排序的结果:{ArrayToString(arr)}"); } } } }
5.效果演示图