这节课我们来学习一些排序算法

常见排序算法

选择排序：

选择排序 时间复杂度O(N^2)，额外空间复杂度O(1)

public static void selectionSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   for (int i = 0; i < arr.length - 1; i++) {  
      int minIndex = i;  
      for (int j = i + 1; j < arr.length; j++) {  
         minIndex = arr[j] < arr[minIndex] ? j : minIndex;  
      }  
      swap(arr, i, minIndex);  
   }  
}

选择排序

image-20211118223856264

操作次数：

image-20211118224945776

冒泡排序

public static void bubbleSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   for (int e = arr.length - 1; e > 0; e--) {  
      for (int i = 0; i < e; i++) {  
         if (arr[i] > arr[i + 1]) {  
            swap(arr, i, i + 1);  
         }  
      }  
   }  
}

冒泡排序

image-20211118230002969

插入排序

时间复杂度O(N^2)，额外空间复杂度O(1) 算法流程按照最差情况来估计时间复杂度

public static void insertionSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   for (int i = 1; i < arr.length; i++) {  
      for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {  
         swap(arr, j, j + 1);  
      }  
   }  
}

查案入排序

二分搜索

二分法的详解与扩展

1.在一个有序数组中，找某个数是否存在

public static boolean exist(int[] sortedArr, int num) {  
   if (sortedArr == null || sortedArr.length == 0) {  
      return false;  
   }  
   int L = 0;  
   int R = sortedArr.length - 1;  
   int mid = 0;  
   while (L < R) {  
      mid = L + ((R - L) >> 1);  
      if (sortedArr[mid] == num) {  
         return true;  
      } else if (sortedArr[mid] > num) {  
         R = mid - 1;  
      } else {  
         L = mid + 1;  
      }  
   }  
   return sortedArr[L] == num;  
}

2.在一个有序数组中，找>=某个数最左侧的位置

image-20211122212706298

// 在arr上，找满足>=value的最左位置  
public static int nearestIndex(int[] arr, int value) {  
   int L = 0;  
   int R = arr.length - 1;  
   int index = -1;  
   while (L < R) {  
      int mid = L + ((R - L) >> 1);  
      if (arr[mid] >= value) {  
         index = mid;  
         R = mid - 1;  
      } else {  
         L = mid + 1;  
      }  
   }  
   return index;  
}

3.局部最小值

public static int getLessIndex(int[] arr) {  
   if (arr == null || arr.length == 0) {  
      return -1; // no exist  
   }  
   if (arr.length == 1 || arr[0] < arr[1]) {  
      return 0;  
   }  
   if (arr[arr.length - 1] < arr[arr.length - 2]) {  
      return arr.length - 1;  
   }  
   int left = 1;  
   int right = arr.length - 2;  
   int mid = 0;  
   while (left < right) {  
      mid = (left + right) / 2;  
      if (arr[mid] > arr[mid - 1]) {  
         right = mid - 1;  
      } else if (arr[mid] > arr[mid + 1]) {  
         left = mid + 1;  
      } else {  
         return mid;  
      }  
   }  
   return left;  
}

image-20211122213344986

总结

二分不一定用在有序数组里，在某些可以确定去掉另一半数据的情况下也可以使用

归并排序

  1. 整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
  2. 让其整体有序的过程里用了排外序方法
  3. 利用master公式来求解时间复杂度
  4. 归并排序的实质

时间复杂度O(N*logN)，额外空间复杂度O(N)

public static void mergeSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   mergeSort(arr, 0, arr.length - 1);  
}  
  
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[] help = new int[r - l + 1];  
   int i = 0;  
   int p1 = l;  
   int p2 = m + 1;  
   while (p1 <= m && p2 <= r) {  
      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];  
   }  
   while (p1 <= m) {  
      help[i++] = arr[p1++];  
   }  
   while (p2 <= r) {  
      help[i++] = arr[p2++];  
   }  
   for (i = 0; i < help.length; i++) {  
      arr[l + i] = help[i];  
   }  
}

归并排序

image-20211122222431739

master公式

image-20211122222637310

实质

没有浪费每次小排序的结果，最后合并在一起，而选择排序，冒泡等n^2的浪费了每次比较结果

扩展

小和问题和逆序对问题
小和问题 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。
例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16

逆序对问题 在一个数组中，左边的数如果比右边的数大，则这两个数 构成一个逆序对，请打印所有逆序对。

image-20211122224045759

image-20211122224001994

public static int smallSum(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return 0;  
   }  
   return mergeSort(arr, 0, arr.length - 1);  
}  
  
public static int mergeSort(int[] arr, int l, int r) {  
   if (l == r) {  
      return 0;  
   }  
   int mid = l + ((r - l) >> 1);  
   return mergeSort(arr, l, mid)   
         + mergeSort(arr, mid + 1, r)   
         + merge(arr, l, mid, r);  
}  
  
public static int merge(int[] arr, int l, int m, int r) {  
   int[] help = new int[r - l + 1];  
   int i = 0;  
   int p1 = l;  
   int p2 = m + 1;  
   int res = 0;  
   while (p1 <= m && p2 <= r) {  
      res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;  //通过右边下标相减确定当前这次比较比左边这个数要大的个数，即有多少个小和
      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];  //相等的时候，先拷贝右组，而且不产生小和，如果先拷贝左组，则不能确定右组有多少个数比拷贝的这个数大。必须保证右边严格大于左边
   }  
   while (p1 <= m) {  
      help[i++] = arr[p1++];  
   }  
   while (p2 <= r) {  
      help[i++] = arr[p2++];  
   }  
   for (i = 0; i < help.length; i++) {  
      arr[l + i] = help[i];  
   }  
   return res;  
}

逆序对问题

同理

快排

荷兰国旗

问题一

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

1.把数组范围中的最后一个数作为划分值，然后把数组分成三个部分: 左侧<划分值、中间=划分值、右侧>划分值
2.对左侧范围和右侧范围，递归执行

分析

  1. 划分值越靠近两侧，复杂度越高;划分值越靠近中间，复杂度越低
  2. 可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)

问题二(荷兰国旗问题)
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放 在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度 O(N)

image-20211122225834119

image-20211122225925272

image-20211122230308259

public static int[] partition(int[] arr, int l, int r, int p) {  
   int less = l - 1;  
   int more = r + 1;  
   while (l < more) {  
      if (arr[l] < p) {  
         swap(arr, ++less, l++);  
      } else if (arr[l] > p) {  
         swap(arr, --more, l);  
      } else {  
         l++;  
      }  
   }  
   return new int[] { less + 1, more - 1 };  
}

快排1.0 n^2

快排

image-20211122230732031

快排2.0

荷兰国旗方法，因为搞定了一批=5的数 所以快一些 n^2

image-20211122230945780

快排3.0

随机快速排序(改进的快速排序)

1)在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分 成三个部分:
左侧<划分值、中间=划分值、右侧>划分值
2)对左侧范围和右侧范围，递归执行

3)时间复杂度为O(N*logN)

public static void quickSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   quickSort(arr, 0, arr.length - 1);  
}  
  
public static void quickSort(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);  
      quickSort(arr, l, p[0] - 1);  
      quickSort(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 };  
}

随机快排

空间复杂度

最差的情况O(n) 开n个数组， 最优logn，形式为树， 树的子节点可以在递归回退的时候销毁，节省空间

堆

是一种特殊完全二叉树

  1. 堆结构就是用数组实现的完全二叉树结构
  2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
  3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
  4. 堆结构的heapInsert与heapify操作
  5. 堆结构的增大和减少
  6. 优先级队列结构，就是堆结构

将堆用一个连续的数组的来表示，如下图，则 i位置的左节点：2*i+1，右节点 2*1 +2，父节点（i-1)/2

image-20211123220927700

大根堆

在这个二叉树，每个子树最大值都是根 image-20211123221004334

小根堆

同理

构建大根堆

每添加一个节点，跟自己的父节点（i-1）/2比较 ,如果比根节点大，则在数组中互换位置

image-20211123221241976 image-20211123221259847

public static void heapInsert(int[] arr, int index) {  
   while (arr[index] > arr[(index - 1) / 2]) {  
      swap(arr, index, (index - 1) /2);  
      index = (index - 1)/2 ;  
   }  
}

gif 从数组: 2,7,26,25,19,17,1,90,3,36 创建大根堆（O(N log N)）

大根堆最大值

index = 0

Heapify（堆化）

提取最大值并保持大根堆结构（Heapify）

// index 某个数在index位置，能否往下移动
public static void heapify(int[] arr, int index, int size) {  
   int left = index * 2 + 1;  //左孩子下标
   while (left < size) {  //有做孩子
   //取左右孩子最大的一个 left+1即为右孩子
      int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  
      //父节点跟较大的子节点比较
      largest = arr[largest] > arr[index] ? largest : index;  
      if (largest == index) {  
         break;  
      }  
      //子节点比父节点大，则交换
      swap(arr, largest, index);  
      //子节点与父节点交换后，index继续向下走
      index = largest;  
      //当前index的左节点，继续while循环
      left = index * 2 + 1;  
   }  
}

移除最大值并保持堆结构

更新某个位置的值

某个位置去掉并保持堆结构

先将该位置改成最大值+1，然后heapinsert，然后remove max，然后向下heapify

时间复杂度

logn

空间复杂度

1

堆排序

  1. 先将数组改成堆 heapinsert （一个一个往堆里添加）

  2. 将0位置上的数（最大值）跟最后一个数做交换，然后heapsize–，将最大值与堆断联系

  3. 然后将剩下的数字从0位置向下heapify

  4. 重复2、3

  5. heapsize=0的时候完成排序，最后数组从小到大排列

  6. 先让整个数组都变成大根堆结构，建立堆的过程:

    1. 从上到下的方法，时间复杂度为O(N*logN)
    2. 从下到上的方法，时间复杂度为O(N)

  7. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调 整堆，一直周而复始，时间复杂度为O(N*logN)

  8. 堆的大小减小成0之后，排序完成

代码

public static void heapSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   for (int i = 0; i < arr.length; i++) {  
      heapInsert(arr, i);  
   }  
   int size = arr.length;  
   swap(arr, 0, --size);  
   while (size > 0) {  
      heapify(arr, 0, size);  
      swap(arr, 0, --size);  
   }  
}  
  
public static void heapInsert(int[] arr, int index) {  
   while (arr[index] > arr[(index - 1) / 2]) {  
      swap(arr, index, (index - 1) /2);  
      index = (index - 1)/2 ;  
   }  
}  
  
public static void heapify(int[] arr, int index, int size) {  
   int left = index * 2 + 1;  
   while (left < size) {  
      int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  
      largest = arr[largest] > arr[index] ? largest : index;  
      if (largest == index) {  
         break;  
      }  
      swap(arr, largest, index);  
      index = largest;  
      left = index * 2 + 1;  
   }  
}

时间复杂度

Nlogn

优化

优化在构建堆的时候：用到了整个数组(一次性给你全部数)，不按照一个一个向里添加。 从底层节点，从右到左，开始向上heapify，一层一层heapify。 如下图， 数组中有n个数，想象成满二叉树，最底层有n/2个叶节点，这层向下heapify需要n/2次，不需要移动，倒数第二层有n/4个节点，每个节点heapify最多移动两步，以此类推: image-20211123224323311 运算推理: image-20211123224406470 复杂度为O(n)，而用heapinsert为logN 所以快了一点 但底部区域未经优化，还是nlogn，所以整体复杂度还是nlogn

    public static void heapSort(int[] arr) {  
      if (arr == null || arr.length < 2) {  
         return;  
      }  
//    for (int i = 0; i < arr.length; i++) {  
//       heapInsert(arr, i);//采用heapinsert的复杂度为logN  
//    }  
      //采用从底层heapify的方式构建堆，优化这步骤的复杂度为N      
      for (int i = arr.length-1; i >=0 ; i--) {  
         heapify(arr,i,arr.length);  
      }  
      //而这个while循环，时间复杂度一定是nlogN,所以最终时间复杂度还是不变，  
      // 仅仅优化了第一步      
      int size = arr.length;  
      swap(arr, 0, --size);  
      while (size > 0) {  
         heapify(arr, 0, size);  
         swap(arr, 0, --size);  
      }  
   }

扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。 

public void sortedArrDistanceLessK(int[] arr, int k) {  
   PriorityQueue<Integer> heap = new PriorityQueue<>();  
   int index = 0;  
   for (; index < Math.min(arr.length, k); index++) {  
      heap.add(arr[index]);  //首先将前k个数放入heap
   }  
   int i = 0;  
   for (; index < arr.length; i++, index++) {  
      heap.add(arr[index]);  //继续放入heap
      arr[i] = heap.poll();  //取出小根堆的最小值，从index=0的位置依次放入数组
   }  
   while (!heap.isEmpty()) {  
      arr[i++] = heap.poll();  //都加入到堆后，将剩下的heap里的数取出来放入数组
   }  
}

优先级队列底层PriorityQueue=小根堆，如果你如果只是需要一个堆，可以直接用系统提供的，如果想要删掉某个位置并保持堆这种功能，则需要自己写堆结构。

  • 堆单次扩容代价( n*logN )/n = logN

  • 某些情况得手写堆来实现 删掉某个位置并保持堆 的功能

构建小根堆的时候传入一个比较器

PriorityQueue<Student> maxHeapBasedAge = new PriorityQueue<>(new AgeDescendingComparator());

桶排序

基于比较数据情况（大小范围）定制

基数排序

仍然需要根据数据情况定制（根据进制桶）

  1. 先根据个位数排序入桶

  2. 然后从左到右将桶中的数据倒出来

    image-20211123230939014

  3. 然后根据十位数入桶 并倒出来

    image-20211123231012494

  4. 然后百位数排序并倒出来

    image-20211123231035687

// only for no-negative value  
public static void radixSort(int[] arr) {  
   if (arr == null || arr.length < 2) {  
      return;  
   }  
   radixSort(arr, 0, arr.length - 1, maxbits(arr));  
}  
  
public static int maxbits(int[] arr) {  
   int max = Integer.MIN_VALUE;  
   for (int i = 0; i < arr.length; i++) {  
      max = Math.max(max, arr[i]);  
   }  
   int res = 0;  
   while (max != 0) {  
      res++;  
      max /= 10;  
   }  
   return res;  
}  
  
public static void radixSort(int[] arr, int begin, int end, int digit) {  
   final int radix = 10;  
   int i = 0, j = 0;  
  
   int[] bucket = new int[end - begin + 1];  
   for (int d = 1; d <= digit; d++) {  
      int[] count = new int[radix];  
      for (i = begin; i <= end; i++) {  
         j = getDigit(arr[i], d);  
         count[j]++;  
      }  
      for (i = 1; i < radix; i++) {  
         count[i] = count[i] + count[i - 1];  
      }  
      for (i = end; i >= begin; i--) {  
         j = getDigit(arr[i], d);  
         bucket[count[j] - 1] = arr[i];  
         count[j]--;  
      }  
      for (i = begin, j = 0; i <= end; i++, j++) {  
         arr[i] = bucket[j];  
      }  
   }  
}  
  
public static int getDigit(int x, int d) {  
   return ((x / ((int) Math.pow(10, d - 1))) % 10);  
}

分析:

  1. 桶排序思想下的排序都是不基于比较的排序
  2. 时间复杂度为O(N)，额外空间负载度O(M)
  3. 应用范围有限，需要样本的数据状况满足桶的划分

排序算法稳定性

排序算法的稳定性及其汇总 同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定 性的;否则就没有。

不具备稳定性的排序: 选择排序、快速排序、堆排序

具备稳定性的排序: 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。

image-20211124200210693

常见的坑

  1. 归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴趣可以搜“归并排序 内部缓存法”
  2. “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O(N^2)
  3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜“01 stable sort”
  4. 所有的改进都不重要，因为目前没有找到时间复杂度O(N*logN)，额外空间复 杂度O(1)，又稳定的排序
  5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对 次序不变，碰到这个问题，可以怼面试官。

工程上对排序的改进

  1. 充分利用O(N*logN)和O(N^2)排序各自的优势
  2. 稳定性的考虑