目錄

插入排序

希爾排序

歸并排序

快速排序

插入排序

排序原理：

1.把所有元素分為兩組，第一組是有序已經(jīng)排好的，第二組是亂序未排序。

2.將未排序一組的第一個(gè)元素作為插入元素，倒序與有序組比較。

3.在有序組中找到比插入元素小或者大的元素，將插入元素放入該位置，后面元素向后移動(dòng)一位。

?時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：當(dāng)A與B相等，排序前A若在B前，排序后A仍然在B前，就說明該排序是穩(wěn)定的。

插入排序：穩(wěn)定

//比較兩元素大小方法
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }

 //數(shù)組中 交換元素位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

插入排序

    public static void insertSort(Comparable[] a){
        for (int i = 1; i < a.length-1; i++) {
            for (int j = i+1; j >0; j--) {
                if (greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else break;
            }
        }
    }

希爾排序

排序原理：

1.選擇一個(gè)增長量h，按照h將數(shù)據(jù)分組。

2.每組進(jìn)行插入排序。

3.減少增長量h直到h=1，重復(fù)步驟2

穩(wěn)定性：不穩(wěn)定

     public static void shellSort(Comparable[] a){
        int h = 1;
        //確定h
        while (h<a.length/2){
            h = 2*h+1;
        }
        // 希爾排序
        while (h>=1){
            for (int i = h; i < a.length; i=i+h) {
                for (int j = i; j >= h; j=j-h) {
                    if (greater(a[j-h],a[j])){
                        exch(a,j-h,j);
                    }else break;
                }
            }
            h=h/2;
        }
    }

歸并排序

排序原理：

1.盡可能的一組數(shù)據(jù)拆分成兩個(gè)元素相等的子組，并對(duì)每一個(gè)子組繼續(xù)拆分，直到拆分后的每個(gè)子

組的元素個(gè)數(shù)是1為止。

2.將相鄰的兩個(gè)子組進(jìn)行合并成一個(gè)有序的大組；

3.不斷的重復(fù)步驟2，直到最終只有一個(gè)組為止。

時(shí)間復(fù)雜度：O(nlogn)

穩(wěn)定性： 穩(wěn)定

import java.util.Arrays;

public class Merge {
    //歸并需要的輔助數(shù)組
    private static Comparable[] assist;

    //判斷v是否比w小
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    //交換元素
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    //對(duì)數(shù)組a排序
    public static void sort(Comparable[] a){
        //    1.初始化輔助數(shù)組assist
        assist= new Comparable[a.length];
        //    定義lo變量和hi變量。分別記錄數(shù)組中最小的索引和最大的索引
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //對(duì)數(shù)組a中從lo到hi元素進(jìn)行排序
    private static void sort(Comparable[] a,int lo,int hi){
    //安全檢驗(yàn)
        if (hi<=lo){
            return;
        }
    //  對(duì)lo和hi之間的數(shù)據(jù)進(jìn)行分為兩組
        int mid = lo+(hi-lo)/2;
    //    分別排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
    //兩組歸并
        merge(a,lo,mid,hi);
    }

    //歸并
    private static void merge(Comparable[] a,int lo,int mid,int hi){
    //    定義三個(gè)指針
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;
    //    遍歷移動(dòng)p1指針和p2指針，比較對(duì)應(yīng) 索引處的值，找出小的，放到輔助數(shù)組對(duì)應(yīng)分索引處
       while (p1<=mid&&p2<=hi){
           if (less(a[p1],a[p2])){
               assist[i++] = a[p1++];
           }else {
               assist[i++] = a[p2++];
           }
       }
    //遍歷，如果p1的指針沒有走完，將p1剩余遍歷到輔助數(shù)組中
        while (p1<=mid){
            assist[i++] = a[p1++];
        }
    //遍歷，如果p2的指針沒有走完，將p2剩余遍歷到輔助數(shù)組中
        while (p2<=hi){
            assist[i++] = a[p2++];
        }
    //    把輔助數(shù)組中的元素復(fù)制到原數(shù)組中
        for (int index = lo;index<=hi;index++){
            a[index] = assist[index];
        }
    }

    public static void main(String[] args) {
        Integer[] a={7,8,4,5,6,1,3,9,2};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    //    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

}

快速排序

排序原理：
1.首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分；

2.將大于或等于分界值的數(shù)據(jù)放到到數(shù)組右邊，小于分界值的數(shù)據(jù)放到數(shù)組的左邊。此時(shí)左邊部分

中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值；

3.然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分

數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處

理。
4.重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)

部分的順序。當(dāng)左側(cè)和右側(cè)兩個(gè)部分的數(shù)據(jù)排完序后，整個(gè)數(shù)組的排序也就完成了。?

時(shí)間復(fù)雜度：

平均情況：O(nlogn)，最壞情況：O(n^2)?

穩(wěn)定性：不穩(wěn)定?

文章來源地址http://www.zghlxwxcb.cn/news/detail-644583.html

import java.util.Arrays;

public class Quick {
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    //對(duì)數(shù)組內(nèi)的元素進(jìn)行排序
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //對(duì)數(shù)組a中從索引hi之間的元素進(jìn)行排序
    public static void sort(Comparable[] a,int lo,int hi){
        if (lo>=hi)return;
        int partition = partition(a,lo,hi);
        sort(a,lo,partition-1);
        sort(a,partition+1,hi);
    }

    private static int partition(Comparable[] a,int lo,int hi){
        //確定分界值
        Comparable key = a[lo];
        //定義兩個(gè)指針，分別指向待切分元素的最小索引處和最大索引處的下一個(gè)位置
        int left = lo;
        int right = hi+1;
        //切分 掃描
        while (true){
            //先從右邊向左掃描，移動(dòng)right指針，找到比分界值小的，停止
            while (less(key,a[--right])){
                if (right==lo){
                    break;
                }
            }
            //從左邊向右掃描，移動(dòng)light指針，找到比分界值大的，停止
            while (less(a[++left],key)){
                if (left==hi){
                    break;
                }
            }
            //right<right時(shí)交換
            if (left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //交換分界值
        exch(a,lo,right);
        return right;
    }

    public static void main(String[] args) {
        Integer a[] = {3,6,9,2,5,8,4,7,1};
        Quick.sort(a);
        System.out.println(Arrays.toString(a));
    //    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

}

到了這里，關(guān)于插入、希爾、歸并、快速排序(java實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！