共计 3924 个字符，预计需要花费 10 分钟才能阅读完成。
阮一峰排序算法
1. 冒泡排序
一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越来越小的元素会经由交换慢慢“浮”到数列的顶端。
描述：
- 比较相邻的元素，如果第一个比第二个大，就交换他们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾最后一对，这样在最后的元素应该会是最大的数；
- 针对所有元素重复以上步骤，除了最后一个；
- 重复以上步骤，直到排序完成。
代码实现：
function bubbleSort(arr) {
var len = arr.length; for(var i = 0; i < len - 1; i ++) {for(var j = 0; j < len - 1; j ++) {if(arr[j] > arr[j + 1]) {var temp = arr[j + 1]; arr[j+1] = arr[j]; arr[j] = temp; } } } return arr;}
function bubbleSort(arr) {
var len = arr.length; var i; var j; var stop; for(i = 0; i < len - 1; i ++) {for(j = 0, stop = len - 1 - i; j < stop; j ++) {if(arr[j] > arr[j + 1]) {swap(arr, j, j+1); } } } return arr;}
function swap(arr, p1, p2) {arr[p1] = arr[p1] + arr[p2]; arr[p2] = arr[p1] - arr[p2]; arr[p1] = arr[p1] - arr[p2];}
时间复杂度：O(n^2)（平均），O(N)（最好），O(n^2)（最坏），
空间复杂度：O(1)
稳定性：稳定
2. 选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩下未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述：
- 初始状态：无序区为 R[1..n]，有序区为空
- 第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R[1..i-1]和 R[i..n]。该趟排序从当前无序区中选出关键字最小的记录 R[k], 将它与无序区的第一个记录 R 交换，使 R[1..i]和 R[i+1..n]分别变为记录个数增加 1 个的有序新区和记录个数少一个的新无序区了
- n- 1 趟结束，数组有序化了
代码实现：
function seletionSort(arr) {
var len = arr.length; var minIndex, temp; for(var i = 0; i < len - 1; i ++) { minIndex = i; for(var j = i + 1; j < len; j ++) {if(arr[j] < arr[minIndex]) {minIndex = j;} } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}
算法分析：
- 表现最稳定的排序算法，因为无论什么数据进去都是 O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占额外的内存空间了吧。
- 稳定性：不稳定
3. 插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述：
- 从第一个元素开始，该元素可以认为已经排好序；
- 取出下一个元素，在已经排好序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复上一步骤，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复 2 - 5 步。
代码实现：
function insertionSort(arr) {
var len = arr.length; var preIndex, current; for(var i = 1; i < len; i ++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex]; preIndex --; } arr[preIndex + 1] = current; } return arr;}
时间复杂度：O(n^2)（平均），O(n^2)（最坏），O(n)（最好）
4. 希尔排序
简单插入排序的改进版。与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述：
- 选择一个增量序列 t1,t2,…,tk, 其中 ti>tj,tk=1;
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，对待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现：
function sort(arr) {
for(int gap = arr.length / 2; gap > 0; gap /= 2) {for(int i = gap; i < arr.length; i++) { int j = i; while(j - gap >= 0 && arr[j] < arr[j - gap]) {swap(arr, j, j - gap); j -= gap; } } }}
function swap(arr, a, b) {arr[a] = arr[a] + arr[b]; arr[b] = arr[a] - arr[b]; arr[a] = arr[a] - arr[b];}
时间复杂度：O(n^1.3)（平均）、O(n^2)（最坏）、O(n)（最好）
5. 归并排序
归并排序是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，成为 2 - 路归并。
算法描述：
- 把长度为 n 的输入序列分成两个长度为 n / 2 的子序列
- 对这两个子序列分别采用归并排序
- 将两个排好序的子序列合并成一个最终的排序序列
代码实现：
function mergeSort(arr) {
var len = arr.length; if(len < 2) {return arr;} var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));}
function merge(left, right) {
var result = []; while(left.length>0 && right.length>0) {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;}
时间复杂度：O(nlog2n)（平均）、O(nlog2n)（最坏）、O(nlog2n)（最好）
6. 快速排序
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述：
- 从数列中挑出一个元素，称为“基准”
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作
- 递归地把小于基准值元素的子数列和大于基准值元素的子序列排序
代码实现一：
function quickSort(arr) {
if(arr.length <= 1) {return arr;} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = [], right = []; for(var i = 0; i < arr.length; i ++) {if(arr[i] < pivot) {left.push(arr[i]); } else {right.push(arr[i]); } } return quickSort(left).concat([pivot],quickSort(right));}
代码实现二：
function swap(arr, a1, a2) {
var temp = arr[a1]; arr[a1] = arr[a2]; arr[a2] = temp;}
function partition(arr, left, right) {var pivot = arr[Math.floor((right + left) / 2)], i = left, j = right; while(i <= j) {while(arr[i] < pivot) {i ++;} while(arr[j] > pivot) {j --;} if(i <= j) {swap(arr, i ,j); i ++; j --; } } return i;}
function quickSort(arr, left, right) {if(arr.length < 2) {return arr;} left = (tyepof left !== "number" ? 0 : left); right = (typeof right !== 'number' ? arr.length - 1 : right); var index = partition(arr, left, right); if(left <index - 1) {quickSort(arr, left, index - 1); } if(index <right) {quickSort(arr, index, right); } return arr;}