现在的位置: 首页 > 综合 > 正文

排序算法终结总结

2013年10月05日 ⁄ 综合 ⁄ 共 2670字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  1. /** 
  2.  * 排序算法学习之希尔排序 
  3.  * 实现方法： 
  4.  * 希尔排序是特殊的插入排序 
  5.  * 插入排序按照处理的子数组长度递增分为多趟插入操作 
  6.  * 而每一趟插入操作处理的子数组元素索引间隔都是1（即步长） 
  7.  * 希尔排序每趟处理的子数组元素索引间隔是动态的。 
  8.  */  
  9. package 排序算法.shellSort;  
  10.   
  11. public class ShellSort {  
  12.     /** 
  13.      * 对输入数组进行希尔排序 
  14.      * @param a 待排序数组，索引有效范围从0开始 
  15.      */  
  16.     @SuppressWarnings({ "rawtypes", "unchecked" })  
  17.     public static void shellSort(Comparable[] a) {  
  18.         int incr = a.length / 2;//初始步长  
  19.         while (incr >= 1) {  
  20.             for (int i = incr; i < a.length; i++) {  
  21.                 Comparable insertElement = a[i];  
  22.                 int j;  
  23.                 for (j = i - incr; j >= 0 &&        
  24.                                      insertElement.compareTo(a[j]) < 0; j -= incr)  
  25.                     a[j + incr] = a[j];  
  26.                 a[j + incr] = insertElement;  
  27.             }  
  28.             if (incr == 2)  
  29.                 incr = 1;   
  30.             else  
  31.                 incr = (int) (incr / 2.2);  
  32.         }  
  33.     }  
  34. }  

 

[java] view
plaincopy

  1. /** 
  2.  * 排序算法学习之选择排序 
  3.  * 实现方法： 
  4.  * 每次选择子数组中最大的元素依次排列在子数组末尾， 
  5.  * 子数组的长度依次递减。 
  6.  */  
  7. package 排序算法.selectionSort;  
  8.   
  9. public class SelectionSort {  
  10.     @SuppressWarnings({ "rawtypes", "unchecked" })  
  11.     /** 
  12.      * 查找指定长度的数组中最大元素的索引 
  13.      * @param a 指定数组 
  14.      * @param n 数组长度 
  15.      * @return 最大元素的索引 
  16.      */  
  17.     public static int max(Comparable[] a, int n) {  
  18.         if (n < 0)  
  19.             throw new IllegalArgumentException("数组为空");  
  20.         int positionOfCurrentMax = 0;  
  21.         for (int i = 1; i <= n; i++)  
  22.             if (a[positionOfCurrentMax].compareTo(a[i]) < 0)  
  23.                 positionOfCurrentMax = i;  
  24.         return positionOfCurrentMax;  
  25.     }  
  26.   
  27.     /** 
  28.      * 交换指定数组中指定索引的元素 
  29.      * @param a 指定数组 
  30.      * @param i 第一个索引 
  31.      * @param j 第二个索引 
  32.      */  
  33.     public static void swap(Object[] a, int i, int j) {  
  34.         Object temp = a[i];  
  35.         a[i] = a[j];  
  36.         a[j] = temp;  
  37.     }  
  38.   
  39.     /** 
  40.      * 对输入数组执行一般选择排序 
  41.      * @param a 输入数组 
  42.      */  
  43.     @SuppressWarnings("rawtypes")  
  44.     public void selectionSort(Comparable[] a) {  
  45.         //按照子数组长度递减的顺序进行每趟的选择操作  
  46.         for (int size = a.length; size > 1; size--) {  
  47.             int j = max(a, size - 1);  
  48.             swap(a, j, size - 1);  
  49.         }  
  50.     }  
  51.   
  52.     /** 
  53.      * 对输入数组执行早结束版本的选择排序 
  54.      * @param a 输入数组,数组索引有效范围从0开始 
  55.      */  
  56.     @SuppressWarnings({ "rawtypes", "unchecked" })  
  57.     public  void selectionSort2(Comparable[] a) {  
  58.         boolean sorted = false;//当前子数组是否有序的标志  
  59.         for (int size = a.length; !sorted && (size > 1); size--) {  
  60.             int pos = 0;  
  61.             sorted = true;  
  62.             for (int i = 1; i < size; i++)  
  63.                 if (a[pos].compareTo(a[i]) <= 0)  
  64.                     pos = i;  
  65.                 else

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）