C#[C#][算法] 用菜鸟的思考学习算法 — 马桶排序、冒泡排序和高效排序

用菜鸟的思维学习算法 — 马桶排序、冒泡排序和急迅排序

【博主】反骨仔    【来源】http://www.cnblogs.com/liqingwen/p/4994261.html   

目录

  • 马桶排序(令人痛恨到极点的排序)
  • 冒泡排序(面试都要问的算法)
  • 急速排序(见证艾达m和夏娃的情意之旅)

 

马桶排序(令人讨厌的排序)

  一、场景:期末考试完了,老师要将同学们的分数从高到低排序。假诺班上有
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# 1

    

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

 

C# 2

    

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

 

C# 3

    

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

 

C# 4

         

      … …

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

 

C# 5

 

    

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

 

 

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

 

C# 6

图:这里有 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#
给出简单的算法进程。

 1         static void Main(string[] args)
 2         {
 3             var scores = new int[] { 5, 3, 5, 2, 8 };
 4             var newScores = new int[9];
 5 
 6             for (int i = 0; i < scores.Length; i++)
 7             {
 8                 var score = scores[i];
 9                 newScores[score]++;
10             }
11 
12             for (int i = newScores.Length - 1; i >= 0; i--)
13             {
14                 var num = newScores[i];
15                 for (int j = 1; j <= num; j++)
16                 {
17                     Console.Write($"{i} ");
18                 }
19             }
20 
21             Console.WriteLine();
22             Console.Read();
23         }
24     }    

C# 7

 

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

  一、基本考虑:每一回比较相邻的四个元素,按需调整顺序

 

  二、标题:须要将 12 35 99 18 76 那 5
个数举办从大到小排序

C#, 

  三、思路:

    (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# 8

 

    

    (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#
给出不难的算法进度。 

 1         static void Main(string[] args)
 2         {
 3             var nums = new int[] { 12, 35, 99, 18, 76 };
 4             Output(nums);
 5 
 6             for (int j = 0; j < nums.Length - 1; j++)
 7             {
 8                 for (int i = 0; i < nums.Length - 1; i++)
 9                 {
10                     if (nums[i] < nums[i + 1])
11                     {
12                         var temp = nums[i];
13                         nums[i] = nums[i + 1];
14                         nums[i + 1] = temp;
15                     }
16                 }
17 
18                 Output(nums);
19             }
20 
21             Console.Read();
22         }
23 
24         /// <summary>
25         /// 控制台输出
26         /// </summary>
27         /// <param name="nums"></param>
28         static void Output(int[] nums)
29         {
30             foreach (var num in nums)
31             {
32                 Console.Write($"{num} ");
33             }
34 
35             Console.WriteLine();
36         }

C# 9

 

飞速排序(见证Adam和夏娃的情爱之旅)

  一、场景:对 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# 10

 

图:亚当 i 和夏娃 j 

 

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

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

 

C# 11

 

 

    (4)j
的职分延续向左移动(友情提示:每趟都必须先从 j
的职位出发),发现 4 满足必要,接着 i++ 发现 9
满意须要,交流后的结果:6 1 2 5 4 3 9 7 10 8;

 

C# 12

 

    (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# 13

 图:Adam和夏娃终于生出了交集

 

    (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# 14

 

 

    【总括】神速排序的每一轮拍卖其实就是将这一轮的基准数归位,当所有的基准数归位,排序就得了啦

 

 

 

 


  【参考】文章改编与插图来源《啊哈!算法》

相关文章