快速排序

🏠 首页 / 数据结构与算法 / 快速排序

快速排序 #

步骤如下:

  1. 先从数列中取出一个数作为基准数。一般取第一个数。
  2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
  3. 再对左右区间重复第二步,直到各区间只有一个数。

举一个例子:5 9 1 6 8 14 6 49 25 4 6 3

一般取第一个数 5 作为基准,从它左边和最后一个数使用[]进行标志,
如果左边的数比基准数大,那么该数要往右边扔,也就是两个[]数交换,这样大于它的数就在右边了,然后右边[]数左移,否则左边[]数右移。
5 [9] 1 6 8 14 6 49 25 4 6 [3]  因为 9 > 5,两个[]交换位置后,右边[]左移
5 [3] 1 6 8 14 6 49 25 4 [6] 9  因为 3 !> 5,两个[]不需要交换,左边[]右移
5 3 [1] 6 8 14 6 49 25 4 [6] 9  因为 1 !> 5,两个[]不需要交换,左边[]右移
5 3 1 [6] 8 14 6 49 25 4 [6] 9  因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 [6] 8 14 6 49 25 [4] 6 9  因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 [4] 8 14 6 49 [25] 6 6 9  因为 4 !> 5,两个[]不需要交换,左边[]右移
5 3 1 4 [8] 14 6 49 [25] 6 6 9  因为 8 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [25] 14 6 [49] 8 6 6 9  因为 25 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [49] 14 [6] 25 8 6 6 9  因为 49 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [6] [14] 49 25 8 6 6 9  因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [14] 6 49 25 8 6 6 9  两个[]已经汇总,因为 14 > 5,所以 5 和[]之前的数 4 交换位置
第一轮切分结果:4 3 1 5 14 6 49 25 8 6 6 9  
现在第一轮快速排序已经将数列分成两个部分:
4 3 1 和 14 6 49 25 8 6 6 9
左边的数列都小于 5,右边的数列都大于 5。
使用递归分别对两个数列进行快速排序。
package main

import "fmt"

type BinaryTreeNode struct {
 Value       int
 Left, Right *BinaryTreeNode
}

func main() {
 nums := []int{4, 7, 2, 9, 3, 1}
 quickSort(nums, 0, len(nums)-1)
 fmt.Println(nums)
}

func quickSort(nums []int, r, l int) {
 if r < l {
  loc := quickSortHelper(nums, r, l)
  quickSort(nums, r, loc-1)
  quickSort(nums, loc+1, l)
 }
}

func quickSortHelper(nums []int, r, l int) int {
 i := r + 1
 j := l
 for i < j {
  if nums[i] > nums[r] {
   nums[i], nums[j] = nums[j], nums[i]
   j--
  } else {
   i++
  }
 }
 if nums[r] <= nums[i] {
  i--
 }
 nums[r], nums[i] = nums[i], nums[r]

 return i
}

« 堆排序