# 快速排序

TIP

快速排序(Quick Sort)是冒泡排序的升级版,可以说是目前所有排序算法中,最快的一种排序算法。当然,没有任何一种算法是在任意情况下都是最优的。但是,大多数情况下快速排序是比较好的选择

# 算法描述

快速排序的核心思想是分而治之

  • 步骤 1:从数列中挑出一个元素,称为 “基准”、“枢纽” (pivot)
  • 步骤 2:重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作
  • 步骤 3:递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

# 静图演示

sort

# 动图演示

sort

# 选取枢纽

# 选取方案

  • 第一种方案:直接选择第一个元素作为枢纽。但是,当第一个元素就是最小值的情况下,效率不高
  • 第二种方案:使用随机数。随机数本身十分消耗性能,不推荐
  • 优秀的解决方法
    1. 取 index 为头、中、位的三个数据排序后的中位数
    2. 当(length-1)/2 不整除时可向下或向上取整

如下图所示,按下标值取出的三个数据为:92,43,0,经排序后变为:0,43,92,取其中的中位数 43 作为枢纽

sort

# 代码编写

// 交换两个位置的数据:用个临时变量中转一次
function swap(arr, m, n) {
	var tmp = arr[m]
	arr[m] = arr[n]
	arr[n] = tmp
}

// 选择枢纽
function median(arr, left, right) {
	// 1.求出中间的位置
	var center = Math.floor((left + right) / 2)

	// 2.判断大小并且进行交换
	if (arr[left] > arr[center]) {
		swap(arr, left, center)
	}
	if (arr[center] > arr[right]) {
		swap(arr, center, right)
	}
	if (arr[left] > arr[center]) {
		swap(arr, left, center)
	}

	// 3.巧妙的操作: 将center移动到right - 1的位置.
	swap(arr, center, right - 1)

	// 4.返回pivot
	return arr[right - 1]
}

# 代码测试

var arr = [3, 6, 4, 2, 11, 10, 5]
var pivot = median(arr, 0, 6)
console.log(pivot) // 3
console.log(arr) // [2, 6, 4, 10, 11, 3, 5]

# 快速排序

# 递归代码 1

// 快速排序
function quickSort(arr) {
	quick(arr, 0, arr.length - 1)
	return arr
}
// 递归函数
function quick(arr, left, right) {
	// 1. 递归结束条件
	if (left >= right) return

	// 2. 获取枢纽
	var pivot = median(arr, left, right)

	// 3. 定义变量,用于记录当前找到的位置
	var i = left
	var j = right - 1

	// 4. 开始进行交换
	while (true) {
		while (arr[++i] < pivot) {}
		while (arr[--j] > pivot) {}

		if (i < j) {
			swap(arr, i, j)
		} else {
			break
		}
	}

	// 5. 将枢纽放到正确的位置,i的位置
	swap(arr, i, right - 1)

	// 6. 分而治之
	quick(arr, left, i - 1)
	quick(arr, i + 1, right)
}

# 代码说明

  • 第一步:获取枢纽
  • 第二步:定义两个指针,从前和后两端分别开始往中间移动,不停地交换位置,将数组分成两组
  • 第三步:分别针对 左右两组进行递归 1~2 步

# 代码测试

// 测试快速排序
var arr = [3, 6, 4, 2, 11, 10, 5]
console.log(quickSort(arr).join("-"))
// 2-3-4-5-6-10-11

# 排序效率

  • 快速排序最坏情况下的效率:
    1. 每次选择的枢纽都是最左边或最右边的数据,此时效率等同于冒泡排序,时间复杂度为 O(N²)
    2. 一般会采取取中位数的方式来避免
  • 快速排序的平均效率:为 O(N*logN)
  • 虽然其他算法效率也可达到 O(N*logN),但是其中快速排序是最好的

# 完整代码

/* 快速排序 */

// 交换两个位置的数据:用个临时变量中转一次
function swap(arr, m, n) {
	var tmp = arr[m]
	arr[m] = arr[n]
	arr[n] = tmp
}

// 选择枢纽
function median(arr, left, right) {
	// 1.求出中间的位置
	var center = Math.floor((left + right) / 2)

	// 2.判断大小并且进行交换
	if (arr[left] > arr[center]) {
		swap(arr, left, center)
	}
	if (arr[center] > arr[right]) {
		swap(arr, center, right)
	}
	if (arr[left] > arr[center]) {
		swap(arr, left, center)
	}

	// 3.巧妙的操作: 将center移动到right - 1的位置.
	swap(arr, center, right - 1)

	// 4.返回pivot
	return arr[right - 1]
}

// 快速排序
function quickSort(arr) {
	quick(arr, 0, arr.length - 1)
	return arr
}
// 递归函数
function quick(arr, left, right) {
	// 1. 递归结束条件
	if (left >= right) return

	// 2. 获取枢纽
	var pivot = median(arr, left, right)

	// 3. 定义变量,用于记录当前找到的位置
	var i = left
	var j = right - 1

	// 4. 开始进行交换
	while (true) {
		while (arr[++i] < pivot) {}
		while (arr[--j] > pivot) {}

		if (i < j) {
			swap(arr, i, j)
		} else {
			break
		}
	}

	// 5. 将枢纽放到正确的位置,i的位置
	swap(arr, i, right - 1)

	// 6. 分而治之
	quick(arr, left, i - 1)
	quick(arr, i + 1, right)
}

// 测试中位数选取
var arr = [3, 6, 4, 2, 11, 10, 5]
var pivot = median(arr, 0, 6)
console.log(pivot) // 3
console.log(arr) // [2, 6, 4, 10, 11, 3, 5]

// 测试快速排序
var arr = [3, 6, 4, 2, 11, 10, 5]
console.log(quickSort(arr).join("-"))
// 2-3-4-5-6-10-11