1.冒泡排序

基本思想：重复遍历要排序的数组，每次比较相邻两个元素的大小，如果顺序错误，则交换两个元素的位置

步骤：

1. 比较相邻两个元素，如果位置不对交换两个元素
2. 对每一对相邻的元素重读步骤1，直到最后，把最大（小）元素冒泡的最后一个位置
3. 针对所有（除最后一个）元素，重复步骤1，2
4. 重复步骤1，2，3，直到排序完成

代码实现：

function bubbleSort (arr) {
	let len = arr.length;
	for(let i=0; i<len; i++) {
		for(let j=0; j<len-1-i;j++) {
			if(arr[j]>arr[j+1]) {
				[arr[j],arr[j+1]] = [arr[j+1], arr[j]];
			}
		}
	}
	return arr;
}

时间复杂度：O(n^2)

2.快速排序

快排，是对冒泡排序的一种优化。对于处理大数据来说，这是一种速度最快的算法。
基本思想：他是一种分而治之的算法，找出一个参考值，通过递归的方式将数据一次分解为包含较小元素和较大元素的不同子序列，重复这个步骤直到所有数据都是有序的
步骤：

1. 选择一个参考元素，将数组分割为两个子序列
2. 对序列重新排序，将所有小于基准的元素放在基准值的前面，大于基准值的元素放在基准值的右侧
3. 分别对小元素的子序列和较大元素的子序列重复步骤1，2

代码实现：

function quickSort (arr) {
	let len=arr.length,left=[],right=[],current = arr[0];
	if(len<=1) return arr;
	for(let i=1; i<len; i++){
		if(arr[i]<current) {
			left.push(arr[i]);
		} else {
			right.push(arr[i])
		}	
	}
	// 递归步骤1，2
	return quickSort(left).concat(current, quickSort(right))
}

时间复杂度：O(nlogn)

3.插入排序

基本思想：通过构建有序序列，对于未排序数据，在已排序的队列中从后向前扫描，找到相应的位置并插入。
步骤：

1. 从第一个元素开始，该元素被认为是已经排序
2. 取出下一个与元素，在已经排序的队列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将元素移到下一个位置
4. 重复步骤3，直到找到已排序元素中小于或等于新元素的位置
5. 将新元素插入到这个位置
6. 重复步骤2～5

代码实现：

/**双层循环，外循环控制未排序的元素，内循环控制已排序的元素，将未排序元素设为标杆，
与已排序的元素进行比较，小于则交换位置，大于则位置不动
*/
function insertSort(arr) {
    let tem
    for(let i=0; i<arr.length; i++) {
        tem = arr[i]
        for(let j=i; j>=0; j--){
            if(arr[j-1] > tem){
                arr[j] = arr[j-1]
            }else {
                arr[j] = tem
                break
            }
        }
    }
    return arr
}

时间复杂度：O(n^2)

4.选择排序

基本思想：首先在待排序的序列中选出最大值（或最小值），存放在排序序列的起始位置，然后再从剩余未排序的序列中继续选出最大值（或最小值），放在已排序的队列的末尾，以此类推，直到所有元素排序完成。
步骤：

1. 初始状态：无序区为[1,...,n], 有序区为空
2. 第i（i=1,2,3...n)趟排序时，当前有序区和无需区分别为[1, ...,i-1]和[i,...,n], 该趟排序从无序列表中选出最小（大）的元素，将它与无需区的第一个元素交换
3. n-1趟结束后，数组就是有序的了

代码实现：

/**
 * 先假设第一个元素为最小的，然后通过循环找出最小元素，
 * 然后同第一个元素交换，接着假设第二个元素，重复上述操作即可
 */
function selectSort(arr) {
    let len = arr.length, minIndex, tem
    for(let i=0; i<len-1; i++) {
        minIndex = i //最小值下标
        for(let j=i+1; j<len; j++) {
            if(arr[j] < arr[minIndex]){
                // 找出最小值
                minIndex = j //更换最小值下标
            }
        }
        // 交换位置
        tem = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = tem
    }
    return arr
}

时间复杂度：O(n^2);

5.归并排序

归并的含义是将两个或两个以上的有序序列合并成一个有序序列的过程。
基本思想：将若干有序序列逐步归并，最终归并为一个有序序列。
步骤：

1. 把长度为n的序列分成两个长度为n/2的子序列
2. 对这两个子序列分别采用归并排序
3. 将排好序的子序列合并成最终的有序序列

代码实现：

// 将数组一直等分，然后合并
function merge(left, right) {
    let tem = [];
    while(left.length && right.length) {
        if(left[0] < right[0]) {
            tem.push(left.shift());
        }else{
            tem.push(right.shift());
        }
    }
    return tem.concat(left,right);
}
function mergeSort(arr) {
    const len = arr.length;
    if(len<2) return arr;
    let mid = Math.floor(len / 2), left = arr.slice(0,mid), right = arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right));
}

时间复杂度：O(nlog(n))

6*.希尔排序

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序的一种更加高效的改进版本。
基本思想：把记录按的一定增量分组，对每组使用直接插入排序，随着增量的逐步减少，每组包含的元素越来越多，当增量减少到1时，整个序列被分成一组，排序完成。
步骤：

1. 选择一个增量序列t1,t2,t3…tk, 其中ti>tj,tk=1
2. 按增量序列个数k,对序列进行k趟排序
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

代码实现：

function shellSort(arr) {
    var len = arr.length;
    for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for(var i = gap; i < len;i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

时间复杂度：O(nlogn)