数组去重和排序

数组去重

Set 去重

function unique(arr) {
  return Array.from(new Set(arr))
}
// OR
function unique(arr) {
  return [...new Set(arr)]
}

双重循环

function unique(arr) {
  let result = []
  for (let i = 0; i < arr.length; i++) {
    let isHas = false
    for (let j = 0; j < result.length; j++) {
      if (arr[i] === result[j]) {
        isHas = true
        break
      }
    }
    if (!isHas) result.push(arr[i])
  }
  return result
}

// OR
function unique(arr) {
  let result = []
  for (let i = 0; i < arr.length; i++) {
    if (result.indexOf(arr[i]) === -1) result.push(arr[i])
  }
  return result
}

// OR
function unique(arr) {
  let result = []
  for (let i = 0; i < arr.length; i++) {
    if (!result.includes(arr[i])) result.push(arr[i])
  }
  return result
}

// OR
function unique(arr) {
  let result = []
  arr.forEach((element) => {
    // if (!result.includes(element)) result.push(element)
    // OR
    if (result.indexOf(element) === -1) result.push(element)
  })
  return result
}

reduce 去重

function unique(arr) {
  return arr.reduce((result, element, index) => {
    // if (!result.includes(item)) result.push(element)
    // OR
    if (result.indexOf(element) === -1) result.push(element)
    return result
  }, [])
}

sort 去重

function unique(arr) {
  arr.sort((a, b) => a - b)
  if (arr.length === 1) return arr
  let result = [arr[0]]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      result.push(arr[i])
    }
  }
  return result
}

排序

冒泡排序

function BubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1)
    }
  }
}

function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

冒泡排序优化

function BubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let isSwap = false
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        isSwap = true
        swap(arr, j, j + 1)
      }
    }
    if (!isSwap) break // 如果没有再交换元素了，表明已经有序，不需要继续遍历
  }
}

function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

插入排序

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

快速排序

function fastSort(arr) {
  function sort(arr, left, right) {
    if (left >= right) return
    let index = findIndex(arr, left, right)
    sort(arr, left, index)
    sort(arr, index + 1, right)
  }
  function findIndex(arr, left, right) {
    if (left > right) return
    let key = arr[left]
    let low = left
    while (left < right) {
      while (key < arr[right] && left < right) {
        right--
      }
      while (arr[left] <= left && left < right) {
        left++
      }
      if (left < right) {
        swap(arr, left, right)
      }
    }
    swap(arr, low, right)
    return left
  }
  sort(arr, 0, arr.length - 1)
}
function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

归并排序

function mergeSort(arr) {
  let len = arr.length
  if (len <= 1) {
    return arr
  }
  let mid = parseInt(len / 2)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
  let arr = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      arr.push(left.shift())
    } else {
      arr.push(right.shift())
    }
  }
  while (left.length) {
    arr.push(left.shift())
  }
  while (right.length) {
    arr.push(right.shift())
  }
  return arr
}

堆排序

• 构建堆
• 交换第一个和最后一个的位置，并重新构建堆

1. 大顶堆

升序

// 堆排序
function HeapSort(arr) {
  for (let i = arr.length / 2; i >= 0; i--) {
    // 构建堆
    buildHeap(arr, i, arr.length)
  }
  // 开始排序
  for (let i = arr.length - 1; i > 0; i--) {
    //交换第一个和最后一个的位置
    swap(arr, 0, i)
    // 交换位置之后重新构建堆
    buildHeap(arr, 0, i)
  }
}
// 构建堆 - 大顶堆
function buildHeap(arr, i, len) {
  let parent = arr[i]
  let child = 2 * i + 1
  while (child < len) {
    if (child + 1 < len && arr[child + 1] > arr[child]) child = child + 1
    if (arr[child] <= parent) break
    arr[i] = arr[child]
    i = child
    child = 2 * i + 1
  }
  arr[i] = parent
}

function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

1. 小顶堆

降序

// 堆排序
function HeapSort(arr) {
  for (let i = arr.length / 2; i >= 0; i--) {
    // 构建堆
    buildHeap(arr, i, arr.length)
  }
  // 开始排序
  for (let i = arr.length - 1; i > 0; i--) {
    //交换第一个和最后一个的位置
    swap(arr, 0, i)
    // 交换位置之后重新构建堆
    buildHeap(arr, 0, i)
  }
}
// 构建堆 - 小顶堆
function buildHeap(arr, i, len) {
  let parent = arr[i]
  let child = 2 * i + 1
  while (child < len) {
    if (child + 1 < len && arr[child + 1] < arr[child]) child = child + 1
    if (arr[child] >= parent) break
    arr[i] = arr[child]
    i = child
    child = 2 * i + 1
  }
  arr[i] = parent
}

function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}