题解 | #排序#_牛客博客

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

输入：
[5,2,3,1,4]
返回值：
[1,2,3,4,5]

本题主要考察几种常见的排序算法，除了冒泡排序和选择排序的时间复杂度比较高，会出现运行超时现象，其他排序算法可以采用。
思路：
方法一：用库函数Arrays.sort

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
       Arrays.sort(arr);
        return arr;
    }
}

复杂度：
时间复杂度： $Arrays.sort ()$ 是经过调优排序算法，时间复杂度达到 $图片说明$

方法二：快速排序：
通过一趟排序将待排记录分割成独立的两部分，以基准为分界的两部分，一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述
快速排序使用分治法来把一个串分为两个子串。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        QuickSort(arr,0,arr.length-1);
        return arr;
    }
    void QuickSort(int[]arr,int low,int high)
    {
        //递归终止条件
        if(low<high)
        {
            int partition=Partition(arr,low,high);
            QuickSort(arr,low,partition-1);
            QuickSort(arr,partition+1,high);
        }

    }

    int Partition(int[]arr,int low,int high){
        //每次排序都以首元素为基准
        int pivot=arr[low];
        while(low<high)
        {
            //从最右边开始扫描，使得大于基准的元素位于基准右边
            while(low<high&&arr[high]>=pivot)high--;
            arr[low]=arr[high];
            //再从左边扫描，使得小于基准的元素位于基准左边
            while(low<high&&arr[low]<=pivot)low++;
            arr[high]=arr[low];
        }
        //low和high相遇的位置就是基准元素应该放置的位置
        arr[low]=pivot;
        return low;
    }

}

复杂度：
时间复杂度：平均时间复杂度为 $图片说明$
空间复杂度：使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 $图片说明$ ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 $O(n)$ 。所以我们一般认为快速排序的空间复杂度为
$图片说明$
方法三：堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（小根堆）或者大于（大根堆）它的父节点，构建大根堆可实现数组的递增排序。

算法描述

将初始待排序关键字序列 $(R1,R2….Rn)$ 构建成大根堆，此堆为初始的无序区；
将堆顶元素 $R[1]$ 与最后一个元素 $R[n]$ 交换，此时得到新的无序区 $(R1,R2,……Rn-1)$ 和新的有序区 $(Rn)$ ,且满足 $R[1,2…n-1]<=R[n]$
由于交换后新的堆顶 $R[1]$ 可能违反堆的性质，因此需要对当前无序区 $(R1,R2,……Rn-1)$ 调整为新堆，然后再次将 $R[1]$ 与无序区最后一个元素交换，得到新的无序区 $(R1,R2….Rn-2)$ 和新的有序区 $(Rn-1,Rn)$ 。不断重复此过程直到有序区的元素个数为 $n-1$ ，则整个排序过程完成。

图片说明

代码如下：

import java.util.*;


public class Solution {
    /**
代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
将给定数组排序
@param arr int整型一维数组 待排序的数组
@return int整型一维数组
*/
public int[] MySort (int[] arr) {
    // write code here
    //初始建大根堆
    int len=arr.length-1;
    BuildMaxHeap(arr,len);
    for(int i=len;i>=0;i--)
    {
    //堆顶元素值最大，堆底元素和堆顶元素交换
        int temp=arr[i];
        arr[i]=arr[0];
        arr[0]=temp;
        //调整除堆底元素的剩余元素
        HeapAdjust(arr,0,i);
    }
    return arr;
}
void HeapAdjust(int[]arr,int k,int len)
{
    //temp暂存子树的根结点
    int temp=arr[k];
    //从根结点开始向下搜索
    for(int i=2*k;i<len;i*=2)
    {
    //如果右孩子的值大于左孩子的值，取较大孩子的下标
        if(i<len-1&&arr[i]<arr[i+1]){
            i++;
        }
        //根结点本身最大，跳出循环
        if(temp>=arr[i])break;
        else{
        //将arr[i]调整到双亲结点，并修改k的值便于继续向下筛选
        arr[k]=arr[i];
        k=i;}
        //筛选结束，根结点最终放入位置
    }
    arr[k]=temp;
}
void BuildMaxHeap(int[]arr,int len){
    //从最后一个非终端结点开始按顺序从后往前调整
    for(int i=(len-1)/2;i>=0;i--)
    {
        HeapAdjust(arr,i,len);
    }
}
}

复杂度：
时间复杂度：与二叉树的高度有关， $图片说明$
空间复杂度： $O(n)$
方法四：归并排序：

左指针定位在数组的最左边，右指针定位到数组的最右边，不断找到数组的中点，从中点处分割，直到左右指针相遇，递归终止
将分割出来的每一个部分排序，也就是进入merge函数,每一轮排序都是基于上一轮左右数组已排序好的情况下再排序
排序部分是从中点处分割数组为 $l1,l2$ ，逐轮比较 $l1，l2$ ，将较小值放入辅助数组 $temp$ 中，最后如果 $l1$ 或者 $l2$ 有剩余部分元素，将剩余部分直接拷贝到 $temp$ 中接下来的位置

图片说明
代码如下：

import java.util.*;
public class Solution {
    /**
代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
将给定数组排序
@param arr int整型一维数组 待排序的数组
@return int整型一维数组
*/
public int[] MySort (int[] arr) {
    // write code here
    mergeSort(arr,0,arr.length-1);
    return arr;
}
void merge(int[]arr,int left,int mid,int right)
{
    //声明一个和排序数组相同大小的辅助数组
    int[]temp=new int[right-left+1];
    int l1=left,l2=mid+1,i=0;
    //每次都比较两个有序数组中的元素，将较小元素拷贝到辅助数组
    while(l1<=mid&&l2<=right)
    {
        if(arr[l1]<arr[l2])temp[i++]=arr[l1++];
        else temp[i++]=arr[l2++];
    }
    //将剩余元素放入temp数组中
    while(l1<=mid)temp[i++]=arr[l1++];
    while(l2<=right)temp[i++]=arr[l2++];
    //将temp数组拷贝到arr指定位置中
    for(int j=0;j<i;j++)
    {
        arr[left+j]=temp[j];
    }
}
void mergeSort(int[]arr,int left,int right)
{
    if(left>=right)
        return ;
    int mid=left+(right-left)/2;
    //先左边排序
    mergeSort(arr,left,mid);
    //再右边排序
    mergeSort(arr,mid+1,right);
    //合并左右数组
    merge(arr,left,mid,right);

} 
}

复杂度：
时间复杂度：归并排序的平均时间复杂度是归并树的高度，因此为 $图片说明$
空间复杂度：与辅助数组的大小有关,因此为 $O(n)$ ;
方法五：插入排序
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；

重复步骤2~5。

代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 将给定数组排序
   * @param arr int整型一维数组 待排序的数组
   * @return int整型一维数组
   */
  public int[] MySort (int[] arr) {
       InsertSort(arr,arr.length);
       return arr;
  }
  void InsertSort(int[]arr,int len)
  {
      for(int i=1;i<arr.length;i++)
      {
          //temp记录要插入的值
          int temp=arr[i],j;
          for(j=i-1;j>=0&&arr[j]>temp;j--){
              arr[j+1]=arr[j];
          }
          arr[j+1]=temp;
      }
  }  
}

复杂度：
时间复杂度：最好情况下是 $O(n)$ ,最坏情况下是 $图片说明$ ,平均时间复杂度为 $图片说明$
空间复杂度：只需用到 $O(1)$ 的额外空间