快速排序 (quickSort)

  • 快速排序是对冒泡排序的一种改进, 第一趟排序先分成两份, 然后递归调用,继续二分。
  • 快排属于分治法的一种,先把大问题分成各个小问题,再把小问题分成更小的问题。

简单算法实现

const quickSort = (arr) => {
	const len = arr.length
	if (len < 2) return arr
	else {
		let flag = arr[0]
		let left = []
		let right = []
		let temp
		for (let i of arr) {
			temp = arr[i]
			if (temp < flag) left.push(temp)
			else right.push(temp)
		}
		return quickSort(left).concat(flag, quickSort(right))
	}
}

高级算法实现 (in-place)

//交换函数
const swap = (arr, i, j) => {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
 }

//找到交换位置的函数
 const findIndex = (arr, left, right) => {
    const flag = arr[left]
    const index = flag + 1
    for(let i = index; i <= right; i ++) {
    if (arr[i] < flag) {
        swap(arr, flag, i)
        index ++
    }
    }
    swap(arr, left, index - 1)
    return index
 }

 const inPlace = (arr, left, right) => {
    if(left < right) {
        const index = findIndex(arr, left, right)
        inPlace(arr, left, index - 1)
        inPlace(arr, index, right)
    }
 }

inPlace(arr, 0, arr.length - 1)

A new frontend developer.