O(NlogN)复杂度的排序

一、归并排序

时间复杂度

• 平均：O(NlogN)
• 最好：O(NlogN)
• 最差：O(NlogN)

额外空间复杂度

O(N)

稳定性

稳定

基本思路

• arr左右两边先排好序，然后merge整合
• p1指向左边最左侧，p2指向右边最左侧
• p1、p2进行比较，哪边小就将值加入辅助数组help，然后++
• 直到p1或p2越界，将另一边剩下的加入辅助数组help
• 最后将辅助数组中的数放回arr

代码实现

public static void mergeSort(int[] arr,int L,int R){
    if(L >= R) return;
    int mid = L + ((R-L) >> 1);
    mergeSort(arr,L,mid);//对左边进行排序
    mergeSort(arr,mid+1,R);//对右边进行排序
    merge(arr,mid,L,R);
}
//整合
public static void merge(int[] arr, int mid, int L, int R){
    int[] help = new int[R-L+1];
    int i = 0;//help数组下标
    int p1 = L;//左侧下标
    int p2 = mid+1;//右侧下标
    while(p1 <= mid && p2 <= R){
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++]:arr[p2++];
    }
    //如果右侧已经越界，左侧还没遍历完，将剩下的加入help
    while (p1 <= mid){
        help[i++] = arr[p1++];
    }
    //如果左侧已经越界，右侧还没遍历完，将剩下的加入help
    while (p2 <= R){
        help[i++] = arr[p2++];
    }
    //将排好序的部分放回原数组
    for(int j = 0;j < help.length; j++){
        arr[L + j] = help[j];
    }
}

额外空间复杂度

O(N)，help数组最大为N。

扩展

1、小和问题

描述

每个数的左边比它小的数的和的总和。

也可理解为：m的右边有n个比m大的，就会有n个m的和

基本思路

• 按归并排序方式，对左右两边进行递归排序
• 在排序的同时，计算左右两边单独的小和
• 整合的时候，因为左右两边是已经排好序的，所以在p1所指小于p2所指时，可以算出共有p2到右边结尾个元素比p1所指的大。

实现代码

/**
     * 小和问题（归并排序扩展）
     * @return 小和总和
     */
public static int getMergeSortSmall(int[] arr, int L, int R){
    if(L >= R) return 0;
    int mid = L + ((R-L) >> 1);
    return getMergeSortSmall(arr,L,mid) +
        getMergeSortSmall(arr,mid+1,R) +
        mergeSamll(arr,L,mid,R);
}
/**
     * 小和问题左右整合并得到小和
     * @return
     */
public static int mergeSamll(int[] arr, int L, int mid, int R){
    int[] help = new int[R-L+1];
    int p1 = L;
    int p2 = mid+1;
    int i = 0;
    int sum = 0;
    while (p1 <= mid && p2 <= R){
        //关键
        sum += arr[p1] < arr[p2] ? arr[p1]*(R-p2+1) : 0;
        help[i++] = arr[p1] < arr[p2] ? arr[p1++]:arr[p2++];
    }
    while (p1 <= mid){
        help[i++] = arr[p1++];
    }
    while (p2 <= R){
        help[i++] = arr[p2++];
    }
    for (int j = 0;j < help.length; j++){
        arr[L+j] = help[j];
    }
    return sum;
}

2、逆序对问题

描述

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，计算所有逆序对个数。

基本思路

• 根据归并排序思路，左右两边先分别排好序，在排序的同时分别计算两边的逆序对
• 排好序后两边整合，如果p1所指大于p2，则逆序对数量增加p1及其后面数个数
• 然后按归并排序正常排序即可

实现代码

/**
     * 逆序对问题（归并排序扩展）
     * @return 逆序对数量
     */
    public static int getInversionPair(int[] arr, int L, int R){
        if(L >= R) return 0;
        int mid = L + ((R-L) >> 1);
        return getInversionPair(arr,L,mid) +
                getInversionPair(arr,mid+1,R) +
                mergeInversionPair(arr,L,mid,R);
    }
    /**
     * 逆序对问题左右整合并得到逆序对数量
     * @return 逆序对数量
     */
    public static int mergeInversionPair(int[] arr, int L, int mid, int R){
        int[] help = new int[R-L+1];
        int p1 = L;
        int p2 = mid+1;
        int i = 0;
        int count = 0;
        while (p1 <= mid && p2 <= R){
            //关键
            count += arr[p1] > arr[p2] ? mid-p1+1 : 0;
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++]:arr[p2++];
        }
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        for (int j = 0;j < help.length; j++){
            arr[L+j] = help[j];
        }
        return count;
    }

二、快速排序

时间复杂度

• 平均：O(NlogN)
• 最好：O(NlogN)
• 最差：O(N^2)

额外空间复杂度

O(logN) ~ O(N)

稳定性

不稳定

基本思路

• 在当前待排数组中随机选取一个数作为划分值，并与最后一个元素交换
• 将划分值左边的数分成小于划分值、等于划分值、大与划分值三个区域
• 然后用上述同样的方式对标记位两边的数组进行排序。

实现代码

public static void quickSort3(int[] arr, int L, int R){
    if(L < R){
        swap(arr,L + (int)(Math.random()*(R-L+1)),R);
        int[] p = partition(arr,L,R);//划分
        quickSort3(arr,L,p[0]-1);
        quickSort3(arr,p[1]+1,R);
    }
}
public static int[] partition(int[] arr, int L, int R){
    int less = L - 1;//小于区的右边界
    int more = R;//大于区的左边界
    while(L < more){
        if(arr[L] < arr[R]){ //当前数小于划分值
            swap(arr,++less,L++);//跟小于区的右边界的后一个数交换位置，然后看下一个
        }else if(arr[L] > arr[R]){//当前数大于划分值
            swap(arr,--more,L);//跟大于区的左边界的前一个数交换位置，然后不动，下一次将这个换过来的值与划分值比较
        }else{ //当前数等于划分值
            L++;//直接看下一个
        }
    }
    swap(arr,more,R);//将划分值与大于区的左边界进行交换，完成一次划分
    return new int[]{less+1,more};
}

三、堆排序

堆结构

• 用数组实现的完全二叉树结构
• 完全二叉树中每棵子树的最大值都在根节点就是大根堆
• 完全二叉树中每棵子树的最小值都在根节点就是小根堆
• 堆结构主要操作：heapInsert和heapify
• 优先级队列结构，就是堆结构（java默认小根堆）
• 辅助操作：
  • 找当前位置i节点的父节点：(i-1)/2
  • 找当前位置i节点的左子节点：i*2+1
  • 找当前位置i节点的右子节点：i*2+2

时间复杂度

• 平均：O(NlogN)
• 最好：O(NlogN)
• 最差：O(NlogN)

额外空间复杂度

O(1)

稳定性

不稳定

基本思路

• 先将数组按最大堆排好序
• 然后将堆顶位置元素和堆尾位置元素交换，同时堆大小-1
• 然后将调整大小后的堆重新进行堆化（重新排成最大堆），再交换堆顶和堆尾，堆大小-1
• 循环上一步，直到堆大小减至0

实现代码

//主要过程
public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    //将数组中的数加入堆（按最大堆排序）
    for(int i = 0;i < arr.length;i++){	//O(N)
        heapInsert(arr,i);	//O(logN)
    }
    int heapSize = arr.length;
    //按最大堆排好序后，将堆顶位置和堆尾位置交换，同时堆大小-1
    swap(arr,0,--heapSize);
    //再将堆按最大堆排好序，堆顶和堆尾交换，同时堆大小-1，循环直到堆大小为0
    while(heapSize > 0){	//O(N)
        heapify(arr,0,heapSize);//O(logN)
        swap(arr,0,--heapSize);//O(1)
    }
}
//堆插入，按最大堆方式插入，某个数在index位置上，看它能否向上走
private static void heapInsert(int[] arr, int index){
    //如果index位置上的数比其根节点大，则交换位置，并继续往上直到不发生交换
    while(arr[index] > arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index - 1)/2;
    }
}
//堆化，重新将堆排成最大堆，某个数在index位置上，看它能否下走
private static void heapify(int[] arr, int index, int heapSize){
    //先找到其左子节点
    int left = index*2 + 1;
    //当左子节点下标小于堆大小时
    while(left < heapSize){
        //若左子节点不是最后一个，将左右节点中大的那个的下标给maxIndex
        int maxIndex = left+1 < heapSize && arr[left] < arr[left+1] ? left+1:left;
        //父节点和较大子节点比较，父节点较小则交换
        if(arr[index] < arr[maxIndex]){
            swap(arr,index,maxIndex);
            //交换后来到较大子节点位置，继续向下看
            index = maxIndex;
            left = index*2 + 1;
        }else{//不小则直接退出循环
            break;
        }
    }
}

扩展

已知一个几乎有序的数组（如果要把数组排好序的话，每个元素移动的距离不超过k，并且k相对于数组来说较小），对其进行排序。

基本思路

• 先将数组中前k+1个元素加进小根堆（可以使用java中的优先队列PriorityQueue）
• 则这k+1个元素中必定会有数组中最小值，加入小根堆后即在堆顶位置
• 将堆顶位置弹出并放到数组中0位置
• 再将k+1后面的元素依次加进堆，每加一个就弹出堆顶，依次放入数组中
• 最后将堆中剩下的结点依次弹出，放入数组中

代码实现

//堆排序扩展，排一个“几乎有序的数组”
public static void sortArrayDistanceLessK(int[] arr, int k){
    //创建一个小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    //index记录已经加进堆的数组元素的最后一个元素在数字中的位置
    int index = 0;
    //将数组前k+1个元素加进堆
    for(;index < Math.min(arr.length,k+1);index++){
        heap.add(arr[index]);
    }
    int i = 0;
    //将数组中最小值（即堆顶位置）放入数组0位置
    arr[0] = heap.poll();
    //将后面的元素加进堆并弹出
    for(;index < arr.length;index++){
        heap.add(arr[index]);
        arr[++i] = heap.poll();
    }
    while(!heap.isEmpty()){
        arr[++i] = heap.poll();
    }
    //上面i=0到while这段是为了方便理解
    //也可以写成这样
    //int i = 0;
    //for(;index < arr.length;index++,i++){
    //		heap.add(arr[index]);
    //      arr[i] = heap.poll();
    //}
    //while (!heap.isEmpty()){
    //      arr[i++] = heap.poll();
    //}
}