[排序]

[Linjiayu6]

1 - 快速排序

// 最好的情况是O(N)，最差的时候是O(N^2)，所以平时说的O(N*logN)为其平均时间复杂度
var arr = [4, 3, 1, 5, 10, 2, 7]
function quickSort (arr) {
  if (arr.length <= 1) return arr
  var left = [], right = [], mid = []

  var pivot_index = Math.floor(arr.length / 2)
  var pivot = arr[pivot_index]

  // 小于放到left, 等于放到mid, 大于放到right
  for (data of arr) {
    if (data < pivot) { left.push(data) }
    else if (data > pivot) { right.push(data) }
    else { mid.push(pivot) }
  }

  return quickSort(left).concat(mid).concat(quickSort(right))
}

quickSort(arr)

[Linjiayu6]

2 - 384. 打乱数组

- 拷贝数组 arr.slice()
- 随机位置 Math.floor(Math.random() * (i + 1))

/**
 * @param {number[]} nums
 */
var Solution = function(nums) {
  this.origin = nums
};

/**
 * Resets the array to its original configuration and return it.
 * @return {number[]}
 */
Solution.prototype.reset = function() {
  return this.origin
};

/**
 * Returns a random shuffling of the array.
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
  var arr = this.origin.slice() // copy一个数组
  for (let i = 0; i < arr.length; i++) {
    var pos = Math.floor(Math.random() * (i + 1)) // 在之前位置的交换
    var temp = arr[i]
    arr[i] = arr[pos]
    arr[pos] = temp
  }
  return arr
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.reset()
 * var param_2 = obj.shuffle()
 */

[Linjiayu6]

3 - 希尔排序
sisterAn/JavaScript-Algorithms#75

[Linjiayu6]

4 - 148. 排序链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  if (!head || !head.next) return head
  var list = []
  while (head) {
    list.push(head.val)
    head = head.next
  }

  list.sort((a, b) => a - b)
  var root = new ListNode(list[0])
  var _root = root
  for (let i = 1; i < list.length; i++) {
    _root.next = new ListNode(list[i])
    _root = _root.next
  }

  return root
};

[Linjiayu6]

5 - 归并排序

• 将其分割 一半半的分割
• 将有序数组合并在一起

// left, right 都是部分有序
function sort (left = [], right = []) {
  var i = 0, j = 0
  var result = []
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }
  let temp = []
  if (i < left.length) temp = left.slice(i)
  if (j < right.length) temp = right.slice(j)
  return result.concat(temp)
}

function mergeSort(arr) {
  if (arr.length < 2) return arr
  var mid = arr.length >> 1
  return sort(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
mergeSort([7, 6, 5, 4, 3, 2, 1])