NC140：排序

题目链接

描述

给定一个数组，请你编写一个函数，返回该数组排序后的形式。

示例

输入：

[5,2,3,1,4]

返回值：

[1,2,3,4,5]

就是一个普普通通的排序，把数组里面的所有元素按从小到大的顺序排后输出即可。

方法一

快速排序

这里我们实现方法一中函数的快排

解题思路

快排是基于分治的思想实现的，在待排序的数列中，我们首先要找一个数字作为基准值，之后我们需要把这个待排序的数列中小于基准值的元素移动到待排序的数列的左边，把大于基准值的元素移动到待排序的数列的右边，这时我们就得到了两个相对有序的小数组。之后对两个小数组不断地划分，划分成更多的数组，直到每个数组的大小为1（只剩下一个元素）。这时我们的原数组排序完成。（中的快排好像每次划分为三份，不过我们这样已经足够快）相对与冒泡排序来讲快排每一次交换元素的跨度非常大，所以速度也会快很多。

算法步骤：

1. 确定基准值
2. 将小于基准值的放入其左边，大于的放入右边
3. 基准值将数组分为两个数组，并递归分别进入左右数组重复操作

图解

代码

class Solution {
    public int[] MySort(int[] arr) {
        quickSort(arr, 0,arr.length-1);     // 开始进入递归
        return arr;
    }

    public void quickSort(int[] L,int low,int high) {
        int pivot;
        if(low<high) {
            //将L[low,high]一分为二,算出基准值pivot,该值得位置固定,不用再变化
            pivot=partition(L,low,high);

            //对pivot两边的数组分别排序
            quickSort(L,low,pivot-1);
            quickSort(L,pivot+1,high);
        }
    }

    //  选择一个基准值(关键字) 把它放到某个位置 使其左边的值都比它小 右边的值都比它大
    public int partition(int[] L,int low,int high) {
        int pivotkey;
        pivotkey=L[low];
        //顺序很重要，要先从右边找
        while(low<high) {
            //从后往前找到比key小的放到前面去
            while(low<high && L[high]>=pivotkey) {  
                high--;
            }
            swap(L,low,high);
            //从前往后找到比key大的 放到后面去
            while(low<high && L[low]<=pivotkey) {  
                low++;
            }
            swap(L,low,high);
        } 
        //遍历所有记录  low的位置即为 key所在位置, 且固定,不用再改变
        return low;
    }

    //交换数组的两个位置
    public void swap(int[] L,int i,int j) {
        int temp=L[i];
        L[i]=L[j];
        L[j]=temp;

    }
}

时间复杂度：(平均每次确定数组一半相对于另一半的顺序)

空间复杂度：（在原数组上进行操作）

方法二

归并排序

我们这里介绍速度同样很快的排序算法归并排序

解题思路

归并排序是创建在归并操作上的一种有效的排序算法，算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。我们对待排序的数组不断的二分，直到每个数组只有一个元素，然后不断的两两将其按大小进行归并知道最后归并为一个数组，这时数组已经排好序。

算法步骤：

1. 将数组不断二分
2. 将数组两两按大小归并

图解

代码

class Solution {
    public int[] MySort(int[] arr) {
        //新建一个临时数组存放
        int[] tmp = new int[arr.length];

        // 开始进入递归
        mergeSort(arr, 0, arr.length - 1, tmp);

        return arr;
    }

    public void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        // tmp临时数组的索引
        int i = 0;

        //左边序列和右边序列起始索引
        int j = low, k = mid + 1;

        // 按顺序将两个数组归并为一个
        while (j <= mid && k <= high) {
            if (arr[j] < arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }

        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while (j <= mid) {
            tmp[i++] = arr[j++];
        }

        //若右边序列还有剩余，则将其全部拷贝进tmp[]中
        while (k <= high) {
            tmp[i++] = arr[k++];
        }

        // 将tmp数组返回arr
        for (int t = 0; t < i; t++) {
            arr[low + t] = tmp[t];
        }
    }

    public void mergeSort(int[] arr, int low, int high, int[] tmp) {
        if (low < high) {
            int mid = (low + high) >> 1;

            //对左边序列进行归并排序
            mergeSort(arr, low, mid, tmp);

            //对右边序列进行归并排序
            mergeSort(arr, mid + 1, high, tmp);

            //合并两个有序序列
            merge(arr, low, mid, high, tmp);
        }
    }
}

时间复杂度：(由图解可以知道每次对数组二分，直到每个数组长度为1，然后两两组合装回去)

空间复杂度：（只新建了一个临时的数组）