16.排序-选择排序
16.1 知识点
选择排序的基本原理
选择排序的基本原理是通过依次比较数组中的元素，找出极值（最大或最小），然后将其放入目标位置。每一轮都在未排序区找到极值和未排序区的第一个元素进行交换，排序区容量逐渐增加，未排序区容量逐渐减少，最终完成排序。
选择排序代码实现过程
第一步：声明一个中间商来记录索引
每一轮开始，默认第一个元素是极值：
int index = 0;
第二步：依次比较
比较轮数的目的是排除上一轮已经放好位置的数：
for (int n = 1; n < arr.Length - 比较轮数; n++)
{
// 比较
}
第三步：找出极值（最大值）
int index = 0;
for (int n = 1; n < arr.Length; n++)
{
if (arr[index] < arr[n])
{
index = n;
}
}
第四步：放入目标位置
如果当前极值所在位置就是目标位置，则无需交换：
if (index != arr.Length - 1 - 比较轮数)
{
int temp = arr[index];
arr[index] = arr[arr.Length - 1 - 比较轮数];
arr[arr.Length - 1 - 比较轮数] = temp;
}
第五步：比较m轮
for (int m = 0; m < arr.Length; m++)
{
int index = 0;
for (int n = 1; n < arr.Length - m; n++)
{
if (arr[index] < arr[n])
{
index = n;
}
}
if (index != arr.Length - 1 - m)
{
int temp = arr[index];
arr[index] = arr[arr.Length - 1 - m];
arr[arr.Length - 1 - m] = temp;
}
}
选择排序最终代码
for (int m = 0; m < arr.Length; m++)
{
int index = 0;
for (int n = 1; n < arr.Length - m; n++)
{
if (arr[index] < arr[n])
{
index = n;
}
}
if (index != arr.Length - 1 - m)
{
int temp = arr[index];
arr[index] = arr[arr.Length - 1 - m];
arr[arr.Length - 1 - m] = temp;
}
}
打印出排序后的数组
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " "); // 输出：1 2 3 4 5 6 7 8 9
}
总结
- 基本概念： 新建中间商，依次比较，找出极值，放入目标位置，比较n轮。
- 套路写法： 两层循环，外层轮数，内层寻找，初始索引，记录极值，内层循环外交换。
16.2 知识点代码
using System;
namespace Lesson14_选择排序
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("选择排序");
#region 知识点一 选择排序基本原理
// 8 7 1 5 4 2 6 3 9
// 新建中间商
// 依次比较
// 找出极值（最大或最小）
// 放入目标位置
// 比较n轮
#endregion
#region 知识点二 选择排序代码实现过程
//实现升序 把 大的 放在最后面
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
//第一步 声明一个中间商 来记录索引
//每一轮开始 默认第一个都是极值
//int index = 0;
//第二步 依次比较
// -比较轮数的目的 是排除上一轮 已经放好位置的数
//int index = 0;
//for (int n = 1; n < arr.Length - 比较轮数; n++)
//{
//}
//第三步 找出极值（最大值）
//int index = 0;
//for (int n = 1; n < arr.Length; n++)
//{
// if (arr[index] < arr[n])
// {
// index = n;
// }
//}
//第四步 放入目标位置
//Length - 1 - 比较轮数
//如果当前极值所在位置 就是目标位置 那就没必要交换了
//if (index != arr.Length - 1 - 比较轮数)
//{
// int temp = arr[index];
// arr[index] = arr[arr.Length - 1 - 比较轮数];
// arr[arr.Length - 1 - 比较轮数] = temp;
//}
//第五步 比较m轮
//for (int m = 0; m < arr.Length; m++)
//{
// int index = 0;
// for (int n = 1; n < arr.Length - m; n++)
// {
// if (arr[index] < arr[n])
// {
// index = n;
// }
// }
// if (index != arr.Length - 1 - m)
// {
// int temp = arr[index];
// arr[index] = arr[arr.Length - 1 - m];
// arr[arr.Length - 1 - m] = temp;
// }
//}
#endregion
#region 知识点三 选择排序最终代码
// 选择排序最终代码
for (int m = 0; m < arr.Length; m++)
{
int index = 0;
for (int n = 1; n < arr.Length - m; n++)
{
if (arr[index] < arr[n])
{
index = n;
}
}
if (index != arr.Length - 1 - m)
{
int temp = arr[index];
arr[index] = arr[arr.Length - 1 - m];
arr[arr.Length - 1 - m] = temp;
}
}
//打印出排序后的数组
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");//1 2 3 4 5 6 7 8 9
}
#endregion
//总结
//基本概念
// 新建中间商
// 依次比较
// 找出极值
// 放入目标位置
// 比较n轮
//套路写法
//两层循环
//外层轮数
//内层寻找
//初始索引
//记录极值
//内存循环外交换
}
}
}
16.3 练习题
定义一个数组，长度为20，每个元素值随机0~100的数，使用选择排序进行升序排序或降序排序并打印
声明随机数组
int[] array = new int[20];
Random r = new Random();
for (int i = 0; i < array.Length; i++)
{
array[i] = r.Next(0, 101);
Console.Write(array[i] + " ");//82 12 70 51 13 25 17 89 41 94 52 96 49 20 18 59 45 80 91 83
}
Console.WriteLine();
进行选择排序
//套路写法
//两层循环
int index;
int temp;
//外层轮数
for (int i = 0; i < array.Length; i++)
{
//初始索引
index = 0;
//内层寻找
for (int j = 1; j < array.Length - i; j++)
{
//记录极值
//这里决定了 找到极值的种类
//只需要改这的条件 就可以改变 降序还是升序
//if (array[index] < array[j])
if (array[index] > array[j])
{
index = j;
}
}
//内层循环外交换
if (index != array.Length - 1 - i)
{
temp = array[index];
array[index] = array[array.Length - 1 - i];
array[array.Length - 1 - i] = temp;
}
}
打印排序后的结果
for (int i = 0; i < array.Length; i++)
{
Console.Write(array[i] + " ");//96 94 91 89 83 82 80 70 59 52 51 49 45 41 25 20 18 17 13 12
}
Console.WriteLine();
16.4 练习题代码
using System;
namespace Lesson14_练习题
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("选择排序练习题");
#region 练习题一
//定义一个数组，长度为20，每个元素值随机0~100的数，使用选择排序进行升序排序或降序排序并打印
//声明随机数组
int[] array = new int[20];
Random r = new Random();
for (int i = 0; i < array.Length; i++)
{
array[i] = r.Next(0, 101);
Console.Write(array[i] + " ");//82 12 70 51 13 25 17 89 41 94 52 96 49 20 18 59 45 80 91 83
}
Console.WriteLine();
//进行选择排序
//套路写法
//两层循环
int index;
int temp;
//外层轮数
for (int i = 0; i < array.Length; i++)
{
//初始索引
index = 0;
//内层寻找
for (int j = 1; j < array.Length - i; j++)
{
//记录极值
//这里决定了 找到极值的种类
//只需要改这的条件 就可以改变 降序还是升序
//if (array[index] < array[j])
if ( array[index] > array[j] )
{
index = j;
}
}
//内层循环外交换
if( index != array.Length - 1 - i )
{
temp = array[index];
array[index] = array[array.Length - 1 - i];
array[array.Length - 1 - i] = temp;
}
}
//打印排序后的结果
for (int i = 0; i < array.Length; i++)
{
Console.Write(array[i] + " ");//96 94 91 89 83 82 80 70 59 52 51 49 45 41 25 20 18 17 13 12
}
Console.WriteLine();
#endregion
}
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
