算法学习

排序

算法学习 📒 repo

快速排序

http://www.conardli.top/docs/algorithm/%E6%8E%92%E5%BA%8F/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.html#%E6%80%9D%E6%83%B3

这个方法比较简单也很好理解

方法一

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];
// 自定义个数
let ageLists = []
for(let i = 0; i <=100; i++) {
    let id = Math.floor(Math.random() * 100 + 1)
    ageLists.push({
        id: id,
        age: Math.floor(Math.random() * 40 + 1),
        name: `学号${i}`,
        type: 'student'
    })
}

console.log(ageLists)

// 排数组
function quickSort(array) {
    if (array.length <= 1) {
        return array
    }

    let target = array[0]
    let left = []
    let right = []

    for (let i = 1; i < array.length; i++) {
        if (array[i] < target) {
            left.push(array[i])
        } else {
            right.push(array[i])
        }
    }

    return quickSort(left).concat([target], quickSort(right))
}

console.log(quickSort(list))

// 排对象
function quickSortObj(array, key) {
    if (array.length <= 1) {
        return array
    }

    let target = array[0]
    let left = []
    let right = []

    for (let i = 1; i < array.length; i++) {
        if (array[i][key] < target[key]) {
            left.push(array[i])
        } else {
            right.push(array[i])
        }
    }

    return quickSortObj(left, key).concat([target], quickSortObj(right, key))
}

console.time('quickSortObj')
console.log(quickSortObj(ageLists, 'id'))
console.timeEnd('quickSortObj')

方法二

// 排序数组
function quickSort(array, start, end) {
    if (end - start < 1) return

    let target = array[start]
    let l = start
    let r = end

    while (l < r) {
        while (l < r && array[r] >= target) {
            r--
        }
        array[l] = array[r]
        while (l < r && array[l] < target) {
            l++
        }
        array[r] = array[l]
    }

    array[l] = target

    quickSort22(array, start, l - 1)
    quickSort22(array, l + 1, end)
    return array
}

console.time('quickSort')
console.log(quickSort(list, 0, list.length - 1))
console.timeEnd('quickSort')

// 拍对象
function quickSort2Obj(array, start, end, key) {
    if (end - start < 1) return

    let target = array[start]
    let l = start
    let r = end

    while(l < r) {
        while(l < r && array[r][key] >= target[key]) {
            r--
        }
        array[l] = array[r]

        while(l < r && array[l][key] < target[key]) [
            l++
        ]
        array[r] = array[l]
    }

    array[l] = target

    quickSort2Obj(array, start, l - 1, key)
    quickSort2Obj(array, l + 1, end, key)

    return array
}

console.time('quickSort2Obj')
console.log(quickSort2Obj(ageLists, 0, ageLists.length - 1, 'id'))
console.timeEnd('quickSort2Obj')

这个对比方法一难点, 一下不容易理解

经过测试 少量的数据 方法二有时候比方法一要慢(10 - 100), 但是数据足够大的时候 方法二比方法一就要快很多(10000左右)

归并排序

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function mergeSort(array) {
  if (array.length < 2) {
    return array
  }

  let mid = Math.floor(array.length / 2)
  let front = array.slice(0, mid)
  let end = array.slice(mid)

  return merge(mergeSort(front), mergeSort(end))
}

function merge(front, end) {
  let temp = []

  while (front.length && end.length) {
    if (front[0] < end[0] ){
      temp.push(front.shift())
    } else {
      temp.push(end.shift())
    }
  }

  while(front.length) {
    temp.push(front.shift())
  }
  while(end.length) {
    temp.push(end.shift())
  }
  return temp
}

console.time()
console.log(mergeSort(list))
console.timeEnd()

选择排序

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j
      }
    }
    [array[minIndex], array[i]] = [array[i], array[minIndex]]
  }
  return array
}

console.time()
console.log(selectionSort(list))
console.timeEnd()

插入排序

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];


function insertSort(array) {
  for (let i = 1; i < array.length; i++) {
    let target = i
    for (let j = i - 1; j >= 0; j--) {
      if (array[target] < array[j]) {
        [array[target], array[j]] = [array[j], array[target]]
        target = j
      } else {
        break
      }
    }
  }
  return array
}


console.time()
console.log(insertSort(list))
console.timeEnd()

冒泡排序

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    let complate = true
    for (let j = 0; j < array.length - 1 - i; j++) {
      console.log(1, array.length - 1 - i)
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]]
        complate = false
      }
    }
    if (complate) {
      break
    }
  }
  return array
}

console.time()
console.log(bubbleSort(list))
console.timeEnd()

堆排序

let list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];

function heapSort(array) {
  createHeap(array)
  console.log('array', array)
  // 交换第一个和最后一个元素，然后重新调整大顶堆
  for (let i = array.length - 1; i > 0; i--) {
    [array[i], array[0]] = [array[0], array[i]]
    adJust(array, 0, i)
  }
  return array
}

// 构建大顶堆，从第一个非叶子节点开始，进行下沉操作
function createHeap(array) {
  const len = array.length
  const start = parseInt(len / 2) - 1
  for (let i = start; i >= 0; i--) {
    adJust(array, i, len)
  }
}
// 将第target个元素进行下沉，孩子节点有比他大的就下沉
function adJust(array, target, len) {
  for (let i = 2 * target + 1; i < len; i= 2 * i + 1) {
    // 找到孩子节点中最大的
    if (i + 1 < len && array[i + 1] > array[i]) {
      i = i + 1
    }
    // 下沉
    if (array[i] > array[target]) {
      [array[i] ,array[target]] = [array[target], array[i]]
      target = i
    } else {
      break
    }
  }
}

console.time()
console.log(heapSort(list))
console.timeEnd()