排序

冒泡排序

千条数据排序所用时间对比：

万条数据排序所用时间对比：

function randArray(len, min, max) {
  return Array.from({ length: len }, v => Math.floor(Math.random() * (max - min)) + min);
}
bubbleSort(randArray(10000, 1, 100000));
bubbleSort1(randArray(10000, 1, 100000));
// 普通版
function bubbleSort(arr) {
  var len = arr.length;
  console.time('冒泡排序');
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  console.timeEnd('冒泡排序');
  console.dir(arr);
  return arr;
}
// 优化版
function bubbleSort1(arr) {
  let low = 0;
  let hign = arr.length - 1;
  let j, tmp;
  console.time('冒泡排序1');
  while (low < hign) {
    for (j = low; j < hign; ++j) {
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    --hign;
    for (j = hign; j > low; --j) {
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    }
    ++low;
  }
  console.timeEnd('冒泡排序1');
  console.dir(arr);
  return arr;
}

合并排序

1. 把⻓度为n的输⼊序列分成两个⻓度为n/2的⼦序列
   2. 对两个⼦序列分别采⽤归并排序
   3. 将两个排序好的⼦序列合并成⼀个最终的排序序列。 ```javascript function mergeSort(arr) { const len = arr.length;

   if (len < 2) { return arr; }

   const middle = Math.floor(len / 2); const left = arr.slice(0, middle); const right = arr.slice(middle);

   return merge(mergeSort(left), mergeSort(right)); }

function merge(left, right) { let result = [];

while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } }

while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) }

return result; }

const list = [2, 34, 25, 33, 13, 6]; mergeSort(list);

<a name="Zf8o9"></a>
# 快速排序
> 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
```javascript
function quickSort(array) {
  // 替换数据
  function swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
  }
  // 分治函数
  function partition(array, left, right) {
    // ⽤index取中 值⽽⾮splice
    const pivot = array[Math.floor((right + left) / 2)]
    let i = left
    let j = right
    while (i <= j) {
      while (array[i] < pivot) {
        i++
      }
      while (array[j] > pivot) {
        j--
      }
      if (i <= j) {
        swap(array, i, j)
        i++
        j--
      }
    }
    return i
  }
  // 快排函数
  function quick(array, left, right) {
    let index
    if (array.length > 1) {
      index = partition(array, left, right)
      if (left < index - 1) {
        quick(array, left, index - 1)
      }
      if (index < right) {
        quick(array, index, right)
      }
    }
    return array
  }
  return quick(array, 0, array.length - 1)
}
quickSort([22, 3453, 4667, 25, 65, 87, 6897, 46, 567]);