递归的三大要素

第一要素：明确你这个函数想要干什么
第二要素：寻找递归结束条件
第三要素：找出函数的等价关系式

快排基本思想

  1. 选定Pivot中心轴
  2. 将大于Pivot的数字放在Pivot的右边
  3. 将小于Pivot的数字放在Pivot的左边
  4. 分别对左右子序列重复前三步操作
    1. 左递归
    2. 右递归

选取中轴 pivot（这里取首元素）， left 指向第一个元素下标， right 指向最后一个元素下标，
如果 arr[right] >= pivot ，则 right—
如果 arr[right] < pivot ，则 arr[left] = arr[right] ，left++

如果 arr[left] <= pivot ，则 left++
如果 arr[left] > pivot ，则 arr[right] = arr[left] ， right—

Go代码

  1. // 快速排序
  3. package main
  5. import (
  6.     "fmt"
  7. )
  9. func quickSort(left int, right int, arr *[8]int) {
  11.     // 保留 左右下标值，不参与运算, 只用来传递参数，定义运算边界，划分子问题
  12.     L := left // 值拷贝
  13.     R := right
  15.     // 递归结束条件
  16.     if left >= right {
  17.         return
  18.     }
  20.     // 中轴
  21.     pivot := arr[left]
  23.     // 从小到大排
  24.     for left < right {
  25.         for left < right && arr[right] >= pivot {
  26.             right--
  27.         }
  28.         if left < right {
  29.             arr[left] = arr[right] // 移动值
  30.         }
  32.         for left < right && arr[left] <= pivot {
  33.             left++
  34.         }
  35.         if left < right {
  36.             arr[right] = arr[left]
  37.         }
  39.         if left >= right {
  40.             arr[left] = pivot
  41.         }
  42.     }
  43.     fmt.Println(left, right, arr)
  45.     // 划分子问题
  46.     // 左递归
  47.     quickSort(L, right-1, arr)
  48.     // 右递归
  49.     quickSort(right+1, R, arr)
  50. }
  52. func main() {
  53.     // arr := [6]int{-9, 78, 0, 23, -567, 70}
  54.     arr := [8]int{5, 8, 1, 3, 6, 2, 4, 7}
  55.     fmt.Println("arr = ", arr)
  56.     quickSort(0, len(arr)-1, &arr)
  57.     fmt.Println("arr = ", arr)
  58. }
  60. /*
  61. arr =  [5 8 1 3 6 2 4 7]
  62. 4 4 &[4 2 1 3 5 6 8 7]
  63. 3 3 &[3 2 1 4 5 6 8 7]
  64. 2 2 &[1 2 3 4 5 6 8 7]
  65. 0 0 &[1 2 3 4 5 6 8 7]
  66. 5 5 &[1 2 3 4 5 6 8 7]
  67. 7 7 &[1 2 3 4 5 6 7 8]
  68. arr =  [1 2 3 4 5 6 7 8]
  69. */

JS代码

var arr = [5, 1, 42, 10, 28]

// 冒泡排序
function bubbleSort(arr) {
  var temp = 0
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
}
// bubbleSort(arr)
console.log(arr);

// 快速排序
function Quicksort(left, right, arr) {
  var L = left
  var R = right
  if (left >= right) {
    return
  }
  // 选定中轴
  var pivot = arr[left]
  while (left < right) {
    while (left < right && arr[right] > pivot)
      right--
    if (left < right) {
      arr[left] = arr[right]
    }
    while (left < right && arr[left] <= pivot)
      left++
    if (left < right) {
      arr[right] = arr[left]
    }
    if (left >= right) {
      arr[left] = pivot
    }
  }
  // 左递归
  Quicksort(L, right - 1, arr)
  // 右递归
  Quicksort(right + 1, R, arr)

}

Quicksort(0, arr.length - 1, arr)
console.log(arr);