`
awed
  • 浏览: 33962 次
  • 性别: Icon_minigender_1
  • 来自: 珠海
社区版块
存档分类
最新评论

几种排序方法的比较

J# 
阅读更多
java 代码
  1. public class Sort {   
  2.   
  3.     /**  
  4.      * 插入法:遍历排序集合，每到一个元素时，都要将这个元素与所有它之前的元素遍历比较一遍， 让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。交换是相邻遍历移动，  
  5.      * 双重循环控制实现.这种排序法属于地头蛇类型,在我的地牌上我要把所有的东西按一定的顺序 规整,过来一个,规整一个.  
  6.      */  
  7.     public static int[] sort(int[] data) {   
  8.         int temp;   
  9.         for (int i = 1; i < data.length; i++) {   
  10.             for (int j = i; (j > 0) && (data[j] > data[j - 1]); j--) {   
  11.   
  12.                 temp = data[j];   
  13.                 data[j] = data[j - 1];   
  14.                 data[j - 1] = temp;   
  15.             }   
  16.         }   
  17.         return data;   
  18.     }   
  19.   
  20.     /**  
  21.      * 冒泡法:比较容易，它的内层循环保证遍历一次后，集合中最小（大）元素出现在它的正确位置， 下一次就是次小元素。。。该方法在集合分布的各种情况下交换移动的次数基本不变，  
  22.      * 属于最慢的一种排序。实现也是双重循环控制。这种排序法属于过江龙,就是要找到极端, 但是过奖龙也有大哥,二哥等,所以他们只能是大哥挑了二哥挑.  
  23.      */  
  24.     public static int[] maopao(int[] data) {   
  25.         int temp;   
  26.         for (int i = 0; i < data.length - 1; i++) {   
  27.             for (int j = i + 1; j < data.length; j++) {   
  28.                 if (data[i] < data[j]) {   
  29.                     temp = data[i];   
  30.                     data[i] = data[j];   
  31.                     data[j] = temp;   
  32.                 }   
  33.             }   
  34.         }   
  35.         return data;   
  36.     }   
  37.   
  38.     /**  
  39.      * 选择法:该方法只是通过遍历集合记录最小（大）元素的位置，一次遍历完后 ，再进行交换位置操作，类似冒泡，但在比较过程中，不进行交换操作，  
  40.      * 只记录元素位置。一次遍历只进行一次交换操作。这个对与交换次序比较费时的元素比较 适合。这种排序法比冒泡法要城府要深的多,我先记住极端数据,待遍历数据完了之后,  
  41.      * 我再处理,不像冒泡法那样只要比自己极端一点的就要处理,选择法只处理本身范围内的 最极端数据.  
  42.      */  
  43.     public static int[] xuanze(int[] data) {   
  44.         int temp;   
  45.         for (int i = 0; i < data.length; i++) {   
  46.             int lowIndex = i;   
  47.             for (int j = data.length - 1; j > i; j--) {   
  48.                 if (data[j] > data[lowIndex]) {   
  49.                     lowIndex = j;   
  50.                 }   
  51.             }   
  52.             temp = data[i];   
  53.             data[i] = data[lowIndex];   
  54.             data[lowIndex] = temp;   
  55.         }   
  56.         return data;   
  57.     }   
  58.   
  59.     /**  
  60.      * Shell排序:它是对插入排序的一种改进，是考虑将集合元素按照一定的基数划分成组去排序， 让每一组在局部范围内先排成基本有序，最后在进行一次所有元素的插入排序。  
  61.      */  
  62.     public static int[] sort2(int[] data) {   
  63.         for (int i = data.length / 2; i > 2; i /= 2) {   
  64.             for (int j = 0; j < i; j++) {   
  65.                 insertSort(data, j, i);   
  66.             }   
  67.         }   
  68.         insertSort(data, 0, 1);   
  69.         return data;   
  70.     }   
  71.   
  72.     private static void insertSort(int[] data, int start, int inc) {   
  73.         int temp;   
  74.         for (int i = start + inc; i < data.length; i += inc) {   
  75.             for (int j = i; (j >= inc) && (data[j] > data[j - inc]); j -= inc) {   
  76.                 temp = data[j];   
  77.                 data[j] = data[j - inc];   
  78.                 data[j - inc] = temp;   
  79.             }   
  80.         }   
  81.     }   
  82.   
  83.     public static void main(String args[]) {   
  84.         Sort s = new Sort();   
  85.         int str[] = {1, 5, 9, 2, 56, 89, 98, 74, 52, 65, 30, 25, 78, 10, 12, 31, 25, 46};   
  86.         // 冒泡法排序所花时间   
  87.         Long star = System.currentTimeMillis();   
  88.         for (int j = 0; j < 100000; j++)   
  89.             str = s.maopao(str);   
  90.         Long end = System.currentTimeMillis();           
  91.         for (int i = 0; i < str.length; i++) {   
  92.             System.out.print(str[i] + " ");   
  93.         }   
  94.         System.out.println("冒泡排序所花时间: " + (end - star));   
  95.   
  96.         // 插入法排序所花时间   
  97.         star = System.currentTimeMillis();   
  98.         for (int j = 0; j < 100000; j++)   
  99.             str = s.sort(str);   
  100.         end = System.currentTimeMillis();   
  101.         for (int i = 0; i < str.length; i++) {   
  102.             System.out.print(str[i] + " ");   
  103.         }   
  104.         System.out.println("插入法排序所花时间: " + (end - star));   
  105.   
  106.         // Shell排序法排序所花时间   
  107.         star = System.currentTimeMillis();   
  108.         for (int j = 0; j < 100000; j++)   
  109.             str = s.sort2(str);   
  110.         end = System.currentTimeMillis();   
  111.         for (int i = 0; i < str.length; i++) {   
  112.             System.out.print(str[i] + " ");   
  113.         }   
  114.         System.out.println("Shell排序法排序所花时间: " + (end - star));   
  115.   
  116.         // 选择法排序所花时间   
  117.         star = System.currentTimeMillis();   
  118.         for (int j = 0; j < 100000; j++)   
  119.             str = s.xuanze(str);   
  120.         end = System.currentTimeMillis();   
  121.         for (int i = 0; i < str.length; i++) {   
  122.             System.out.print(str[i] + " ");   
  123.         }   
  124.         System.out.println("选择法排序所花时间: " + (end - star));   
  125.     }   
  126. }  

比较结果是:

98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 冒泡排序所花时间: 125
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 插入法排序所花时间: 15
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 Shell排序法排序所花时间: 63
98 89 78 74 65 56 52 46 31 30 25 25 12 10 9 5 2 1 选择法排序所花时间: 94

 

分享到：
| 好好学习；天天向上！
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics