Java数据结构之排序(头歌平台，详细注释)

目录

第1关：选择排序

任务描述

相关知识

代码：??

?第2关：插入排序

任务描述

相关知识

插入排序

代码：??

第3关：归并排序

任务描述

相关知识

归并排序

原理

代码：??

?第4关：快速排序

任务描述

相关知识

快速排序

代码：??

?第5关：堆排序

任务描述

相关知识

堆

堆的性质

堆排序

用大根堆排序的基本思想

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

代码：??

---

第1关：选择排序

任务描述

给定一组无序的数据，如果要把它们从小到大重新排序，我们要如何实现这个排序功能呢？

本关任务：实现选择排序。

相关知识

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

上图是一个从小到大排序的选择排序过程。第一次，我们从初始序列中找出了最小的元素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;//数组长度
        for(int i=0;i<n-1;i++){//从第一个数开始比较，第一位存放最小的，第二位存放第二小的，以此推类
            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关：插入排序

任务描述

上一关我们实现了选择排序，本关我们实现另外一种排序方法：插入排序。

本关任务：实现插入排序。

相关知识

插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

假设我们输入的是5，1，4，2，3，我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了1，5，4，2，3。

接下来我们看第三个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了1，4，5，2，3我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。

再来看第四个数字，这个数字是2，我们将2和它左边的数字相比，都比2大，所以就将2一路往左移动，一直移到2的左边是1，这时候排序变成了1，2，4，5，3。

最后，我们检查第五个数字，这个数字是3，3必须往左移，一直移到3的左边是2为止，所以我们的排列就变成了1，2，3，4，5，排序完成。

插入排序示例

?如果难以理解，可以看作，第一次对前两个数排序，第二次对前三个数排序，第n次对第n+1个数排序，即可得插入排序的排序顺序

代码：??

package step2;

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

    public static void sort(int arr[]) {
        /********** Begin *********/
        int n=arr.length;//存储数组长度
        for(int i=1;i<n;i++){//从第二位数开始插入
            int j=i;//存储需要插入数的下标
            int t=arr[j];//存储需要插入数的值
            while(j>0 && t<arr[j-1]){//从后往前开始找比需要插入值大的值
                arr[j]=arr[j-1];//如果大就后移一位
                j--;//继续往前找
            }
            arr[j]=t;//最后将需要插入数插入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关：归并排序

任务描述

本关任务：实现归并排序。

相关知识

归并排序

归并排序(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;//存储数组长度
        int[] t=new int[n];//定义一个数组用于存储排序后的数组
        int i=p,j=q+1,k=i;;//第一部分的左边界,第二部分的左边界,t的初始下标为第一部分的左边界
        while(i<=q&&j<=r){//如果两部分都不超过他们的右边界则继续合并
            if(arr[i]<arr[j]){//比大小，小的先放入排序数组里
                t[k++]=arr[i++];//继续往后比较
            }else{//比大小，小的先放入排序数组里
                t[k++]=arr[j++];//继续往后比较
            }
        }
        //当有一个部分的越界后，另一个部分可能还没找完
        while(i<=q){//再找一遍，确保找完
            t[k++]=arr[i++];
        }
        while(j<=r){//再找一遍，确保找完
            t[k++]=arr[j++];
        }
        for(int l=p;l<=r;l++){//将排序数组的顺序返回arr数组
            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关：快速排序

任务描述

本关任务：实现快速排序。

相关知识

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序

快速排序的基本思想是： 1．先从数列中取出一个数作为基准数。 2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。

现在假设我们对6 1 2 7 9 3 4 5 10 8这10个数进行排序。首先在这个序列中找一个数作为基准数。为了方便，取第一个数6作为基准数。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列： 3 1 2 5 4 6 9 7 10 8 具体过程是：从右往左找比6小的数，从左往右找6大的数，然后把这两个数交换，如下图所示，

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

我们接着在对6的左右区间分别进行同样的操作。会得到类似1 2 3 5 4和8 7 9 10的排列。直到区间只有一个数，处理结束。

代码：??

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开始找，所以下面循环++i，i先加1
        int j=high+1;//右边界，high+1，所以下面循环--j，j先减1
        //主元默认为左边第一个数，arr[low]
        while(i<j){//i大于j则跳出
            while(j>low && arr[--j]>=arr[low]);//从右往左找一个比主元小的数
            while(i<high && arr[++i]<=arr[low]);//从左往右找一个比主元大的数
            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关：堆排序

任务描述

本关任务：在本关，我们将实现另一种排序算法——堆排序(heapsort)。

相关知识

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆

堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 当一个含有n个元素的数组{k1?, k2?... ki?...kn?},当且仅当满足下列关系时称之为堆： (ki? <= k2i?, ki? <= k2i?+1)或者(ki? >= k2i?, ki? >= k2i?+1), (i = 1, 2, 3, 4... n/2)

即，如果用堆中的元素依次从上至下，从左至右构建一棵完全二叉树，那么这棵二叉树的任意节点的值都大于其子节点的值(或都小于其子结点的值)，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质

通常堆是通过一维数组来实现的。在索引起始位置为1的情形中： 父节点i的左子节点在位置 (2i); 父节点i的右子节点在位置 (2i+1);

大根堆堆顶元素最大

堆排序

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得选取最大（或最小）关键字变得简单。

用大根堆排序的基本思想

1. 先将初始数组R[1..n]构造成一个大根堆，此堆为初始的无序区。
2. 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
4. 直到无序区只有一个元素为止。

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

1. 建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。
2. 调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交换节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。
3. 堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。

代码：??

package step5;

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

    public static void sort(int arr[]) {
        /********** Begin *********/
        int n=arr.length;//存储数组长度
        //先将初始数组数据从上到下从左到右摆成一个完全二叉树
        for(int i=n/2-1;i>=0;i--){//从n/2-1的下标开始
            BuildPile(arr,i,n);//导入数组以及当前需要调整的数的下标，数组长度
        }
        for(int i=n-1;i>0;i--){
            int t=arr[0];//将第一个数即最大值与最后一个没被排好的数交换
            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]){//如果下标没有超过数组表示存在，比较大小
            max=lc;//如果大就存储
        }
        if(rc<n && arr[rc]>arr[max]){//如果下标没有超过数组表示存在，比较大小
            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

预期输出：