算法——常见算法

记录算法，三篇文章，持续更新，文章本意只是为了方便本人日后查看，如需转载请注明出处

• 算法——常见算法记录

• 算法——每日 N 题

• 算法——总结

正文

排序

快速排序

1. 时间复杂度
   • 最好O(nlogn)：每次都是中分
   • 最坏O(n^2)：全部都相等、或者已经排好序了
   • 平均O(nlogn)
2. 描述
   • 选取一个pivot，作为指标（排序后的中间值），然后左右各一个指针与pivot进行比较，一趟下来，最后的结果就是pivot左边的全部小于pivot，pivot右边的全部大于pivot
3. 注意点
   • pivot的选取与最先开始比较的指针是相对的（不然值会被覆盖）
     • 如果pivot选的是最左边的，则最先开始比较的是右指针
     • 如果pivot选的是最右边的，则最先开始比较的是左指针
   • 注意控制指针：left < right
   • 每一趟循环完了之后，记得把pivot保存的值赋值给left指针，不然会少值，多出来一个相同的值
4. java实现

public void quickSort(int[] arr, int left, int right) {
      if (left >= right) return;
      int mid = getMid(arr, left, right);
      quickSort(arr, left, mid - 1);
      quickSort(arr, mid + 1, right);
  }

  public int getMid(int[] arr, int left, int right) {
      int pivot = arr[left];            // 选取left为pivot
      while (left < right) {
          while (arr[right] > pivot && left < right) right--;    // 最先开始比较右指针
          arr[left] = arr[right];
          while (arr[left] < pivot && left < right) left++;
          arr[right] = arr[left];
      }
      arr[left] = pivot;      // 将pivot保存的值赋值给left
      return left;      // left已经将左右两边分出来了
  }