算法学习——不交换的选择排序

小灰灰 2021-05-12 11:54 415阅读 0赞

# 前言： #

经过了昨天晚上的头脑风暴，让我意识到了这种不交换数字的排序手法虽然想起来简单但是实现起来确实是有些难度，尤其是对于排好序的数字的处理，这里让我突然想起了在学习C语言的时候的输出0-1000中的素数的算法，让我有了一些思路，所以就做了出来，在此分享给大家。

# 一、思路整理 #

首先来看下面的导图，其中包括了正常选择排序的信息：

![SouthEast][]

其中我来解释一下，因为要按照下标来排序，所以肯定有一个盛放下标的容器，并且大小要和原数组是一样的，所以这里有了一个临时的数组，然后就是选择排序的主体，我们怎么样输出下标呢，其实就是把原来的比较的最终结果的项纪录下来，所以就可以在if的判断中设置一个取临时最值下标的变量，当内循环结束的时候，我们就可以读取他的纪录，里面肯定是一个现阶段的最值。

在这里又有了一个问题，最大的数字不能总是参加比较，所以就需要进行限制，就是要跳过已经挑出来的数字，这么一来不能再原来的数组上做变化，也不能用记录循环，所以我加上了一个标志位来解决这个问题，这个标志位说白了就是一个一样大小的数组，里面对应的位置盛放的是这个数字的下标（或者一个布尔值），只要这个数字被挑选出来，那么这个标志位就会变为零（置位）。

对于程序的主体，我们只需要把内循环排好的数据置位，记录下标即可。

# 二、小问题 #

一开始的时候我想的是犹豫不确定哪个数字被选出，所以每次循环所有的数字都要循环到，所以循环是从头到尾的（内外都是），然后从中挑出已经被置位的数据跳过，这样就可以了，但是到了最后运行的时候发现有了很多没有被排序的数字。

因为前面的置位，导致了总的循环次数并不是总的数据量，所以数据并没有全部的排完（只是前面的一部分）。

要解决这个问题，我又在前面加了一个总的全循环来保证循环次数，但是这样就有了多余的循环了，这是个问题，希望大神们什么时候能给指导优化一下这个程序。

# 三、代码实现 #

详细内容见注释，我加了一个显示时间的功能，但是10000并不会显示时间，是不是太短了呢？

using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;
    namespace confirm
    {
        public partial class Form1 : Form
        {
            int[] intArry = new int[10001];    //存放随机数
            long tick = 0;                  //时间变量
            public Form1()
            {
                InitializeComponent();
            }
    
            private void button1_Click(object sender, EventArgs e)
            {
                string strnum;
                strnum = "";
                Random ran = new Random();            //定义随机变量
                for (int i = 1; i <= 10000; i++)      //生成随机数，区间为10-200
                {
                    intArry[i] = ran.Next(10, 200);
                }
                for (int i = 1; i <= 10000; i++)     //拼接生成的随机数字符串
                {
                    strnum = strnum + Convert.ToString(intArry[i]) + " ";
                }
                textBox1.Text = strnum;
                button2.Enabled = true;
            }
    
            private void timer1_Tick(object sender, EventArgs e)
            {
                tick++;
                label1.Text = Convert.ToString(tick / 2);   //显示时间
            }
    
            private void button2_Click(object sender, EventArgs e)
            {
                int i, j, k, t, x, y;
                int[] listArry = new int[10001];        //标志数组，用来记录哪个数已经被排完序了
                int[] tmpArry = new int[10001];         //临时数组，用来存放下标
                string strnum = "";    
                timer1.Enabled = true;        //计时器开，用来显示时间
                listArry[0] = 0;              //数组0位置零
                tmpArry[0] = 0;      
                k = 0;                           //临时数组赋值标记
                for (i = 1; i <= 10000; i++)     //给标志位赋值
                {
                    listArry[i] = i;
                }
    
                for (y = 1; y < intArry.Length; y++)             //指定循环次数
                {
                    for (i = 1; i < intArry.Length; i++)         //指定开始最大值
                    {
                        if (listArry[i] == 0)            //判断标志位是否为0
                        {
                            continue;                    //如果为0跳出循环
                        }
                        t = intArry[i];                  //假定要排序的的最大数值
                        x = i;                           //记录最值的下标
    
                        for (j = 1; j < intArry.Length; j++)      //比较循环
                        {
                            if (listArry[j] == 0)         //判断标志位是否为
                            {
                                continue;                //如果为0跳出循环
                            }
    
                            if (t < intArry[j])         //判断条件，满足要求要交换最值
                            {
                                t = intArry[j];
                                x = j;                  //记录最值的下标
                            }
                        }
                        k++;               //临时数组赋值标记加
                        tmpArry[k] = x;    //排完的最大数下标放入临时数组
                        listArry[x] = 0;   //排完数的标志位置0
                    }
                }
    
                for (i = 1; i < tmpArry.Length; i++)      //按下标拼接字符串
                {
                    strnum = strnum + Convert.ToString(intArry[tmpArry[i]]) + " ";
                }
                textBox3.Text = strnum;
    
                timer1.Enabled = false;
                button2.Enabled = false;
            }
        }
    }

源码下载请点击：[这里][Link 1]

# 四、总结 #

一些看起来很是简单的事情，做起来总是很复杂，其实没有想象的那么简单，还有很多的地方需要去完善，所以我们以后学习新的简单东西的时候要尝试去自己做一做，有的时候会发现更多的东西，让你觉得这个事情不是那么的简单。

[SouthEast]: /images/20210511/2a7e625325b24d82aa85df19440e5dff.png
[Link 1]: http://download.csdn.net/detail/tr1912/9547324