LeetCode刷题-04-排序

标签：ast   run   upload   https   array   ons   交换   长度   vat   

第四讲 排序

4.1 巨经典的排序算法

1. 冒泡排序（很简单）

• 平均时间复杂度 O(n^2) ，空间复杂度 O(1)，稳定

• 基本思想

  • 两个数比较大小，较大的数下沉，较小的数冒起来。

• 演示（图片来自菜鸟教程）

  

• 代码

  /**
   * 冒泡排序
   * @param array 待排序的数组
   */
  public static void bubbleSort(int[] array) {
      for(int i=0; ii; j--){
              if(array[j] 

2. 选择排序

• 平均时间复杂度 O(n^2) ，空间复杂度 O(1)，不稳定

• 基本思想

  • 遍历数组，依次找到第 i 小的元素，然后把它和第i 个元素交换位置

• 演示

  

• 代码

  /**
   * 选择排序
   * @param array 待排序的数组
   */
  public static void selectSort(int[] array) {
      for(int i=0;i

3. 插入排序

• 平均时间复杂度 O(n^2) ，空间复杂度 O(1)，稳定

• 基本思想

  • 在要排序的一组数中，假定前 i 个数已经排好序了，那么第 i+1 个数只需要插入到前面已经排好序的数组中即可

• 演示（图片来自菜鸟教程）

  

• 代码

  /**
   * 插入排序
   * @param array 待排序的数组
   */
  public void insertSort(int[] array) {
      for (int i = 0; i  0; j--) {
              if (array[j] 

4. 归并排序

• 平均时间复杂度 O(n log(n)) ，空间复杂度 O(n)，稳定

• 基本思想（分治）

  • 首先考虑如何合并两个有序数组
    • 我们只需要依次比较两个数组中的第一个数即可，谁小放到新数组中
  • 归并排序的主要思想就是归并两个有序数组。
    • 将原数组分成二组 A，B。如果A，B都是有序的，归并即可。
    • 但是A，B都不是有序的，那么就继续分。直到这个数组中只有1个数据的时候。
    • 这个时候可以认为他是有序的，然后依次向上合并
  • 总结：递归分解数组，然后再从小到大合并

• 演示（图片来自菜鸟教程）

  

• 代码

  /**
   * 归并排序
   * @param array 需要排序的数组
   * @return 排好序的数组
   */
  public int[] mergeSort(int[] array) {
      // 创建额外的空间
      int[] res = Arrays.copyOf(array, array.length);
      if (res.length 

5. 快速排序（很常用）

• 平均时间复杂度 O(n log(n)) ，空间复杂度 O(log n)，不稳定

• 算法思想（分治）

  • 选取一个key，对于比key大的，全部放到右边，对于比key小的，全部放到key的左边。这样key的位置就可以唯一确定了。然后对key两边的区间重复操作就可以确定所有元素的位置了

• 演示（图片来自菜鸟教程）

  

• 具体操作

  1. i=0，j=n-1，key=array[i]
  2. j 向前移动，找到第一个比 key 小的元素，把这个元素放到 i
  3. i 向后移动，找到第一个比 key 大的元素，将它放到 j 的位置
  4. 在 i 的地方放上 key
  5. 经过这么一步操作，就可以使得 [0,i-1] 中所有的元素都是比 i 小的，[j,n-1] 中的所有元素都是比 i 大 的，然后重复操作，直到 i==j 这样就满足了 array[0,i-1] 。然后 i左右两边的区间重复操作。

• 代码

  /**
   * @param array 需要排序区间所在的数组
   * @param left 区间的起始下标
   * @param right 区间的结束下标
   */
  public void quickSort(int[] array, int left, int right) {
      if (left = key) {
                  j--;
              }
              if (i 

6. 堆排序

• 平均时间复杂度 O(n+k) ，空间复杂度 O(k)，稳定

• 什么是堆？

  • 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。（注意是左右孩子而不是左右子树）

• 基本思想

  • 将待排序的数组构造成一个大顶堆。此时，堆顶的元素就是最大的，将堆顶元素和最后一个元素交换位置，然后重新构造大顶堆。
  • 我们不需要想构造一颗二叉树一样去构造堆，我们只需要按照以下规则进行对应即可：
    • 即数组下标为 i 的元素，他的左右孩子的下标是 2i+1 和 2i+2
  • 如此一来，我们就不需要额外的空间

• 演示

  

• 代码

  /**
   * 堆排序
   * @param array 待排序的数组
   */
  public void heapSort(int[] array) {
      // len表示的是未进行排序的长度
      int len = array.length;
      for (int i = 0; i = 0; j--) {
              int left = 2 * j + 1;
              int right = left + 1;
              if (array[left] > array[j]) {
                  swap(array, left, j);
              }
              if (right  array[j]) {
                  swap(array, right, j);
              }
          }
          len--;
          // 将堆顶元素和放到正确的地方
          swap(array, 0, array.length - 1 - i);
      }
  }
  
  /**
   * 交换数组中的两个元素
   * @param array 数组
   * @param i1 元素1
   * @param i2 元素2
   */
  private void swap(int[] array, int i1, int i2) {
      int temp =  array[i1];
      array[i1] = array[i2];
      array[i2] = temp;
  }
  

7. 计数排序

• 平均时间复杂度 O(n+k) ，空间复杂度 O(k)，稳定。其中，k是整数的范围

• 基本思想

  • 遍历数组，得出最大值、最小值、差距三者中的两个。
  • 申请一个新数组，数组长度为差距。然后对原数组中的数进行遍历，记录出现的次数
  • 最后遍历新数组，就可以得到排序后的结果

• 演示

  

• 代码

  /**
   * 计数排序
   * @param array 待排序的数组
   */
  public void countingSort(int[] array) {
      int min = array[0];
      int max = array[0];
      // 找最大值和最小值
      for (int i : array) {
          min = Math.min(i, min);
          max = Math.max(i, max);
      }
  
      // 申请额外的空间，大小为最值之间的范围
      int[] temp = new int[max - min + 1];
  
      // 填充新数组
      for (int i : array) {
          temp[i - min]++;
      }
  
      // 遍历新数组，然后填充原数组
      int index = 0;
      for (int i = 0; i 

• 注意：计数排序对于一定范围内的整数进行排序具有最高的效率，前提是整数的范围不要太大

8. 桶排序

• 平均时间复杂度 O(n) ，空间复杂度 O(n+k)，稳定。其中k是桶的数量

• 基本思想

  • 首先划分若干个范围相同的 “桶” ，
  • 然后将待排序的数据扔到属于他自己的桶中
  • 对桶中的数据进行排序
  • 依次输出所有桶中的数据

• 关键

  • 计数排序的优化，适合于对于大量有范围的数据
  • 桶的划分要尽量保证元素应当可以均匀分散到所有桶中，如果说所有元素都集中在一个桶中，那么桶排序就会失效

• 演示

  

• 代码

  • 桶排序的关键在于桶的划分和选取。需要根据实际使用场景按需进行设计，所以这里不做展示。

4.2 快速选择

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

• 思路

  • 快速选择算法是快速排序的一个变形
  • 从上文对于快速排序的讲解中不难发现。对于一个 key 来说，在进行一次快速排序的过程中，是可以确定出这个 key 所在有序数组中的位置。
  • 那么我们只需要关注这个位置是不是我们需要的 K 即可。如果比 k 大，则在 key 的右边再做一次快速排序即可；反之，则在左边做一次快速排序

• 时间复杂度 O(n)，空间复杂度 O(1)

• 代码

  public int findKthLargest(int[] nums, int k) {
      int left = 0;
      int right = nums.length - 1;
      int target = nums.length - k;
      while (left  target) {
              right = p - 1;
          } else {
              return nums[p];
          }
      }
      return nums[left];
  }
  
  // 快速排序函数，返回key的下标
  public int quickSort(int[] array, int left, int right) {
      int i = left;
      int j = right;
      int key = array[left];
      while (i = key) {
              j--;
          }
          if (i 

• 注意点

  • 当 k=1 时，函数可能不会在循环体中返回结果。此时，退出循环后left=5 ，所以要返回 nums[left]

4.3 桶排序

347. 前 K 个高频元素（Medium）

• 思路

  • 典型的桶排序的使用场景，来回顾一下桶排序
    • 桶排序就是把需要排序的元素放到属于他的桶中，然后再对桶中的元素进行排序，最后把所用桶中的元素输出就是排序之后的结果。重点是让所有元素均匀的分布到所有桶中
  • 如果我们的桶中只放这个元素自己，那么桶的大小就是这个元素的出现次数，然后根据桶的大小进行排序，就可以很方便的得到出现频率前K个高频元素
  • 重点：将元素和出现频率进行对应
  • 时间 O(n log(n))， 空间 O(n)

• 代码

  public int[] topKFrequent(int[] nums, int k) {
      int[] res = new int[k];
      // 用哈希表做桶排序，每个元素作为key，出现次数作为value
      Map map = new HashMap();
      for (int num : nums) {
          map.put(num, map.getOrDefault(num, 0)+1);
      }
      int[][] bucket = new int[map.size()][2];
      int p = 0;
      // 利用数组将元素和出现次数进行对应
      for (Integer i : map.keySet()) {
          bucket[p][0] = i;
          bucket[p++][1] = map.get(i);
      }
      // 降序排序
      Arrays.sort(bucket, ((o1, o2) -> o2[1]-o1[1]));
      for (int i = 0; i 

• 优化

  • 在得到每个元素的频率之后，可以再对频率进行一次桶排序，这样的话可以把时间复杂度降低到 O(n)

• 代码

  // 再对频率进行一次桶排序，这样就可以得到前K个高频的元素
  // 对于频率最高的元素，放在最前面
  List[] bucket = new List[maxFrequency + 1];
  for (int i : map.keySet()) {
      int f = maxFrequency - map.get(i);
      if (bucket[f] == null) {
          bucket[f] = new ArrayList();
      }
      bucket[f].add(i);
  }
  List res = new ArrayList();
  int i = 0;
  while (k > 0) {
      List list = bucket[i++];
      if (list != null) {
          res.addAll(list);
          k -= list.size();
      }
  }
  

4.4 基础练习

451. 根据字符出现频率排序（Medium）

• 思路

  • 桶排序，每个字母一个桶，最后降序输出

• 代码

  public String frequencySort(String s) {
      Map map = new HashMap();
      // 对字母进行桶排序，得到每个字母出现的频率
      int max = 0;
      for (int i = 0; i [] bucket = new ArrayList[max + 1];
      for (char c : map.keySet()) {
          int f = map.get(c);
          if (bucket[f] == null) {
              bucket[f] = new ArrayList();
          }
          bucket[f].add(c);
      }
      int p = 0;
      char[] chars = s.toCharArray();
      for (int i = max; i >= 0; i--) {
          if (bucket[i] != null) {
              for (char c : bucket[i]) {
                  Arrays.fill(chars, p, p+i, c);
                  p += i;
              }
          }
      }
      return new String(chars);
  }
  

4.5 进阶练习

75. 颜色分类（Medium）

• 思路

  • 遍历数组，对三种颜色出现的次数进行统计，然后填充数组

• 代码

  public void sortColors(int[] nums) {
      int[] f = new int[3];
      for (int num : nums) {
          f[num]++;
      }
      int p = 0;
      for (int i = 0; i 

LeetCode刷题-04-排序

标签：ast   run   upload   https   array   ons   交换   长度   vat   

原文地址：https://www.cnblogs.com/primabrucexu/p/14061405.html