Nxlogn排序算法篇

归并排序

归并排序就是先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并，相当于二叉树的后序遍历。

模板如下

class Merge {

    // 用于辅助合并有序数组
    int[] temp;

    public static void sort(int[] nums) {
        // 先给辅助数组开辟内存空间
        temp = new int[nums.length];
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }

    // 将子数组 nums[lo..hi] 进行排序
    void sort(int[] nums, int lo, int hi) {
        if (lo == hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    void merge(int[] nums, int lo, int mid, int hi) {
        // 先把 nums[lo..hi] 复制到辅助数组中，以便合并后的结果能够直接存入 nums
        for (int i = lo; i <= hi; i++) temp[i] = nums[i];

        // 数组双指针技巧，合并两个有序数组
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                // 右半边数组已全部被合并
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }
}

912. 排序数组

315. 计算右侧小于当前元素的个数

493. 翻转对

327. 区间和的个数

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列，快速排序相当于二叉树的前序遍历

public class QuickSort {

    private final Random random = new Random();

    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) return ;
        int p = partition(nums, lo, hi);
        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    private int partition(int[] nums, int lo, int hi) {
        int p = random.nextInt(hi - lo + 1) + lo;
        swap(nums, lo, p);
        int pivot = nums[lo];
        int i = lo + 1, j = hi;
        while (i <= j) {
            // while 结束后，[lo, i) 均 <= pivot
            while (i < hi && nums[i] <= pivot) i++;
            // while 结束后，(j, hi] 均 > pivot
            while (j > lo && nums[j] > pivot) j--;
            
            // ------ 若为降序，只需更改此处两行代码即可 ------
            // while (i < hi && nums[i] >= pivot) i++;
            // while (j > lo && nums[j] < pivot) j--;
            // ------------------- end -------------------
            
            if (i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

912. 排序数组

75. 颜色分类

思路

经典荷兰国旗问题，基于快排思想的双指针。考察的是「快速排序」的子过程 partition，即：通过一次遍历，把数组分成三个部分。

215. 数组中的第K个最大元素

思路

快速选择算法

剑指 Offer 40. 最小的k个数

堆排序

// 堆排序额外空间复杂度O(1)
  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)
	  }
      // O(N)
      for (int i = arr.length - 1; i >= 0; i--) {
          heapify(arr, i, arr.length);
      }
      int heapSize = arr.length;
      swap(arr, 0, --heapSize);
      // O(N*logN)
      while (heapSize > 0) { // O(N)
          heapify(arr, 0, heapSize); // O(logN)
          swap(arr, 0, --heapSize); // O(1)
      }
  }

  // arr[index]刚来的数，往上
  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;
      }
  }

  // arr[index]位置的数，能否往下移动
  public static void heapify(int[] arr, int index, int heapSize) {
      int left = index * 2 + 1; // 左孩子的下标
      while (left < heapSize) { // 下方还有孩子的时候
          // 两个孩子中，谁的值大，把下标给largest
          // 1）只有左孩子，left -> largest
          // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
          // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
          int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
          // 父和较大的孩子之间，谁的值大，把下标给largest
          largest = arr[largest] > arr[index] ? largest : index;
          if (largest == index) {
              break;
          }
          swap(arr, largest, index);
          index = largest;
          left = index * 2 + 1;
      }
  }

  public static void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
  }