认识O(NlogN)的排序_笔记02

目录

• • • • • 04_归并排序
        • • 小和问题
          • 逆序对问题
        • 05_快速排序
        • • 荷兰国旗问题

本文知识点记录自左程云 算法与数据结构基础到高级教程 图片截取自视频中

04_归并排序

时间复杂度：O(N*logN)

前三种排序浪费了大量的“比较行为”，而归并排序，在递推到递归出口，要进行回溯的时候，每一次排序都会把两个各自排好序的小部分并在一起，成为一个更大的部分，再使其重新变为一个整体有序的部分。这样不断归并，直到数组的规模已经回到原始大小。

//归并排序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,l,mid,r);}//合并左右两个有序小数组，使其整体有序public static void merge(int[] arr, int l, int m, int r){    int[] aux = new int[r-l+1];    int p1 = l, p2 = m + 1;    int i = 0;    while(p1 <= m && p2 <= r){ aux[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];    }    while(p1 <= m){ aux[i++] = arr[p1++];    }    while(p2 <= r){ aux[i++] = arr[p2++];    }    for (int j = 0; j < aux.length; j++) { arr[l+j] = aux[j];    }}

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。等价于找当前数右边，比当前数大的数字个数，这个数字个数再乘以当前数，当前数不断在数组中向前推进，把每一个数得到的小和相加就是整个数组的小和。

找一个数左边比其小的数→找当前数右边比它大的数

例如{2,5,8,3}的小和为：11

public class Test_smallSum {    /***/    public static int smallSum(int[] arr, int l, int r) { if (l == r) {     return 0; } int sum = 0; int mid = l + ((r - l) >> 1); sum += smallSum(arr, l, mid) + smallSum(arr, mid + 1, r) + merge(arr, l, mid, r); return sum;    }    //外排序，合并两个小数组，使其变为较大规模的数组，递增排序    public static int merge(int[] arr, int l, int m, int r){ int[] aux = new int[r-l+1]; int p1 = l, p2 = m + 1; int i = 0,ret = 0; while(p1 <= m && p2 <= r){     ret += arr[p1] < arr[p2] ? arr[p1]*(r-p2+1) : 0;     aux[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= m){     aux[i++] = arr[p1++]; } while(p2 <= r){     aux[i++] = arr[p2++]; } for (int j = 0; j < aux.length; j++) {     arr[l+j] = aux[j]; } return ret;    }    public static void main(String[] args) { int[] test = new int[]{3, 7, 4, 9, 8, 3, 6, 1, 4, 3, 2}; System.out.println(smallSum(test,0,test.length-1));    }}//输出结果为53

逆序对问题

逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。

如果存在正整数 i, j 使得 1 ≤ i A[j]，则 这个有序对称为 A 的一个逆序对，也称作逆序数。

public class Test_InversePairNum {    /**逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。    如果存在正整数 i, j 使得 1 ≤ i  A[j]，则  这个有序对称为 A 的一个逆序对，也称作逆序数。     打印所有的逆序对,并返回逆序对数*/    //归并排序    public static int inverseNum(int[] arr, int l, int r) { if (l == r) {     return 0; } int num = 0; int mid = l + ((r - l) >> 1); num += inverseNum(arr, l, mid) + inverseNum(arr, mid + 1, r) + merge(arr, l, mid, r); return num;    }    //外排序，合并两个小数组，使其变为较大规模的数组，递减排序    public static int merge(int[] arr, int l, int m, int r){ int[] aux = new int[r-l+1]; int p1 = l, p2 = m + 1; int i = 0,ret = 0; while(p1 <= m && p2 <= r){     if(arr[p1] > arr[p2]){  ret += r-p2+1;  for (int j = p2; j <= r; j++) {      System.out.print("<"+arr[p1]+","+arr[j]+">\t");  }     }     aux[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= m){     aux[i++] = arr[p1++]; } while(p2 <= r){     aux[i++] = arr[p2++]; } for (int j = 0; j < aux.length; j++) {     arr[l+j] = aux[j]; } return ret;    }    public static void main(String[] args) { int[] arr = new int[]{3,8,2,4,9,0,1,7,5,6}; int num = inverseNum(arr,0,arr.length-1); System.out.println(); System.out.println("共有"+num+"对逆序对"); System.out.println("打印排序后的数组:"); for(int i : arr){     System.out.print(i+"\t"); }    }}//输出<8,2><3,2><8,4><7,6><7,5><9,7><9,6><9,5><9,1><9,0><8,7><8,6><8,5><8,1><8,0><4,1><4,0><3,1><3,0><2,1><2,0>共有21对逆序对打印排序后的数组:9876543210

//快速排序，时间复杂度为O(NlogN),空间复杂度为O(logN)的版本public static void quickSort(int[] arr, int l, int r){    if(arr == null || l >= r){ return;    }    swap(arr, l+(int)(Math.random()*(r-l+1)),r);    int[] p = process(arr, l, r);    quickSort(arr, l,p[0]-1);    quickSort(arr,p[1]+1,r);}/** * 当arr[i]num时，交换arr[i]与arr[p2-1],然后p2--,i不发生自增！！！ * 当i==p2时，结束循环，arr已经被分为以num为边界的三部分 * @param arr * @param l * @param r * @return */public static int[] process(int[] arr, int l, int r){    int num = arr[r];    int i = l;    int p1 = l - 1, p2 = r + 1;    //p1代表小于num的区域右边界，p2代表大于num的区域左边界    while(i <= r && i < p2){ if(arr[i] < num){     swap(arr,i,p1+1);     p1++;     i++; }else if(arr[i] > num) {     swap(arr, i, p2 - 1);     p2--; }else{     i++; }    }    int[] ret = new int[2];    ret[0] = p1 + 1;    ret[1] = p2 - 1;    return ret;}//swappublic static void swap(int[] arr, int a, int b){    int temp = arr[a];    arr[a] = arr[b];    arr[b] = temp;}//printpublic static void  print(int[] arr){    for(int i : arr){ System.out.print(i+"\t");    }}