• 欢迎访问我爱CSharp学习网,这里有最新最全的C#书籍,C#视频。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我爱C#学习网吧
  • 推荐使用最新版Chrome浏览器和火狐浏览器访问本网站

C#思维学习算法-马桶排序、冒泡排序和快速排序

C#杂烩 52csharp 989次浏览 0个评论 扫描二维码

(点击上方蓝字,可快速关注我们)


来源:反骨仔(二五仔)

链接:cnblogs.com/liqingwen/p/4994261.html


马桶排序(令人作呕的排序)


一、场景:期末考试完了,老师要将同学们的分数从高到低排序。假设班上有 5 名同学,分别考了 5 分、3 分、5 分、2 分和 8 分【满分:10 分】,排序后的结果就是 8 5 5 3 2,现在,让我们先思考 10 分钟吧!

 

二、思路:


(1)先创建一个数组 int scores[11],就有 scores[0]~scores[10] 共 11 个变量。我们用变量值为 0 表示没有人得到该分数,即 scores [0]=0 表示没有人得 0 分,scores [10]=0 表示没有人得 10 分,而 scores [8]=1 表示有一个人得到 8 分。

 

C#思维学习算法-马桶排序、冒泡排序和快速排序

 

(2)第 1 个数为 5,所以在 scores[5]=0 的基础上+1,即 scores[5]=1 表示有 1 人得到 5 分

 

C#思维学习算法-马桶排序、冒泡排序和快速排序


(3)第 2 个数为 3,所以在 scores[3]=0 的基础上+1,即 scores[3]=1 表示有 1 人得到 3 分

 

C#思维学习算法-马桶排序、冒泡排序和快速排序


(4)第 3 个数为 5,所以在 scores[5]=1 的基础上+1,即 scores[5]=2 表示有 2 人得到 5 分

 

C#思维学习算法-马桶排序、冒泡排序和快速排序


(5)依此类推,处理第 4 和第 5 个数,最终的结果图如下:

 

C#思维学习算法-马桶排序、冒泡排序和快速排序

 

(6)我们发现,scores[0]~scores[10] 内对应的值就是 0~10 分中每个分数所出现的次数。现在,只需将结果打印即可,出现几次就打印机次。

 

我们暂且称它为“马桶排序”,这个算法就相当于有 11 个马桶,编号从 0~10。每出现一个数,就在对应编号的马桶中放一个旗子。

 

C#思维学习算法-马桶排序、冒泡排序和快速排序


图:这里有 11 个马桶

 

三、思考:现在分别有 5 个人的名字和分数:小A 5、小二 3、小三 5、小妞 2 和王大锤 8,请按照分数从高到低,输出他们的名字?


【特点】


假设需要排序的范围 0~20000000,则需要 new int[20000001],非常浪费空间,即便只给 2 个数排序(1,19999999 );


如果排序的数是小数也不行,如:3.141 5926 5358 9793 2384 6264 3383 2795 0238;

 

这里使用 C# 给出简单的算法过程。


static void Main(string[] args)

{

            var scores = new int[] { 5, 3, 5, 2, 8 };

            var newScores = new int[9];

            for (int i = 0; i < scores.Length; i++)

            {

                var score = scores[i];

                newScores[score]++;

            }

            for (int i = newScores.Length – 1; i >= 0; i–)

            {

                var num = newScores[i];

                for (int j = 1; j <= num; j++)

                {

                    Console.Write($”{i} “);

                }

            }

            Console.WriteLine();

            Console.Read();

        }

    }


C#思维学习算法-马桶排序、冒泡排序和快速排序

 

冒泡排序(面试都要问的算法)


一、基本思想:每次比较相邻的两个 元素,按需调整顺序

 

二、题目:要求将 12 35 99 18 76 这 5 个数进行从大到小排序

 

三、思路:


(1)先比较第 1 位和第 2 位的大小,12<35,因为希望越小越靠后,所以要调整两者顺序,交换后的结果:35 12 99 18 76


(2)现在比较第 2 位和第 3 位的大小,12<99,所以需要交换位置,交换后的结果为:35 99 12 18 76


(3)接着比较第 3 位和第 4 位的大小,12<18,交换后的结果为:35 99 18 12 76


(4)最后比较第 4 位和第 5 位的大小,12<76,交换后的结果为:35 99 18 76 12

 C#思维学习算法-马桶排序、冒泡排序和快速排序


(5)经过 4 次后我们发现 5 个数中最小的一个数已经就位,每将一个数归位我们称其为“一趟”;


(6)现在我们开始第二趟,目标将第 2 小的数归位,根据之前逻辑,还是从第 1 个数和第 2 个数开始比较上:35 99 18 76 12 –①–> 99 35 18 76 12 –②–> 99 35 18 76 12 –③–> 99 35 76 18 12


在第一趟比较就知道第 5 位是最小的,所以第 4 位不用和第 5 位比较,这一趟只需比较 3 次


(7)第3趟:99 35 76 18 12 –> 99 35 76 18 12 –> 99 76 35 18 12 (比较 2 次)


(8)第4趟:99 76 35 18 12 –> 99 76 35 18 12 ,有4个数已经就位,那么最后一个数无须比较,它就是最大的


 【总结】如果有 n 个数进行排序,只需将 n-1 个数归位,即要进行 n-1 趟操作,而每一趟开始都从第 1 位进行相邻的两个数 进行比较,将小的那个数放在后面,已经归位的就不用进行比较。


【特点】冒泡算法的核心部分是双重嵌套循环,可以看出时间复杂度是 O(N²),这是一个非常高的时间复杂度。

 

这里使用 C# 给出简单的算法过程。 


static void Main(string[] args)

{

            var nums = new int[] { 12, 35, 99, 18, 76 };

            Output(nums);

            for (int j = 0; j < nums.Length – 1; j++)

            {

                for (int i = 0; i < nums.Length – 1; i++)

                {

                    if (nums[i] < nums[i + 1])

                    {

                        var temp = nums[i];

                        nums[i] = nums[i + 1];

                        nums[i + 1] = temp;

                    }

                }

                Output(nums);

            }

            Console.Read();

        }

        /// <summary>

        /// 控制台输出

        /// </summary>

        /// <param name=”nums”></param>

        static void Output(int[] nums)

        {

            foreach (var num in nums)

            {

                Console.Write($”{num} “);

            }

            Console.WriteLine();

}


C#思维学习算法-马桶排序、冒泡排序和快速排序

 

快速排序(见证亚当和夏娃的爱情之旅)


一、场景:对 6 1 2 7 9 3 4 5 10 8 这 10 个数进行排序

 

二、思路:


先找一个基准数(一个用来参照的数),为了方便,我们选最左边的 6,希望将 >6 的放到 6 的右边,<6 的放到 6 左边。如:3 1 2 5 4 6 9 7 10 8


先假设需要将 6 挪到的位置为 k,k 左边的数 <6,右边的数 >6


(1)我们先从初始数列“6 1 2 7 9 3 4 5 10 8 ”的两端开始“探测 ”,先从右边往左找一个 <6 的数,再从左往右找一个 >6 的数,然后交换。我们用变量 i 和变量 j 指向序列的最左边和最右边。刚开始时最左边 i=0 指向 6,最右边 j=9 指向 8


C#思维学习算法-马桶排序、冒泡排序和快速排序

 

图:亚当 i 和夏娃 j 

 

(2)现在设置的基准数是最左边的数,所以序列先右往左移动(j–),当找到一个 <6 的数(5)就停下来。接着序列从左往右移动(i++),直到找到一个 >6 的数又停下来(7);


(3)两者交换,结果:6 1 2 5 9 3 4 7 10 8;

 

C#思维学习算法-马桶排序、冒泡排序和快速排序

 

(4)j 的位置继续向左移动(友情提示:每次都必须先从 j 的位置出发),发现 4 满足要求,接着 i++ 发现 9 满足要求,交换后的结果:6 1 2 5 43 9 7 10 8;


C#思维学习算法-马桶排序、冒泡排序和快速排序

 

(5)目前 j 指向的值为 9,i 指向的值为 4,j– 发现 3 符合要求,接着 i++ 发现 i=j,说明这一轮移动结束啦。现在将基准数 6 和 3 进行交换,结果:3 1 2 5 4 6 9 7 10 8;现在 6 左边的数都是 <6 的,而右边的数都是 >6 的,但游戏还没结束


C#思维学习算法-马桶排序、冒泡排序和快速排序

图:亚当和夏娃终于产生了交集

 

(6)我们将 6 左边的数拿出来先:3 1 2 5 4,这次以 3 为基准数进行调整,使得 3 左边的数 <3,右边的数 >3,根据之前的模拟,这次的结果:2 1 3 5 4


(7)再将 2 1 抠出来重新整理,得到的结果: 1 2


(8)剩下右边的序列:9 7 10 8 也是这样来搞,最终的结果: 1 2 3 4 5 6 7 8 9 10 (具体看下图)

 

C#思维学习算法-马桶排序、冒泡排序和快速排序

 

【总结】快速排序的每一轮处理其实就是将这一轮的基准数归位,当所有的基准数归位,排序就结束啦


 

C#思维学习算法-马桶排序、冒泡排序和快速排序


我爱CSharp学习网 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C#思维学习算法-马桶排序、冒泡排序和快速排序
喜欢 (1)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址