你的位置:首页 > 软件开发 > Java > 排序

排序

发布时间:2017-09-15 22:00:14
插入排序 の implementation  插入排序就像打赌的时候,比如双扣。抽牌的时候,一次拿一张牌,这张牌和之前的牌一张张比较。选择把这张牌插入什么位置,排好顺序的位置后打牌更顺。要不然得一个一个找到时麻烦。也不利于打牌的大局观。看下图  假设第一次抽到梅花7, 不用排序。 ...

排序

插入排序 の implementation


  插入排序就像打赌的时候,比如双扣。抽牌的时候,一次拿一张牌,这张牌和之前的牌一张张比较。选择把这张牌插入什么位置,排好顺序的位置后打牌更顺。要不然得一个一个找到时麻烦。也不利于打牌的大局观。看下图

  假设第一次抽到梅花7, 不用排序。因为只有一张排序

  接着抽到梅花10 排序。因为10比7大,所以不用排序。

  再接着抽卡。发现抽到了梅花5 排序。这个时候不要犹豫,2点真的不算大的。果断弃牌

  接着我们拿 5 和 10 比较。 5 小于 10 所以交换位置。排序

  拿5再和7比。 5 比 7 小。 所以交换 5 和 7 的位置 得到排序

  这个时候就已经是sorted的了。 原理就是这样子。

  因为比较简单。直接贴上代码

  

排序排序
 // O(n^2) 最坏的情况 // 最好的情况 O(n) public static void sort(Comparable[] a) {  for (int i = 1; i < a.length; i++) {   for (int j = i ; j > 0; j--) {    if (less(a[j], a[j - 1]))      exch(a, j, j - 1);    else     break;   }  } }  public static void sort(Comparable[] a, int low, int hi) {  for (int i = low; i <= hi ; i++) {   for (int j = i ; j > low; j--) {    if (less(a[j], a[j - 1]))      exch(a, j, j - 1);    else     break;   }  } }
InsertSort

  完整的代码在https://github.com/Cheemion/algorithms/blob/master/src/com/algorithms/sort/InsertionSort.java

  性能分析


  最坏的情况就是每次抽到的卡是最小的。这个时候每次都需要从尾部遍历到头部。时间是N ^ 2成正比

  最好的情况就是已经排好序了。因为已经排好序了。所以每次抽到的牌都不需要排序。 时间是 N 成正比

 

 

 

  

 

  

 

  

 

 

  

  

  

原标题:排序

关键词:排序

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。