[TOC]

排序算法

简单选择排序(了解)

基本思路：不断的从未排序的区域中选择出最小（大）的元素放入到排序的数组区域中；
时间复杂度:最好=平均=最差:O(n^2);
空间复杂度：O(1)
不稳定

public int[] selectSort(int[] nums){
    int len = nums.length;
    for(int i = 0 ; i < len ; i++){
        int min = i;
        for(int j = i ; j < len ; j++){
            if (nums[j] < nums[min]){
                min = j;
            }
        }
        swap(nums,min,i);
    }
    return nums;
}

public void swap(int[] nums,int i,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

插入排序(熟悉)

基本思路：从第一个元素开始，依次从后选择一个元素，然后跟前面排好序的区域进行比较，插入到合适的位置中；
时间复杂度:最好：O(n);平均=最差:O(n^2);
空间复杂度：O(1)
- 特点：可以提前终止内存循环，在数组几乎有序的前提下，插入排序的时间复杂度可以达到O(N);

稳定

  public int[] insertSort(int[] nums){
      int len = nums.length;
      for(int i = 1 ; i < len ; i++){
          int temp = nums[i];
          int j = i;
          while(j > 0 && nums[j-1] > temp){
              nums[j] = nums[j-1];
              j--;
          }
          nums[j] = temp;
      }
      return nums;
  }

归并排序

基本思路:先两两拆分递归至一个元素，然后依次往上让相邻的子数组进行排序。分而治之加上对两个已经排好序的数组合并为一个新的排序数组；
时间复杂度：平均=最差=最好：O(nlogn)
空间复杂度：O(n)

稳定 || 不稳定：可以选择稳定也可以不稳定，区别在于将前后两个数组进行排序放入临时数组时，nums[l]与nums[r]的比较是< 还是 <= ;<=就会保持原来的位置。

class Solution {
  public int[] sortArray(int[] nums) {
      mergeSrot(nums,0,nums.length-1,new int[nums.length]);
      return nums;
  }
    
  public void mergeSrot(int[] nums,int left,int right,int[] temp){
      if (left >= right){
          return;
      }

      int mid = left+(right-left)/2;
      mergeSrot(nums,left,mid,temp);
      mergeSrot(nums,mid+1,right,temp);
        
      //本身就有序了，不需要在进行操作。
      if (nums[mid] < nums[mid+1]){
          return;
      }
      int l = left;
      int r = mid+1;
      int index = l;
      while(l <= mid && r <= right){
          if (nums[l] <= nums[r]){
              temp[index++] = nums[l++];
          }else{
              temp[index++] = nums[r++];
          }
      }
      while(index <= right) temp[index++] = l==(mid+1)?nums[r++]:nums[l++];
      for(int i = left;i<=right;i++){
          nums[i] = temp[i];
      }
  }
}

快速排序

基本思路：分治；每次选择数组中的一个元素（一般是第一个），然后从尾部开始比较，当尾部指针指向的元素小于选择的元素，与头指针进行交换，然后再从头指针开始寻找比选择元素大的元素，与尾部指针交换，再从尾部开始，直到首位相邻；因为是分治，所以数组会被不断的折半；
时间复杂度:最好=平均=O(nlogn);最差O(n^2)
空间复杂度：O(logn)
不稳定

class Solution {
    private static final Random RANDOM = new Random();

    public int[] sortArray(int[] nums){
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums,int left,int right){
        if (left >= right){
            return;
        }

        int pivot = partition(nums,left,right);
        quickSort(nums,left,pivot-1);
        quickSort(nums,pivot+1,right);
    }

    public int partition(int[] nums,int left,int right){
        int randomIndex = RANDOM.nextInt(right - left + 1) + left;
        swap(nums, left, randomIndex);
        int lt = left;
        int pivot = nums[lt];

        for(int i = left+1;i <= right ; i++){
            if (nums[i] < pivot){
                lt++;
                swap(nums,lt,i);
            }
        }
        swap(nums,left,lt);
        return lt;
    }    
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

这段代码优化的点： 1.不是选择数组中的第一个元素，而是随机选取一个，这样才能使算法的复杂度平均，不然很容易就变为插入排序了。 2.在根据pivot数组左右分割时，将pivot放在第一个，然后(left,lt]表示小于pivot的元素，依次遍历当前数组，若遍历到元素小于lt，则lt后移一位，然后将小于pivot的元素交换过来，相当于将小于pivot的元素都移到前面。遍历完成之后，此时小于pivot的元素值就都在(left,lt]，再讲left与lt交换，此时pivot就在它最终的位置上，小于pivot的值都在他前面了

堆排序

基本思路：以大根堆为例，将一维的数组看成一个完成二叉树，保证每个分支节点都符合堆；
　堆：大根堆就是左右子节点都小于父节点，小根堆就是左右子节点都大于父节点
调整堆：将首位元素交换后，需要重新将当前最大的元素调整到根节点，从根节点开始依次找出子节点较大的那个节点，然后交换上去，直到没有比他大的或者到底的； 初建堆：就是将原来树调整为堆。
时间复杂度：平均=最差=最好：O(nlong)
空间复杂度：O(1);
不稳定
堆排序的过程，可以看这个视频：数据结构排序算法之堆排序演示

    public int[] heapSort(int[] nums) {
        int len = nums.length;
        // 将数组整理成堆
        buildHeap(nums);

        // 循环不变量：区间 [0, i] 堆有序
        for (int i = len - 1; i >= 1; ) {
            // 把堆顶元素（当前最大）交换到数组末尾
            swap(nums, 0, i);
            // 逐步减少堆有序的部分
            i--;
            // 下标 0 位置下沉操作，使得区间 [0, i] 堆有序
            siftDown(nums, 0, i);
        }
        return nums;
    }

    /**
     * 将数组整理成堆（堆有序）;
     * 因为数据本身是用数组表示一棵完全二叉树，所以最后一个有子节点的根节点就为(len-1)/2
     * 所以我们只需要对0~(len-1)/2个节点进行调整
     *
     * @param nums
     */
    private void buildHeap(int[] nums) {
        int len = nums.length;
        // 只需要从 i = (len - 1) / 2 这个位置开始逐层下移
        for (int i = (len - 1) / 2; i >= 0; i--) {
            siftDown(nums, i, len - 1);
        }
    }

    /**
     * 调整的思路:
     * 当前节点k，他的左节点为 2*k + 1 右节点为 2*k + 2;
     * 如果他的左右节点都存在(不超过end)，则先获取他们中的最大值下标j
     * 然后将该值与根节点(k)比较，如果根节点小，则将j与k交换(根节点下移)
     * 交换完成之后,k=j，来到原根节点被交换下来的位置，继续判断他是否需要被继续交换下去。
     * @param nums
     * @param k    当前下沉元素的下标
     * @param end  [0, end] 是 nums 的有效部分
     */
    private void siftDown(int[] nums, int k, int end) {
        while (2 * k + 1 <= end) {
            int j = 2 * k + 1;
            if (j + 1 <= end && nums[j + 1] > nums[j]) {
                j++;
            }
            if (nums[j] > nums[k]) {
                swap(nums, j, k);
            } else {
                break;
            }
            k = j;
        }
    }
    
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

排序常用的api

Arrays.sort()

指针对数组类型的排序

int[] a = {9, 8, 7, 2, 3, 4, 1, 0, 5};
Arrays.sort(a);
for(int i = 0; i < a.length; i ++) {
    System.out.print(a[i] + " ");
}

如果要自定义排序规则，不能用基本类型的数组，因为要用到泛型。

Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 5};
Arrays.sort(a,(o1,o2)->{
    return o2-o1;
});
for(int i = 0; i < a.length; i ++) {
    System.out.print(a[i] + " ");
}

Collections.sort()

针对List等Collection容器的排序api

    List<Character> charList = new ArrayList<>(map.keySet());
    Collections.sort(charList,(c1,c2)->{
        return map.get(c2)-map.get(c1);
    });

优先队列PriorityQueue

    PriorityQueue<Map.Entry<Character,Integer>> items = new PriorityQueue<>((o1,o2)->o2.getValue()-o1,getValue());