优略度解释

• 时间复杂度： 算法执行所耗费的时间
• 空间复杂度： 运行完一个程序所需内存大小
• 稳定： 如果a=b,a在b的前面，排序后a仍在b前面
• 不稳定： 如果a=b,a在b的前面，排序后a和b可能会交换位置
• 内排序： 所有排序操作都在内存中完成
• 外排序： 由于数据过大，要把数据放在磁盘中，排序通过磁盘和内存的数据传输才能进行

性能总结

|算法类型|平均时间复杂度|最优情况 |最坏情况 |空间复杂度|排序方式 |稳定性| |:—: |:—: |:—: |:—: |:—: |:—: |:—:| |冒泡 |O(n²) |O(n) |O(n²) |O(1) |In-place|稳定| |选择 |O(n²) |O(n²) |O(n²) |O(1) |In-place|不稳定| |插入 |O(n²) |O(n) |O(n²) |O(1) |In-place|稳定| |希尔 |O(n log n) |O(n log² n)|O(n log² n)|O(1) |In-place|不稳定| |归并 |O(n log n) |O(n log n) |O(n log n) |O(n) |Out-place|稳定| |快速 |O(n log n) |O(n log n) |O(n²) |O(log n) |In-place|不稳定| |堆 |O(n log n) |O(n log n) |O(n log n) |O(1) |In-place|不稳定| |计数 |O(n + k) |O(n + k) |O(n + k) |O(k) |Out-place|稳定| |桶 |O(n + k) |O(n + k) |O(n²) |O(n + k) |Out-place|稳定| |基数 |O(n * k) |O(n * k) |O(n * k) |O(n + k) |Out-place|稳定|

1. 冒泡排序

function sort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
  }
  return arr;
}

var arrBefore = [9, 4, 9, 3, 9, 4, 7, 7, 1];
console.log("arrBefore: " + arrBefore);  // "arrBefore: 9,4,9,3,9,4,7,7,1"
var arrAfter = sort(arrBefore);
console.log("arrAfter: " + arrAfter);  // "arrAfter: 1,3,4,4,7,7,9,9,9"

---

未完~