十大经典排序之：归并排序 ｜桶排序

归并排序

归并排序原理

什么是归并排序呢？归并排序，首先要理解什么是归并：将两个的有序数列合并成一个有序数列，我们称之为”归并”。

思想：归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括”从上往下”和”从下往上”2种方式。也是采用分治法的一个非常典型的应用。

算法实现

1、算法描述
Step 1：将n个元素分成两个含n/2元素的子序列（左边可能比右边多1个数）
Step 2：用MS将两个子序列递归排序，直到所有部分的元素个数都为1。（最后可以将整个原序列分解成n个子序列）
Step 3：从最底层开始逐步合并两个排好序的数列。

2、图示

3、算法空间复杂度和时间复杂度
时间复杂度：

• 最坏：o（$n{\log }_{2}n$）
• 最好：o（$n{\log }_{2}n$）
• 平均：o（$n{\log }_{2}n$）

空间复杂度（辅助存储）：o（n）
稳定性：稳定

例题

用归并排序将以下数列按照从小到大的顺序输出：123,45,6,22,99,1,38,41,-6,0

java代码：

 import java.util.Arrays; public class Test { 
    public static void mergeSort(int[] arr, int first, int last){ 
    if(null == arr || arr.length < 0 || first == last){ 
    return; } mergeSort(arr, first, (last + first)/2); mergeSort(arr, (last + first)/2 + 1, last); sort(arr, first, (last + first)/2, last); } //这个方法是合并两个有序数组，就好像直接插入排序算法一样 public static void sort(int[] arr, int first, int mid, int last ){ 
    int[] temp = new int[last - first + 1]; int i = 0; int j = 0; int index = 0; while(i < mid - first + 1 && j < last - mid){ 
    if(arr[first + i] >= arr[mid + 1 + j]){ 
    temp[index] = arr[mid + 1 + j]; j++; index++; } else { 
    temp[index] = arr[first + i]; i++; index++; } } while(i < mid - first + 1){ 
    temp[index] = arr[first + i]; index++; i++; } while(j < last - mid){ 
    temp[index] = arr[mid + 1 + j]; index++; j++; } for(int k = first, n = 0; k <= last; k++, n++){ 
    arr[k] = temp[n]; } } public static void main(String[] args) { 
    int[] arr=new int[]{ 
   123,45,6,22,99,1,38,41,-6,0}; //归并排序 mergeSort(arr,0,9); System.out.println("归并排序后的结果是:"); System.out.println(Arrays.toString(arr)); } } 

桶排序

桶排序原理

所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。是一种又快又简便的方法，桶排序可以看做计数排序的升级版。

它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。

为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

算法实现

1、算法描述

1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把元素再放回原来的序列中。

2、图示

3、算法空间复杂度和时间复杂度
时间复杂度：

• 最坏：o（$n^2$）
• 最好：o（$n$）或者 o（$n+k$）
• 平均：o（$n$）或者 o（$n+k$）

空间复杂度（辅助存储）：o（$n$）或者 o（$n+k$）

桶排序的平均时间复杂度为 o（$n+n^2/k+k$） （将值域平均分成 n 块 + 排序 + 重新合并元素），当k 约等于n 时为o（$n$）

稳定性：稳定

例题

java代码：

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class Test { 
    public static void bucketSort(int[] arr){ 
    int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ 
    max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } //桶数 int bucketNum = (max - min) / arr.length + 1; List<List<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ 
    bucketArr.add(new ArrayList<Integer>()); } //将每个元素放入桶 for(int i = 0; i < arr.length; i++){ 
    int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ 
    Collections.sort(bucketArr.get(i)); } //将各非空桶中的元素组合起来 int k=0; for(int i=0;i<bucketNum;i++){ 
    if(bucketArr.get(i).size()!=0){ 
    for(int n:bucketArr.get(i)){ 
    arr[k]=n; k++; } } } } public static void main(String[] args) { 
    int[] arr=new int[]{ 
   123,45,6,22,99,1,38,41,-6,0}; //桶排序 bucketSort(arr); System.out.println("桶排序后的结果是:"); System.out.println(Arrays.toString(arr)); } }