16.选择排序

CSharp > CSharp基础 > CSharp基础语法知识 CSharp 语法知识 CSharp基础排序算法

发布时间 : 2024-01-10 20:26

字数:1.7k 阅读 :

评论:

16.排序-选择排序

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