java各種排序演算法及實現

先來看看8種排序之間的關係：

 

下圖是各種排序的比較：

 

1，  直接插入排序

   （1）基本想法：在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排

好順序的，現在要把第n個數插到前面的有序數中，使得這n個數

也是排好順序的。如此反覆循環，直到全部排好順序。

在插入演算法中，如果有一個最小的數在數組的最後面，用插入演算法就會從最後一個

位置移動到第一個。

（2）實例

 

package cglib;

 

public class StringNumber {
    
      public static void insertSort(int[] a) {  
            if (a == null || a.length < 2) {  
                return;  
            }  
            int length=a.length; //数组长度  
            int j;               //当前值的位置  
            int i;               //指向j前的位置  
            int key;             //当前要进行插入排序的值  
            //从数组的第二个位置开始遍历值  
            for(j=1;j<length;j++){  
                key=a[j];  
                i=j-1;
                System.out.println(" 将i="+i);
                //a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移  
                while(i>=0 && a[i]>key){
                    System.out.println("进 i="+i);
                    a[i+1]=a[i]; //将a[i]值后移  
                    i--;         //i前移  
                    System.out.println(" i="+i);
                }//跳出循环(找到要插入的中间位置或已遍历到0下标)
                System.out.println(" 退出while");
                System.out.println(" i="+i);
                a[i+1]=key;    //将当前值插入  
            }  
        }  
        
      
        public static void main(String[] args) {  
            int[] array = { 3, -1, 0, -8, 2, 1 };  
            ArrayUtils.printArray(array);  
            insertSort(array);  
            ArrayUtils.printArray(array);  
        }
}

class ArrayUtils {  
    
    public static void printArray(int[] array) {  
        System.out.print("{");  
        for (int i = 0; i < array.length; i++) {  
            System.out.print(array[i]);  
            if (i < array.length - 1) {  
                System.out.print(", ");  
            }  
        }  
        System.out.println("}");  
    }  
}

     輸出：

{3, -1, 0, -8, 2, 1}
 将i=0
进 i=0
 i=-1
 退出while
 i=-1
 将i=1
进 i=1
 i=0
 退出while
 i=0
 将i=2
进 i=2
 i=1
进 i=1
 i=0
进 i=0
 i=-1
 退出while
 i=-1
 将i=3
进 i=3
 i=2
 退出while
 i=2
 将i=4
进 i=4
 i=3
进 i=3
 i=2
 退出while
 i=2
{-8, -1, 0, 1, 2, 3}

希爾希爾（希爾增量數位（最小增量元素）將整個時間排列成真數個以下變化希爾（8個增量）。序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本上有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。

演算法最開始以一定的步長進行排序,然後會繼續以一定步長進行排序，最終演算法以步長為1進行排序。當步長為1時，演算法變成插入排序，這就保證了資料一 定會被排序。 Donald Shell 最初建議步長選擇為frac{n}{2}並且對步長取半直到步長達到 1。雖然這樣取可以比mathcal{O}(n^2)類別的演算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的空間。

希爾排序範例:n=10的一個陣列 58 27 32 93 65 87 58 46 9 65，步長為n/2。

第一次排序步長為10/2 = 5

   58  27  32  93  65  87  58  46  9  65 

    1A                        1B

        2A                          2B

            3A                           3B

                  4A                           4B
                      5A                           5B

    首先將待排序元素序列分組，以5為步長，(1A,1B), (2A,2B),(3A,3B)等為分組標記，大寫字母表示是該組的第幾個元素,數字相同的表示在同一組，這樣就分成5組，即(58,87), (27,58),(32,46),(93,9),(65,65)，然後分別對各分組進行直接插入排序，排序後5組為(58,87),(27,58), (32,46),(9,93),(65,65)，分組排序只是變成各個分組內的下表，下同。

    第二次排序步長為5/2 = 2

    58  27  32  9  65  87  58   

          2A      2B    

                   .......... ................................

    第三次排序步長為2/2 = 1

    32  9  58  27  58  46  65  65  93  87

   1A 1B 1C 1D 1E 1 1 四次排序步長為1/2 = 0 得到有序元素序列

    9  27  32  46  58  58 65  65  87  93

希尔排序的时间性能优于直接插入排序的原因：
     ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
     ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
     ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

增量序列的选择：Shell排序的执行时间依赖于增量序列。
    好的增量序列的共同特征(查到的资料都这么讲)：
     ① 最后一个增量必须为1；
     ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。     

package cglib;

 

public class StringNumber {
    
    public static void main(String[] args) {

        int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};

        System.out.print("排序前：");

        for(int o: arr) {

            System.out.print(o+" ");

        }

        System.out.println();

        shellSort(arr);

        System.out.print("排序后：");

        for(int o: arr) {

            System.out.print(o+" ");

        }

        System.out.println();

    }

    private static void shellSort(int[] arr) {

        int j;

        int len = arr.length;

        for(int val=len>>1; val>0; val>>=1) {

            //下面是对本次的所有分组做直接插入排序

            for(int i=val; i<len; i++) {
                System.out.println("for:i="+i);
                System.out.println("for:arr[i]="+arr[i]);
                System.out.println("for:val="+val);
                int temp = arr[i];

                /*

                 * 为什么每次都用temp比较呢？

                 * 因为直接插入就是找到temp的合适位置。

                 * 为什么temp<arr[j-val]这个条件可以放在for内呢？

                 * 因为原来的组内数据已经有序，找到位置就停止便是。

                 *

                 */

                for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
                    System.out.println("er:j="+j);
                    System.out.println("er:arr[j]="+arr[j]);
                    System.out.println("er:j-val="+(j-val));
                    System.out.println("er:arr[j-val]="+arr[j-val]);
                    /*

                     * 为什么是arr[j-val]不是arr[j]呢？

                     * 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val]

                     */

                    arr[j] = arr[j-val];
                    System.out.println("赋值er:arr[j]="+arr[j]);
                }

                /*

                 * 注意不是arr[i] = temp

                 * 直接插入排序也是这样的。

                 * 为什么呢？

                 * 因为j是位置，i是待插入元素

                 */

                arr[j] = temp;

            }

        }

    }
 
}

输出：

排序前：44 33 99 10 30 20 59 78 23 48
for:i=5
for:arr[i]=20
for:val=5
er:j=5
er:arr[j]=20
er:j-val=0
er:arr[j-val]=44
赋值er:arr[j]=44
for:i=6
for:arr[i]=59
for:val=5
for:i=7
for:arr[i]=78
for:val=5
er:j=7
er:arr[j]=78
er:j-val=2
er:arr[j-val]=99
赋值er:arr[j]=99
for:i=8
for:arr[i]=23
for:val=5
for:i=9
for:arr[i]=48
for:val=5
for:i=2
for:arr[i]=78
for:val=2
for:i=3
for:arr[i]=10
for:val=2
er:j=3
er:arr[j]=10
er:j-val=1
er:arr[j-val]=33
赋值er:arr[j]=33
for:i=4
for:arr[i]=30
for:val=2
er:j=4
er:arr[j]=30
er:j-val=2
er:arr[j-val]=78
赋值er:arr[j]=78
for:i=5
for:arr[i]=44
for:val=2
for:i=6
for:arr[i]=59
for:val=2
er:j=6
er:arr[j]=59
er:j-val=4
er:arr[j-val]=78
赋值er:arr[j]=78
for:i=7
for:arr[i]=99
for:val=2
for:i=8
for:arr[i]=23
for:val=2
er:j=8
er:arr[j]=23
er:j-val=6
er:arr[j-val]=78
赋值er:arr[j]=78
er:j=6
er:arr[j]=78
er:j-val=4
er:arr[j-val]=59
赋值er:arr[j]=59
er:j=4
er:arr[j]=59
er:j-val=2
er:arr[j-val]=30
赋值er:arr[j]=30
for:i=9
for:arr[i]=48
for:val=2
er:j=9
er:arr[j]=48
er:j-val=7
er:arr[j-val]=99
赋值er:arr[j]=99
for:i=1
for:arr[i]=10
for:val=1
er:j=1
er:arr[j]=10
er:j-val=0
er:arr[j-val]=20
赋值er:arr[j]=20
for:i=2
for:arr[i]=23
for:val=1
for:i=3
for:arr[i]=33
for:val=1
for:i=4
for:arr[i]=30
for:val=1
er:j=4
er:arr[j]=30
er:j-val=3
er:arr[j-val]=33
赋值er:arr[j]=33
for:i=5
for:arr[i]=44
for:val=1
for:i=6
for:arr[i]=59
for:val=1
for:i=7
for:arr[i]=48
for:val=1
er:j=7
er:arr[j]=48
er:j-val=6
er:arr[j-val]=59
赋值er:arr[j]=59
for:i=8
for:arr[i]=78
for:val=1
for:i=9
for:arr[i]=99
for:val=1
排序后：10 20 23 30 33 44 48 59 78 99

选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

package cglib;

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class StringNumber {
    
    public static void main(String[] args){  
        Random random = new Random();  
        int[] array = new int[2000];  
          
          
            for (int j = 0; j < 2000; j++) {  
                array[j] = random.nextInt(100000);  
            }  
        
        System.out.println(Arrays.toString(array));  
        selectSortTest(array);  
        System.out.println(Arrays.toString(array));       
    }  
    
     public static void selectSortTest(int a[]) {  
             
            Date dateStart = new Date();  
            selectSort(a);  
            Date dateEnd = new Date();  
            System.out.println("选择排序耗费时间："  
                    + (dateEnd.getTime() - dateStart.getTime()));  
              
           
        }  
    
    
      
    public static void selectSort(int a[]){  
        int n = a.length;  
        for(int k=0; k<n-1; k++) {  
            int min = k;  
            for(int i=k+1; i<n; i++) {//找出最小值  
                if(a[i] < a[min]) {  
                    min = i;  
                }  
            }  
            if(k != min) {  
                int temp = a[k];  
                a[k] = a[min];  
                a[min] = temp;  
            }  
        }  
    }  
}