【数据结构与算法】(15)：快速排序

经典算法：给一个乱序的 number[] 数组，使用快速排序算法进行排序。

一、固定算法，固定思路

1. 找到中间位置 midValue
2. 遍历数组，小于 midValue 放在 left，否则放在 right
3. 继续递归。最后 concat 拼接，返回新数组

二、代码演示

1. 快速排序 （使用 splice）

type IArrNumber = number[]

// 快速排序 （使用 splice）
export function quickSort1(arr:IArrNumber): IArrNumber {
  const len = arr.length;
  if (len <= 1) return arr;

  const midIndex = Math.floor(len / 2)
  const midValue = arr.splice(midIndex, 1)[0]

  const left: IArrNumber = []
  const right: IArrNumber = []

  for (let i = 0; i < arr.length; i++) {
    const n = arr[i]

    if (n < midValue) {
      // 小于 midValue , 则放在 left
      left.push(n)
    } else {
      // 大于 midValue , 则放在 right
      right.push(n)
    }
  }

  return quickSort1(left).concat(
    [midValue],
    quickSort1(right)
  )
}

2. 快速排序 （使用 slice）

export function quickSort2(arr:IArrNumber): IArrNumber {
  const len = arr.length;
  if (len <= 1) return arr;

  const midIndex = Math.floor(len / 2)
  const midValue = arr.slice(midIndex, midIndex + 1)[0]

  const left: IArrNumber = []
  const right: IArrNumber = []

  for (let i = 0; i < len; i++) {
    if (i !== midIndex) {
      const n = arr[i]

      if (n < midValue) {
        // 小于 midValue , 则放在 left
        left.push(n)
      } else {
        // 大于 midValue , 则放在 right
        right.push(n)
      }
    }
  }

  return quickSort2(left).concat(
    [midValue],
    quickSort2(right)
  )
}

三、单元测试

import { quickSort1, quickSort2 } from './../quick-sort.ts'

describe('快速排序 splice', () => {
  it('正常情况', () => {
    const arr = [1, 8, 3, 9, 4, 35, 5, 6, 7,]
    let res = quickSort1(arr)
    expect(res).toEqual([1, 3, 4, 5, 6, 7, 8, 9, 35])
  })
  it('有负数', () => {
    let arr = [-1,1,-2,7]
    let res = quickSort1(arr)
    expect(res).toEqual([-2,-1,1,7])
  })
  it('数组元素都一样', () => {
    let arr = [2,2,2,2]
    let res = quickSort1(arr)
    expect(res).toEqual([2,2,2,2])
  })
  it('空数组', () => {
    let res = quickSort1([])
    expect(res).toEqual([])
  })
})


describe('快速排序 slice', () => {
  it('正常情况', () => {
    const arr = [1, 8, 3, 9, 4, 35, 5, 6, 7,]
    let res = quickSort2(arr)
    expect(res).toEqual([1, 3, 4, 5, 6, 7, 8, 9, 35])
  })
  it('有负数', () => {
    let arr = [-1,1,-2,7]
    let res = quickSort2(arr)
    expect(res).toEqual([-2,-1,1,7])
  })
  it('数组元素都一样', () => {
    let arr = [2,2,2,2]
    let res = quickSort2(arr)
    expect(res).toEqual([2,2,2,2])
  })
  it('空数组', () => {
    let res = quickSort2([])
    expect(res).toEqual([])
  })
})

四、算法复杂度

方法	时间复杂度
for + splice	O(n*logn)
for + slice	O(n*logn)

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-23
最后更新： 2023-07-24
本文标题： 【数据结构与算法】(15)：快速排序
本文链接： https://www.tiven.cn/p/69e45d4b/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！