目錄

第1關：選擇排序

任務描述

相關知識

代碼：??

?第2關：插入排序

任務描述

相關知識

插入排序

代碼：??

第3關：歸并排序

任務描述

相關知識

歸并排序

原理

代碼：??

?第4關：快速排序

任務描述

相關知識

快速排序

代碼：??

?第5關：堆排序

任務描述

相關知識

堆

堆的性質

堆排序

用大根堆排序的基本思想

大根堆排序算法的基本操作

代碼：??

---

第1關：選擇排序

任務描述

給定一組無序的數(shù)據(jù)，如果要把它們從小到大重新排序，我們要如何實現(xiàn)這個排序功能呢？

本關任務：實現(xiàn)選擇排序。

相關知識

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

上圖是一個從小到大排序的選擇排序過程。第一次，我們從初始序列中找出了最小的元素11，把它放到第一位；第二次我們從剩下的元素中找出最小的元素13，把它放到第二位，以此類推，直到所有元素從小到大排好序。

代碼：??

package step1;

/**
 * Created by sykus on 2018/3/20.
 */
public class SelectionSort {

    /**
     * 選擇排序
     *
     * @param arr
     */
    public static void sort(int arr[]) {
        /********** Begin *********/
        int n=arr.length;//數(shù)組長度
        for(int i=0;i<n-1;i++){//從第一個數(shù)開始比較，第一位存放最小的，第二位存放第二小的，以此推類
            for(int j=i+1;j<n;j++){//查找i下標以及之后的最小值，放在i的位置
                if(arr[i]>arr[j]){//如果小就交換
                    int t=arr[i];//t存儲arr[i]的值
                    arr[i]=arr[j];//arr[i]賦arr[j]的值
                    arr[j]=t;//arr[j]賦值t，即為arr[i]的值
                }
            }
            print(arr);//一個輸出的方法，在下面可以看到
        }
        /********** End *********/
    }

    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

以下是測試樣例：

測試輸入：2 8 7 1 3 5 6 4 預期輸出：

?第2關：插入排序

任務描述

上一關我們實現(xiàn)了選擇排序，本關我們實現(xiàn)另外一種排序方法：插入排序。

本關任務：實現(xiàn)插入排序。

相關知識

插入排序

插入排序的基本操作就是將一個數(shù)據(jù)插入到已經排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)。

假設我們輸入的是5，1，4，2，3，我們從第二個數(shù)字開始，這個數(shù)字是1，我們的任務只要看看1有沒有正確的位置，我們的做法是和這個數(shù)字左邊的數(shù)字來比，因此我們比較1和5，1比5小，所以我們就交換1和5，原來的排列就變成了1，5，4，2，3。

接下來我們看第三個數(shù)字有沒有在正確的位置。這個數(shù)字是4，它的左邊數(shù)字是5，4比5小，所以我們將4和5交換，排列變成了1，4，5，2，3我們必須繼續(xù)看4有沒有在正確的位置，4的左邊是1，1比4小，4就維持不動了。

再來看第四個數(shù)字，這個數(shù)字是2，我們將2和它左邊的數(shù)字相比，都比2大，所以就將2一路往左移動，一直移到2的左邊是1，這時候排序變成了1，2，4，5，3。

最后，我們檢查第五個數(shù)字，這個數(shù)字是3，3必須往左移，一直移到3的左邊是2為止，所以我們的排列就變成了1，2，3，4，5，排序完成。

插入排序示例

?如果難以理解，可以看作，第一次對前兩個數(shù)排序，第二次對前三個數(shù)排序，第n次對第n+1個數(shù)排序，即可得插入排序的排序順序

代碼：??

package step2;

/**
 * Created by sykus on 2018/3/20.
 */
public class InsertionSort {

    public static void sort(int arr[]) {
        /********** Begin *********/
        int n=arr.length;//存儲數(shù)組長度
        for(int i=1;i<n;i++){//從第二位數(shù)開始插入
            int j=i;//存儲需要插入數(shù)的下標
            int t=arr[j];//存儲需要插入數(shù)的值
            while(j>0 && t<arr[j-1]){//從后往前開始找比需要插入值大的值
                arr[j]=arr[j-1];//如果大就后移一位
                j--;//繼續(xù)往前找
            }
            arr[j]=t;//最后將需要插入數(shù)插入j下標的位置
            print(arr);//一個輸出的方法，在下面可以看到
        }
        /********** End *********/
    }

    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

以下是測試樣例：

測試輸入：

1. 6
2. 1 5 4 3 2 6

預期輸出：

第3關：歸并排序

任務描述

本關任務：實現(xiàn)歸并排序。

相關知識

歸并排序

歸并排序(Merge Sort)是建立在歸并操作上的一種有效的排序算法。歸并是指將若干個已排序的子序列合并成一個有序的序列。若將兩個有序序列合并成一個有序序列，稱為二路歸并。

原理

假設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1。然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復，直到得到一個長度為n的有序序列為止。

上圖是一個二路歸并排序過程示例，經過三次歸并操作后完成了排序。

代碼：??

package step3;

/**
 * Created by sykus on 2018/3/20.
 */
public class MergeSort {

    /**
     * lo, hi都是指下標
     */
    public static void sort(int arr[], int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            merge(arr, lo, mid, hi);
            print(arr);
        }
    }

    private static void merge(int arr[], int p, int q, int r) {
        /********** Begin *********/
        //歸并排序將兩部分合并
        int n=arr.length;//存儲數(shù)組長度
        int[] t=new int[n];//定義一個數(shù)組用于存儲排序后的數(shù)組
        int i=p,j=q+1,k=i;;//第一部分的左邊界,第二部分的左邊界,t的初始下標為第一部分的左邊界
        while(i<=q&&j<=r){//如果兩部分都不超過他們的右邊界則繼續(xù)合并
            if(arr[i]<arr[j]){//比大小，小的先放入排序數(shù)組里
                t[k++]=arr[i++];//繼續(xù)往后比較
            }else{//比大小，小的先放入排序數(shù)組里
                t[k++]=arr[j++];//繼續(xù)往后比較
            }
        }
        //當有一個部分的越界后，另一個部分可能還沒找完
        while(i<=q){//再找一遍，確保找完
            t[k++]=arr[i++];
        }
        while(j<=r){//再找一遍，確保找完
            t[k++]=arr[j++];
        }
        for(int l=p;l<=r;l++){//將排序數(shù)組的順序返回arr數(shù)組
            arr[l]=t[l];
        }
        /********** End *********/
    }

    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

以下是測試樣例：

測試輸入：

1. 6
2. 1 5 4 3 2 6

預期輸出：

?第4關：快速排序

任務描述

本關任務：實現(xiàn)快速排序。

相關知識

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

快速排序

快速排序的基本思想是： 1．先從數(shù)列中取出一個數(shù)作為基準數(shù)。 2．將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。 3．再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)。

現(xiàn)在假設我們對6 1 2 7 9 3 4 5 10 8這10個數(shù)進行排序。首先在這個序列中找一個數(shù)作為基準數(shù)。為了方便，取第一個數(shù)6作為基準數(shù)。接下來，需要將這個序列中所有比基準數(shù)大的數(shù)放在6的右邊，比基準數(shù)小的數(shù)放在6的左邊，類似下面這種排列： 3 1 2 5 4 6 9 7 10 8 具體過程是：從右往左找比6小的數(shù)，從左往右找6大的數(shù)，然后把這兩個數(shù)交換，如下圖所示，

最后得到3 1 2 5 4 6 9 7 10 8。

我們接著在對6的左右區(qū)間分別進行同樣的操作。會得到類似1 2 3 5 4和8 7 9 10的排列。直到區(qū)間只有一個數(shù)，處理結束。

代碼：??

package step4;

/**
 * Created by sykus on 2018/3/20.
 */
public class QuickSort {

    public void sort(int arr[], int low, int high) {
        /********** Begin *********/
        int i=low;//左邊界，為默認主元，所以從low+1開始找，所以下面循環(huán)++i，i先加1
        int j=high+1;//右邊界，high+1，所以下面循環(huán)--j，j先減1
        //主元默認為左邊第一個數(shù)，arr[low]
        while(i<j){//i大于j則跳出
            while(j>low && arr[--j]>=arr[low]);//從右往左找一個比主元小的數(shù)
            while(i<high && arr[++i]<=arr[low]);//從左往右找一個比主元大的數(shù)
            if(i<j)//如果i小于j就交換
            {
            int t=arr[j];
            arr[j]=arr[i];
            arr[i]=t;
            print(arr);//每次交換都要輸出
            }
            else break;//i大于j則跳出
        }
        int t=arr[j];//交換下標j與主元的位置
        arr[j]=arr[low];
        arr[low]=t;
        print(arr);//一個輸出方法
        if(i>low) sort(arr,low,j-1);//如果i沒越界，將右邊界左移，左邊界默認為主元從
        if(j<high)sort(arr,j+1,high);//如果j沒越界，將左邊界右移
        /********** End *********/
    }


    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

以下是測試樣例：

測試輸入：

1. 10
2. 6 1 2 7 9 3 4 5 10 8

預期輸出：

?第5關：堆排序

任務描述

本關任務：在本關，我們將實現(xiàn)另一種排序算法——堆排序(heapsort)。

相關知識

堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因為根據(jù)大根堆的要求可知，最大的值一定在堆頂。

堆

堆（Heap）是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象。 當一個含有n個元素的數(shù)組{k1?, k2?... ki?...kn?},當且僅當滿足下列關系時稱之為堆： (ki? <= k2i?, ki? <= k2i?+1)或者(ki? >= k2i?, ki? >= k2i?+1), (i = 1, 2, 3, 4... n/2)

即，如果用堆中的元素依次從上至下，從左至右構建一棵完全二叉樹，那么這棵二叉樹的任意節(jié)點的值都大于其子節(jié)點的值(或都小于其子結點的值)，將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

堆的性質

通常堆是通過一維數(shù)組來實現(xiàn)的。在索引起始位置為1的情形中： 父節(jié)點i的左子節(jié)點在位置 (2i); 父節(jié)點i的右子節(jié)點在位置 (2i+1);

大根堆堆頂元素最大

堆排序

堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最?。┻@一特征，使得選取最大（或最小）關鍵字變得簡單。

用大根堆排序的基本思想

1. 先將初始數(shù)組R[1..n]構造成一個大根堆，此堆為初始的無序區(qū)。
2. 再將關鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
3. 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
4. 直到無序區(qū)只有一個元素為止。

大根堆排序算法的基本操作

1. 建堆，建堆是不斷調整堆的過程，從len/2處開始調整，一直到第一個節(jié)點，此處len是堆中元素的個數(shù)。
2. 調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節(jié)點i和它的孩子節(jié)點left(i),right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪?jié)點i而是它的一個孩子節(jié)點，那邊交換節(jié)點i和該節(jié)點，然后再調用調整堆過程，這是一個遞歸的過程。
3. 堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據(jù)元素構建堆。然后將堆的根節(jié)點取出(一般是與最后一個節(jié)點進行交換)，將前面len-1個節(jié)點繼續(xù)進行堆調整的過程，然后再將根節(jié)點取出，這樣一直到所有節(jié)點都取出。

代碼：??

package step5;

/**
 * Created by sykus on 2018/3/20.
 */
public class HeapSort {

    public static void sort(int arr[]) {
        /********** Begin *********/
        int n=arr.length;//存儲數(shù)組長度
        //先將初始數(shù)組數(shù)據(jù)從上到下從左到右擺成一個完全二叉樹
        for(int i=n/2-1;i>=0;i--){//從n/2-1的下標開始
            BuildPile(arr,i,n);//導入數(shù)組以及當前需要調整的數(shù)的下標，數(shù)組長度
        }
        for(int i=n-1;i>0;i--){
            int t=arr[0];//將第一個數(shù)即最大值與最后一個沒被排好的數(shù)交換
            arr[0]=arr[i];
            arr[i]=t;
            BuildPile(arr,0,i);//從0~i重新建堆
            print(arr);//一個輸出方法，下面可以看見
        }
    }
    //需要自己寫一個遞歸方法
public static void BuildPile(int[] arr,int f,int n){
        int max=f;//存儲最大值的下標
        int lc=2*f+1;//左子樹下標
        int rc=2*f+2;//右子樹下標
        if(lc<n && arr[lc]>arr[max]){//如果下標沒有超過數(shù)組表示存在，比較大小
            max=lc;//如果大就存儲
        }
        if(rc<n && arr[rc]>arr[max]){//如果下標沒有超過數(shù)組表示存在，比較大小
            max=rc;//如果大就存儲
        }
        if(f==max)//如果最大值是本身則返回
        {
            return;
        }
        //否則交換，他們的值
            int t=arr[f];
            arr[f]=arr[max];
            arr[max]=t;
            f=max;//查找max值的左右子樹
            BuildPile(arr,f,n);
    }
        /********** End *********/
    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

以下是測試樣例：

測試輸入：

1. 8
2. 2 8 7 1 3 5 6 4

預期輸出：

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

到了這里，關于Java數(shù)據(jù)結構之排序(頭歌平臺，詳細注釋)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！