| 排序算法 | 时间复杂度 | 是否基于比较 |
| 冒泡排序、插入排序、选择排序 | O(n2) | 是 |
| 快速排序，归并排序 | O(nlogn) | 是 |
| 桶排序、计数排序、基数排序 | O(n) | 否 |
在排序过程中，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
我通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
排序算法的分析方法：
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
实现步骤：
function quickSort(arr, left, right) { var len = arr.length, partitionIndex, left = typeof left != ‘number‘ ? 0 : left, right = typeof right != ‘number‘ ? len - 1 : right; if (left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } function partition(arr, left, right) { // 分区操作 var pivot = left, // 设定基准值（pivot） index = pivot + 1; for (var i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function partition2(arr, low, high) { let pivot = arr[low]; while (low < high) { while (low < high && arr[high] > pivot) { --high; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { ++low; } arr[high] = arr[low]; } arr[low] = pivot; return low; } function quickSort2(arr, low, high) { if (low < high) { let pivot = partition2(arr, low, high); quickSort2(arr, low, pivot - 1); quickSort2(arr, pivot + 1, high); } return arr; } let sortArr = [3, 2, 5, 6, 3, 4, 1, 8]; console.log(quickSort(sortArr));
原文：https://www.cnblogs.com/yuyujuan/p/14059872.html