常见的排序方法大致可分为两类
比较类排序：通过比较来决定元素间的相对次序，由于时间复杂度不能突破，因此也称非线性时间比较类排序
非比较类排序：不能通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间
算法复杂度
一，冒泡排序
核心思想：
相邻两个元素比较，将较小的数字放到左侧，以此类推，这样最后那个元素就是最大的数
算法描述：
比较相邻的元素，如果第一个比第二个大，就交换它们两个，对每一对相邻元素作同样的工作，直到最后一对，这样最后面那个数就是最大的数，针对以上所有的元素重复作这个操作，除了最后一个，直到排序完成
代码实现：
function bubbleSort(arr) { varlen = arr.length; for(vari = 0; i < len - 1; i++) { for(varj = 0; j < len - 1 - i; j++) { if(arr[j] > arr[j+1]) { // 相邻元素两两对比 vartemp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } returnarr; }
二，选择排序
核心思想：
首先在未排序的序列中找到最小的那个元素，将它放到起始位置，再从剩余未排序的序列中找到最小的那个元素，放到已排序序列的末尾，以此类推，直到所有的元素都排序完成。
算法描述：
初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。
该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
代码实现：
function selectionSort(arr) { varlen = arr.length; varminIndex, temp; for(vari = 0; i < len - 1; i++) { minIndex = i; for(varj = i + 1; j < len; j++) { if(arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } returnarr; }
三：插入排序
核心思想：
通过构建有序序列，在已排序的序列中从后向前扫描，找到相应位置并插入
算法描述：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
代码实现：
function insertionSort(arr) { varlen = arr.length; varpreIndex, current; for(vari = 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; } returnarr; }
四，希尔排序
核心思想：
是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现：
function shellSort(arr) { varlen = arr.length; for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) { // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行 for(vari = gap; i < len; i++) { varj = i; varcurrent = arr[i]; while(j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } } returnarr; }
五，归并排序
核心思想：
该算法采用的是分冶法，将已有序的子序列合并，得到完全有序的序列，即先让每个子序列有序，再使子序列间有序，若将两个有序表合并成一个有序表，称2路归并
算法描述：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
代码实现：
function mergeSort(arr) { varlen = arr.length; if(len < 2) { returnarr; } varmiddle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); returnmerge(mergeSort(left), mergeSort(right)); } function merge(left, right) { varresult = []; 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()); returnresult; }
六，快速排序
核心思想：
先选择一个元素作为基准，通过一趟排序将待排元素分成两部分，一部分是大于基准的数，一部分是大于基准的数，然后分别对这两部分进行排序，以达到整个序列有序
算法描述：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现：
function quickSort(arr, left, right) { varlen = arr.length, partitionIndex, left =typeofleft !='number'? 0 : left, right =typeofright !='number'? len - 1 : right; if(left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex-1); quickSort(arr, partitionIndex+1, right); } returnarr; } function partition(arr, left ,right) { // 分区操作 varpivot = left, // 设定基准值（pivot） index = pivot + 1; for(vari = index; i <= right; i++) { if(arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); returnindex-1; } function swap(arr, i, j) { vartemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
七，堆排序
核心思想：
堆积是一个近似完全二叉树的结构，并同时满足堆积性质（子节点的键值或者索引总是小于（大于）它的父节点）
算法描述：
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码实现：
varlen; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr) { // 建立大顶堆 len = arr.length; for(vari = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); } } function heapify(arr, i) { // 堆调整 varleft = 2 * i + 1, right = 2 * i + 2, largest = i; if(left < len && arr[left] > arr[largest]) { largest = left; } if(right < len && arr[right] > arr[largest]) { largest = right; } if(largest != i) { swap(arr, i, largest); heapify(arr, largest); } } function swap(arr, i, j) { vartemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr) { buildMaxHeap(arr); for(vari = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } returnarr; }
