[牛人杂谈] if语句输出 由大到小的数字

[复制链接]
2232|35
yiyigirl2014 发表于 2016-5-24 23:23 | 显示全部楼层
经典排序算法 - 归并排序Merge sort
原理,把原始数组分成若干子数组,对每一个子数组进行排序,
继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
举例
无序数组[6 2 4 1 5 9]
先看一下每个步骤下的状态,完了再看合并细节
第一步 [6 2 4 1 5 9]原始状态
第二步 [2 6] [1 4] [5 9]两两合并排序,排序细节后边介绍
第三步 [1 2 4 6] [5 9]继续两组两组合并
第四步 [1 2 4 5 6 9]合并完毕,排序完毕
输出结果[1 2 4 5 6 9]
合并细节
详细介绍第二步到第三步的过程,其余类似
第二步:[2 6] [1 4] [5 9]
两两合并,其实仅合并[2 6] [1 4],所以[5 9]不管它,
原始状态
第一个数组[2 6]
第二个数组[1 4]
--------------------
第三个数组[...]

第1步,顺序从第一,第二个数组里取出一个数字:2和1
比较大小后将小的放入第三个数组,此时变成下边这样
第一个数组[2 6]
第二个数组[4]
--------------------
第三个数组[1]

第2步,继续刚才的步骤,顺序从第一,第二个数组里取数据,2和4,
同样的比较大小后将小的放入第三个数组,此时状态如下
第一个数组[6]
第二个数组[4]
--------------------
第三个数组[1 2]

第3步,再重复前边的步骤变成,将较小的4放入第三个数组后变成如下状态
第一个数组[6]
第二个数组[...]
--------------------
第三个数组[1 2 4]

第4步,最后将6放入,排序完毕
第一个数组[...]
第二个数组[...]
--------------------
第三个数组[1 2 4 6]

[ 1 2 4 6 ]与[ 5 9 ]的合并过程与上边一样,不再分解

yiyigirl2014 发表于 2016-5-24 23:27 | 显示全部楼层
  1. static void merge(int[] unsorted, int first, int mid, int last, int[] sorted)
  2.         {
  3.             int i = first, j = mid;
  4.             int k = 0;
  5.             while (i < mid && j < last)
  6.                 if (unsorted[i] < unsorted[j])
  7.                     sorted[k++] = unsorted[i++];
  8.                 else
  9.                     sorted[k++] = unsorted[j++];

  10.             while (i < mid)
  11.                 sorted[k++] = unsorted[i++];
  12.             while (j < last)
  13.                 sorted[k++] = unsorted[j++];

  14.             for (int v = 0; v < k; v++)
  15.                 unsorted[first + v] = sorted[v];
  16.         }

  17.         static void merge_sort(int[] unsorted, int first, int last, int[] sorted)
  18.         {
  19.             if (first + 1 < last)
  20.             {
  21.                 int mid = (first + last) / 2;
  22.                 Console.WriteLine("{0}-{1}-{2}", first, mid, last);
  23.                 merge_sort(unsorted, first, mid, sorted);
  24.                 merge_sort(unsorted, mid, last, sorted);
  25.                 merge(unsorted, first, mid, last, sorted);
  26.             }
  27.         }

  28.         static void Main(string[] args)
  29.         {
  30.             int[] x = { 6, 2, 4, 1, 5, 9 };
  31.             int[] sorted = new int[x.Length];
  32.             merge_sort(x, 0, x.Length, sorted);
  33.             for (int i = 0; i < sorted.Length; i++)
  34.             {
  35.                 if (x[i] > 0)
  36.                     Console.WriteLine(x[i]);
  37.             }
  38.             Console.ReadLine();
  39.         }


yiyigirl2014 发表于 2016-5-24 23:28 | 显示全部楼层
经典排序算法 - 冒泡排序Bubble sort
原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
这样一趟过去后,最大或最小的数字被交换到了最后一位,
然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子
例子为从小到大排序,
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |

第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第四趟排序(外循环)无交换
第五趟排序(外循环)无交换

排序完毕,输出最终结果1 2 4 5 6 9
  1. static void bubble_sort(int[] unsorted)
  2.         {
  3.             for (int i = 0; i < unsorted.Length; i++)
  4.             {
  5.                 for (int j = i; j < unsorted.Length; j++)
  6.                 {
  7.                     if (unsorted[i] > unsorted[j])
  8.                     {
  9.                         int temp = unsorted[i];
  10.                         unsorted[i] = unsorted[j];
  11.                         unsorted[j] = temp;
  12.                     }
  13.                 }
  14.             }
  15.         }

  16.         static void Main(string[] args)
  17.         {
  18.             int[] x = { 6, 2, 4, 1, 5, 9 };
  19.             bubble_sort(x);
  20.             foreach (var item in x)
  21.             {
  22.                 Console.WriteLine(item);
  23.             }
  24.             Console.ReadLine();
  25.         }


yiyigirl2014 发表于 2016-5-24 23:31 | 显示全部楼层
经典排序算法 - 选择排序Selection sort
顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,
顺序放入新数组,直到全部拿完
再简单点,对着一群数组说,你们谁最小出列,站到最后边
然后继续对剩余的无序数组说,你们谁最小出列,站到最后边
再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了,从小到大
举例
先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]
第一趟找到最小数1,放到最前边(与首位数字交换)
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换
第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 5 | 6 | 9 |
第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换
排序完毕输出正确结果[1 2 4 5 6 9]
第一趟找到最小数1的细节
当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |
先把6取出来,让它扮演最小数
当前最小数6与其它数一一进行比较,发现更小数就交换角色
当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较
当前最小数2与4比较,不动
当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较
当前最小数1与5比较,不动
当前最小数1与9比较,不动,到达末尾
当前最小数1与当前首位数字进行位置交换,如下所示
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
完成一趟排序,其余步骤类似
代码仅供参考
  1. static void selection_sort(int[] unsorted)
  2.         {
  3.             for (int i = 0; i < unsorted.Length; i++)
  4.             {
  5.                 int min = unsorted[i], min_index = i;
  6.                 for (int j = i; j < unsorted.Length; j++)
  7.                 {
  8.                     if (unsorted[j] < min)
  9.                     {
  10.                         min = unsorted[j];
  11.                         min_index = j;
  12.                     }
  13.                 }
  14.                 if (min_index != i)
  15.                 {
  16.                     int temp = unsorted[i];
  17.                     unsorted[i] = unsorted[min_index];
  18.                     unsorted[min_index] = temp;
  19.                 }
  20.             }
  21.         }

  22.         static void Main(string[] args)
  23.         {
  24.             int[] x = { 6, 2, 4, 1, 5, 9 };
  25.             selection_sort(x);
  26.             foreach (var item in x)
  27.             {
  28.                 Console.WriteLine(item);
  29.             }
  30.             Console.ReadLine();
  31.         }


yiyigirl2014 发表于 2016-5-24 23:36 | 显示全部楼层
经典排序算法 - **尾酒排序Cocktail sort
**尾酒排序基于冒泡排序,双向循环
还是看例子吧,给定待排数组[2 3 4 5 1]
第一趟过去时的每一步
第一步迭代,2 < 3不换
[2 3 4 5 1]

第二步迭代,3 < 4不换
[2 3 4 5 1]

第三步迭代,4 < 5不换
[2 3 4 5 1]

第四步迭代,5 > 1交换
[2 3 4 1 5]

第一趟回来时的第一步,**尾酒一次到头后就回返回来,再到头后再过去,来回比,一个来回能排两个数字
第五步迭代,1 < 5不交换
[2 3 4 1 5]

第六步迭代,1 < 4交换
[2 3 1 4 5]

第七步迭代,1 < 3交换
[2 1 3 4 5]

第八步迭代,2 > 1交换
[1 2 3 4 5]

排序完毕,顺序输出结果即可得[ 1 2 3 4 5]

如何判断排序结束了?
假如一趟来回没有交换任何数字,则表示该数组已经有序了,可以设置了个变量表示有没有交换过
代码仅供参考
  1. static void cocktail_sort(int[] unsorted)
  2.         {
  3.             bool swapped = false;
  4.             do
  5.             {
  6.                 for (int i = 0; i < unsorted.Length - 1; i++)
  7.                 {
  8.                     if (unsorted[i] > unsorted[i + 1])
  9.                     {
  10.                         int temp = unsorted[i];
  11.                         unsorted[i] = unsorted[i + 1];
  12.                         unsorted[i + 1] = temp;
  13.                         swapped = true;
  14.                     }
  15.                 }

  16.                 swapped = false;
  17.                 for (int j = unsorted.Length; j > 1; j--)
  18.                 {
  19.                     if (unsorted[j] < unsorted[j - 1])
  20.                     {
  21.                         int temp = unsorted[j];
  22.                         unsorted[j] = unsorted[j - 1];
  23.                         unsorted[j - 1] = temp;
  24.                         swapped = true;
  25.                     }
  26.                 }
  27.             } while (swapped);
  28.         }


  29.         static void Main(string[] args)
  30.         {
  31.             int[] x = { 6, 2, 4, 1, 5, 9 };
  32.             selection_sort(x);
  33.             foreach (var item in x)
  34.             {
  35.                 Console.WriteLine(item);
  36.             }
  37.             Console.ReadLine();
  38.         }


yiyigirl2014 发表于 2016-5-24 23:37 | 显示全部楼层
经典排序算法 - 梳排序Comb sort

梳排序还是基于冒泡排序,与冒泡不同的是,梳排序比较的是固定距离处的数的比较和交换,类似希尔那样

这个固定距离是待排数组长度除以1.3得到近似值,下次则以上次得到的近似值再除以1.3,直到距离小至3时,以1递减

不太好描述,还是看例子吧

假设待数组[8 4 3 7 6 5 2 1]

待排数组长度为8,而8÷1.3=6,则比较8和2,4和1,并做交换

[8 4 3 7 6 5 2 1]

[8 4 3 7 6 5 2 1]

交换后的结果为

[2 1 3 7 6 5 8 4]

第二次循环,更新间距为6÷1.3=4,比较2和6,1和5,3和8,7和4

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

只有7和4需要交换,交换后的结果为

[2 1 3 4 6 5 8 7]

第三次循环,更新距离为3,没有交换

第四次循环,更新距离为2,没有交换

第五次循环,更新距离为1,三处交换

[2 1 3 4 6 5 8 7]

[2 1 3 4 6 5 8 7]

[2 1 3 4 6 5 8 7]

三处交换后的结果为[1 2 3 4 5 6 7 8]

交换后排序结束,顺序输出即可得到[1 2 3 4 5 6 7 8]
yiyigirl2014 发表于 2016-5-24 23:41 | 显示全部楼层
经典排序算法 - 奇偶排序Odd-even sort

又一个比较性质的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序

举例吧,

待排数组[6 2 4 1 5 9]

第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比

[6 2 4 1 5 9]

交换后变成

[2 6 1 4 5 9]



第二次比较偶数列,即6和1比,5和5比

[2 6 1 4 5 9]

交换后变成

[2 1 6 4 5 9]



第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较

[2 1 6 4 5 9]

交换后

[1 2 4 6 5 9]



第四趟偶数列

[1 2 4 6 5 9]

一次交换

[1 2 4 5 6 9]
yiyigirl2014 发表于 2016-5-24 23:42 | 显示全部楼层
经典排序算法 - 珠排序Bead Sort
珠排序非常另类[地精也很另类],看完你就知道了,先介绍思路,再分解过程
截图即从上边的论文里抓的屏
先了解一个概念,不然不容易理解,一个数字3用3个1来表示
一个数字9用9个1来表示,珠排序中的珠指的是每一个1,它把每一个1想像成一个珠子,这些珠子被串在一起,想像下算盘和糖葫芦
图1
上图1中的三个珠就表示数字3,两个珠表示数字2,这个OK了继续,这里的3和2都叫bead
图2
图2(a)中有两个数字,4和3,分别串在四条线上,于是数字4的最后一个珠子下落,因为它下边是空的,自由下落后变成图2(b)
图2(c)中随机给了四个数字,分别是3,2,4,2,这些珠子自由下落,就变成了(d)中,落完就有序了,2,2,3,4
以上就是珠排序的精华
图3
上图3中的n表示待排序数组的长度,有多少数字就有多少层,横向表示一层
m表示有多少个珠子,就是多少个1,这取决于最大数是几
比如待排数组[6 2 4 1 5 9]
让珠子全部做自由落体运动
9没有什么好落的,它在最底层
5也没有什么好落的,全部有支撑点
1同样不需要滑落
4除了第一个珠子不动外,其它三颗全部下落,落到1的位置变成下边这样
过程的细节不画了,原则就是你下边有支点,你就不用再滑落了,最后变成下边这样,排序完毕
从上到下顺序输出即可得到结果:[ 1 2 4 5 6 9]



yiyigirl2014 发表于 2016-5-24 23:44 | 显示全部楼层
经典排序算法 - Cycle Sort
Cycle sort的思想与计数排序太像了,理解了基数排序再看这个会有很大的帮助,
圈排序与计数排序的区别在于圈排序只给那些需要计数的数字计数,先看完**吧,看完再回来理解这一句话
所谓的圈的定义,我只能想到用例子来说明,实在不好描述
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]

第一部分
     第一步,我们现在来观察待排数组和排完后的结果,以及待排数组的索引,可以发现
排完序后的6应该出现在索引4的位置上,而它现在却在位置0上,
记住这个位置啊,一直找到某个数应该待在位置0上我们的任务就完成了
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]
     第二步,而待排数组索引4位置上的5应该出现在索引3的位置上
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]
     第三步,同样的,待排数组索引3的位置是1,1应该出现在位置0上,注意注意,找到这么一个数了:1,它应该待在位置0上
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]
     第四步,而索引0处却放着6,而6应该出现在索引4的位置,至此可以发现,回到原点了,问题回到第一步了,
所以这里并不存在所谓的第四步,前三步就已经转完一圈了
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]
这就是所谓的一圈!真不好描述,不知道您看明白没...汗.
前三步转完一圈,得到的数据分别是[ 6 5 1 ]

第二部分
     第一步,圈排序并不是一圈排序,而一圈或多圈排序,所以,还得继续找,这一步从第二个数字2处开始转圈
待排中的2位于索引1处,排序完毕仍然处于位置1位置,所以这一圈完毕,得到圈数据[ 2 ]
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]

第三部分
     第一步,同上,4也出现了它应该待的位置,结束这一圈,得到第三个圈:[ 4 ]
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]

第四部分
     第一步,由于1和5出现在第一圈里,这是什么意思呢,说明这两个数已经有自己的圈子了,不用再找了,
即是找,最后还是得到第一圈的数据[ 6 5 1 ],所以,1和5跳过,这一部分实际应该找的是9,来看看9的圈子
9应该出现在索引5的位置,实际上它就在索引5的位置,与第二部分的第一步的情况一样,所以这一圈的数据也出来了:[ 9 ]
待排数组[ 6 2 4 1 5 9 ]
排完序后[ 1 2 4 5 6 9 ]
数组索引[ 0 1 2 3 4 5 ]
一共找到四个圈子,分别是
[ 6 5 1 ] , [ 2 ] ,[ 4 ] , [ 9 ]

如果一个圈只有一个数字,那么它是不需要转圈的,即不需要排序,那么只有第一个圈排序即可
你可能要问了,前边的那些圈子都是基于已知排序结果才能得到,我都已知结果还排个毛啊
以上内容都是为了说明什么是圈,知道什么是圈后才能很好的理解圈排序
现在来分解排序的细节
第一步,将6取出来,计算出有4个数字比6小,将6放入索引4,同时原索引4位置的数字5出列
排序之前[ 0 2 4 1 5 9 ] 6
排序之后[ 0 2 4 1 6 9 ] 5
索引位置[ 0 1 2 3 4 5 ]

第二步,当前数字5,计算出有3个数字比5小,将5放入索引3,同时原索引3位置的数字
排序之前[ 0 2 4 1 6 9 ] 5
排序之后[ 0 2 4 5 6 9 ] 1
索引位置[ 0 1 2 3 4 5 ]

第三步,当前数字1,计算出有0个数字比1小,将1放入索引0,索引0处为空,这圈完毕
排序之前[ 0 2 4 5 6 9 ] 1
排序之后[ 1 2 4 5 6 9 ]
索引位置[ 0 1 2 3 4 5 ]
第一个圈[ 6 5 1 ]完毕

第四步,取出下一个数字2,计算出有1个数字比2小,将2放入索引1处,发现它本来就在索引1处
第五步,取出下一个数字4,计算出有2个数字比4小,将4放入索引2处,发现它本来就在索引2处
第六步,取出下一个数字5,5在第一个圈内,不必排序
第七步,取出下一个数字6,6在第一个圈内,不必排序
第八步,取出下一个数字9,计算出有5个数字比9小,将9放入索引5处,发现它本来就在索引5处
全部排序完毕

yiyigirl2014 发表于 2016-5-24 23:44 | 显示全部楼层
经典排序算法 - 奇偶排序Odd-even sort
又一个比较性质的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序
举例吧,
待排数组[6 2 4 1 5 9]
第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比
[6 2 4 1 5 9]
交换后变成
[2 6 1 4 5 9]

第二次比较偶数列,即6和1比,5和5比
[2 6 1 4 5 9]
交换后变成
[2 1 6 4 5 9]

第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较
[2 1 6 4 5 9]
交换后
[1 2 4 6 5 9]

第四趟偶数列
[1 2 4 6 5 9]
一次交换
[1 2 4 5 6 9]


戈卫东 发表于 2016-5-25 00:26 | 显示全部楼层
yiyigirl2014 发表于 2016-5-24 23:44
经典排序算法 - 奇偶排序Odd-even sort又一个比较性质的排序,基本思路是奇数列排一趟序,偶数列 ...

哎哟张姿势了。。。。。。。。。。。。
secretuniverse 发表于 2016-5-25 17:03 | 显示全部楼层
这种方法在硬件程序中用的多吗
 楼主| wahahaheihei 发表于 2016-5-26 11:20 | 显示全部楼层
不错的排序法,非常好,第一次见。。排序还这么多门道。
 楼主| wahahaheihei 发表于 2016-5-26 11:21 | 显示全部楼层
算法让计算机实现了各种功能。真是没有程序和算法,计算机一堆废铁。
yiyigirl2014 发表于 2016-5-29 00:10 | 显示全部楼层
这个排序充分说明算法是灵魂
您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 在线客服 返回列表 返回顶部