算法网课视频

左程云算法视频：https://player.bilibili.com/player.html?bvid=BV13g41157hK
视频p2，讲了几个排序算法和异或，题目比较经典。

石墨和语雀都可以上传 java文件，语雀可以在线预览，导出的 PDF 中代码段效果很好；石墨无法预览，导出的PDF中代码段没有高亮，效果还差。
而且语雀导出PDF中，还可以下载附件中的 java代码，石墨就不能下载，语雀YYDS！

排序算法

选择排序

源码：SelectionSort.java
完整版代码在附件中，包含主函数和其他测试方法。篇幅很长会导致页面显示效果不好，所以这里只截取关键步骤代码。

  1. public static void selectionSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     // 0 ~ N-1  找到最小值，在哪，放到0 位置上
  6.     // 1 ~ n-1  找到最小值，在哪，放到1 位置上
  7.     // 2 ~ n-1  找到最小值，在哪，放到2 位置上
  8.     /**
  9.          * 选择排序
  10.          * 每次内循环，找到当前元素中最小的值，调整到最前面，排序结果为升序
  11.          * 可以设置一个 k 值，实现 k 次循环，找到当前元素中 k个最小的元素
  12.          */
  13.     for (int i = 0; i < arr.length - 1; i++) {
  14.         int minIndex = i;
  16.         for (int j = i + 1; j < arr.length; j++) {
  17.             if (arr[j] < arr[minIndex]) {
  18.                 minIndex = j;           // 内循环，每次找到最小值的索引，赋值给minIndex
  19.             }
  20.         }
  21.         swap(arr, i, minIndex);         // 一次循环结束，把最小值交换到最前面
  22.     }
  23. }

冒泡排序

源码：BubbleSort.java
外层从后往前，内层循环，每次比较相邻元素，把较大值放后面，每次循环就能找到当前元素里最大的那个值了。

  1. public static void bubbleSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     /**
  6.      * 冒泡排序
  7.      * 稳定，
  8.      */
  9.     // 每次选出当前序列中最大的值，赋值给末尾索引处
  10.     for (int i = arr.length - 1; i > 0; i--) {
  11.         for (int j = 0; j < i; j++) {
  13.             if (arr[j] > arr[j + 1]) { // 每次比较相邻元素
  14.                 swap(arr, j, j + 1); // 大的元素往后挪
  15.             }
  16.         }
  17.     }
  18. }

插入排序

源码：InsertionSort.java

  1. public static void insertionSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     /**
  6.      * 插入排序
  7.      * 和打扑克牌的动作很像
  8.      */
  9.     for (int i = 1; i < arr.length; i++) {   // 0~i 上做到有序
  10.         for (int j = i - 1; j >= 0; j--) {  // j 从i相邻的位置开始往前遍历
  12.             if (arr[j] > arr[j + 1]) {
  13.                 swap(arr, j, j + 1);    // 往前遍历，把当前所有元素中较小的值往前挪
  14.             }
  15.         }
  16.     }
  17. }

归并排序

源码：MergeSort.java

  1. public static void mergeSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     process(arr, 0, arr.length - 1);
  6. }
  8. public static void process(int[] arr, int left, int right) {
  9.     if (left == right) {
  10.         return;
  11.     }
  13.     int mid = left + ((right - left) >> 1); // 不会溢出，且快速
  15.     process(arr, left, mid);            // 递归调用
  16.     process(arr, mid + 1, right);
  18.     merge(arr, left, mid, right);
  19. }
  21. // 递归版本
  22. public static void merge(int[] arr, int left, int mid, int right) {
  23.     int[] help = new int[right - left + 1]; // 帮助排序的数组
  25.     int i = 0;          // 主数组的游标
  26.     int p1 = left;      // 左边的游标
  27.     int p2 = mid + 1;   // 右边的游标
  29.     while (p1 <= mid && p2 <= right) {
  30.         // 可以简化成下面这一句代码
  31. //            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
  33.         if (arr[p1] <= arr[p2]) {
  34.             help[i++] = arr[p1++];
  35.         } else {
  36.             help[i++] = arr[p2++];
  37.         }
  38.     }
  40.     // 要么p1越界了，要么p2越界了
  41.     while (p1 <= mid) {
  42.         help[i++] = arr[p1++];  // 把未比较的元素复制到help数组
  43.     }
  44.     while (p2 <= right) {
  45.         help[i++] = arr[p2++];
  46.     }
  48.     for (i = 0; i < help.length; i++) {
  49.         arr[left + i] = help[i];    // 把排好序的元素复制到原数组对应位置上
  50.     }
  51. }

非递归版本：不容易理解，多看几遍。

  1. public static void mergeSort2(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  6.     int N = arr.length;
  7.     int mergeSize = 1;      // 步长
  9.     while (mergeSize < N) {
  10.         int left = 0;       // 当前左组的第一个位置
  12.         while (left < N) {
  13.             if (mergeSize >= N - left) {
  14.                 break;
  15.             }
  17.             int mid = left + mergeSize - 1;
  18.             int right = mid + Math.min(mergeSize, N - mid - 1);
  20.             merge(arr, left, mid, right);
  22.             left = right + 1; // 跳到下一个merge的左组位置
  23.         }
  25.         // 防止溢出
  26.         if (mergeSize > N / 2) {
  27.             break;
  28.         }
  29.         mergeSize <<= 1;    // 步长扩大一倍
  30.     }
  31. }

快速排序

源码：QuickSort.java
算法第四版，三切分快速排序。

  1. /**
  2.  * 快速排序，算法第四版
  3.  * 三切分，把数组分组三部分，小于，等于，大于
  4.  */
  5. public static void quickSort(int[] arr) {
  6.     if (arr == null || arr.length < 2) {
  7.         return;
  8.     }
  10.     process(arr, 0, arr.length - 1);
  11. }
  13. public static void process(int[] arr, int left, int right) {
  14.     if (left >= right) {
  15.         return;
  16.     }
  18.     int[] equalArea = partion(arr, left, right);    // 等于部分的边界数组
  20.     process(arr, left, equalArea[0] - 1);   // 递归处理左侧
  21.     process(arr, equalArea[1] + 1, right);   // 递归处理右侧
  22. }
  24. // 数组切分方法
  25. public static int[] partion(int[] arr, int left, int right) {
  26.     if (left >= right) {
  27.         return new int[]{-1, -1};
  28.     }
  30.     int lt = left;          // 小于切分元素的边界
  31.     int i = left + 1;       // 游标，用来遍历数组
  32.     int gt = right;         // 大于切分元素的边界
  34.     int pivot = arr[left];  // 这里是选择第一个元素为切分元素
  36.     while (i <= gt) {
  37.         if (arr[i] < pivot) {   // 5, 1, 9, 2, 8
  38.             swap(arr, lt++, i++);
  39.         } else if (arr[i] > pivot) {
  40.             swap(arr, i, gt--); // 大于区域边界往左侧扩展，当前i位置的数是交换过来的，大小未知，所以i不变
  41.         } else {
  42.             i++;    // 等于的话，i增加1，比较下一个
  43.         }
  44.     }
  45.     return new int[]{lt, gt};   // lt~gt上的都等于切分元素
  46. }

堆排序

源码：HeapSort.java
堆的结构很巧妙，值得多研究。

  1. public static void heapSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  6.     // 方法1：从无到有,建立大根堆
  7.     // 复杂度： O(N * logN)
  8. //        for (int i = 0; i < arr.length; i++) {
  9. //            heapInsert(arr, i);
  10. //        }
  12.     // 方法2：把数组看成建好的堆，再调整成大根堆
  13.     // 复杂度： O(N)
  14.     for (int i = arr.length - 1; i >= 0; i--) {
  15.         heapify(arr, i, arr.length);
  16.     }
  18.     int heapSize = arr.length;  // 用来控制堆的逻辑范围
  19.     // 最大值交换到末尾，缩小堆的逻辑范围，末尾元素还存在，但逻辑上不属于堆了
  20.     swap(arr, 0, --heapSize);
  22.     while (heapSize > 0) {
  23.         // 根结点是刚从末尾交换的元素，不一定符合大根堆要求，重新调整大根堆
  24.         heapify(arr, 0, heapSize);
  25.         swap(arr, 0, --heapSize);   // 最大值交换到末尾，堆范围逻辑缩小
  26.     }
  27. }
  29. // 建堆方法
  30. // 与父结点比较，直到调整到合适的位置
  31. public static void heapInsert(int[] arr, int index) {
  32.     // 大根堆
  33.     // 当前元素一直与它的父结点比较
  34.     while (arr[index] > arr[(index - 1) / 2]) {
  35.         swap(arr, index, (index - 1) / 2);
  36.         index = (index - 1) / 2;
  37.     }
  38. }
  40. // arr[index] 位置的数，能否向下移动
  41. public static void heapify(int[] arr, int index, int heapSize) {
  42.     int left = index * 2 + 1;
  44.     while (left < heapSize) {
  45.         int larger = left;
  46.         int right = left + 1;
  48.         if (right < heapSize && arr[left] < arr[right]) {
  49.             larger = right;
  50.         }
  51.         if (arr[index] > arr[larger]) {
  52.             break;      // 如果index大于两个子结点的较大者，就退出
  53.         }
  55.         swap(arr, index, larger);
  56.         index = larger;
  57.         left = index * 2 + 1;
  58.     }
  59. }