?? 8?? ??? ??? ???????.

?? ??? ??? ??? ??? ????. ??:

1, ?? ?? ??

(1) ?? ????: In ??? ? ?? ???? ?? (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; //數(shù)組長度  
            int j;               //當(dāng)前值的位置  
            int i;               //指向j前的位置  
            int key;             //當(dāng)前要進(jìn)行插入排序的值  
            //從數(shù)組的第二個(gè)位置開始遍歷值  
            for(j=1;j<length;j++){  
                key=a[j];  
                i=j-1;
                System.out.println(" 將i="+i);
                //a[i]比當(dāng)前值大時(shí)，a[i]后移一位,空出i的位置，好讓下一次循環(huán)的值后移  
                while(i>=0 && a[i]>key){
                    System.out.println("進(jìn) i="+i);
                    a[i+1]=a[i]; //將a[i]值后移  
                    i--;         //i前移  
                    System.out.println(" i="+i);
                }//跳出循環(huán)(找到要插入的中間位置或已遍歷到0下標(biāo))
                System.out.println(" 退出while");
                System.out.println(" i="+i);
                a[i+1]=key;    //將當(dāng)前值插入  
            }  
        }  
        
      
        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
進(jìn) i=0
 i=-1
 退出while
 i=-1
 將i=1
進(jìn) i=1
 i=0
 退出while
 i=0
 將i=2
進(jìn) i=2
 i=1
進(jìn) i=1
 i=0
進(jìn) i=0
 i=-1
 退出while
 i=-1
 將i=3
進(jìn) i=3
 i=2
 退出while
 i=2
 將i=4
進(jìn) i=4
 i=3
進(jìn) i=3
 i=2
 退出while
 i=2
{-8, -1, 0, 1, 2, 3}

? ??(?? ?? ??)

?? ????:

?? ??? ??? ?? ???? ?? ?? ???? ????(?? "??"?? ??) (??? "?"?? ???)? ?? ?? ???? ??? ??, ?? ???? ??? ????? ????(???? ??? ?? ??) ??? ???? ?? ?????. ?? ??? ?? ?????. ?? ?? ??? ??? ????? ???? ?? ?(??? ??? ???) ?? ????? ??? Hill ??? ?? ? ???? ?? ???? ? ????. ?? ??? ??? Hill ??? ??? ?????. ?? ?? ??? 1? ? ?? ?? ?? ??? ?????.

????? ?? ?? ?? ??? ??? ?? ???? ?? ?? ??? ?????. ?? ????? ?? ?? 1? ?????. ?? ??? 1?? ????? ?? ??? ???? ???? ?????. Donald Shell? ??? frac{n}{2}? ?? ??? ???? ?? ??? 1? ??? ??? ?? ??? ???? ???? ??????. ? ?? ??? ??{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) ????. ??? ??? ???? ??? ?? ????? ????, ?? ??? ?? ??? ?? ??? ???? ?? ????? (58,87), (27,58) 5?? ???? ??? , (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 46 93 65

1A 1B

2A 2B

3A 3B

????????????????????????????????????????.....

? ?? ?? ??? 2/2 = 1

32 9 58 7 58 46 65 65 93 87

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

? ?? ?? ??? ??? ??? ?? ???? ?? ?? 1/2 = 0???.

9 27 32 46 58 58 65 65 87 93

希爾排序的時(shí)間性能優(yōu)于直接插入排序的原因：
①當(dāng)文件初態(tài)基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。
②當(dāng)n值較小時(shí)，n和n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度0(n2)差別不大。
③在希爾排序開始時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。

增量序列的選擇：Shell排序的執(zhí)行時(shí)間依賴于增量序列。
好的增量序列的共同特征(查到的資料都這么講)：
① 最后一個(gè)增量必須為1；
② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。

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比較呢？

                 * 因?yàn)橹苯硬迦刖褪钦业絫emp的合適位置。

                 * 為什么temp<arr[j-val]這個(gè)條件可以放在for內(nèi)呢？

                 * 因?yàn)樵瓉淼慕M內(nèi)數(shù)據(jù)已經(jīng)有序，找到位置就停止便是。

                 *

                 */

                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]呢？

                     * 因?yàn)閖=i開始的，而且條件是j>=val&&temp<arr[j-val]

                     */

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

                /*

                 * 注意不是arr[i] = temp

                 * 直接插入排序也是這樣的。

                 * 為什么呢？

                 * 因?yàn)閖是位置，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

選擇排序
每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

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("選擇排序耗費(fèi)時(shí)間："  
                    + (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;  
            }  
        }  
    }  
}