JIA's blog

1.冒泡排序

原理：比较相邻两个数的大小，将较大（或小）的数换到右边（或左边），这样就能将最大（或最小）的数一个一个的比较出来，放到一端。循环这个过程，将所有的数字的顺序排列出来。
数组长度为n，总共要进行n-1趟，每第i趟的排序次数为n-i-1次
时间复杂度：O(n^2)；空间复杂度O(1)

function bubbleSort(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]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        } 
    }
    return arr
}

2.选择排序

原理：先找出数组中最大（或最小）的值，放到一头，然后重复这个过程
时间复杂度：O(n^2)

function selectSort(arr){
    for(var i = 0; i< arr.length-1; i++){//循环次数
        for(var j = i+1; j < arr.length; j++){
            if(arr[i] > arr[j]){
                var tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp
            }
        }
    }
    return arr
}

3.插入排序

原理：构建有序序列，对于未排序数据，在已排序的序列中从后向前扫描，找到相应的位置并插入。
默认该有序数列的第一个值是数组的第一个元素，i从1开始取，arr[i]和 arr[0]到arr[i] 之间的数进行比较，找到自己的位置

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

4.希尔排序

原理：简单插入排序的改进版。与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

5.归并排序

原理：归并排序是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，成为2-路归并。

6.快速排序

原理：设置一个基准数，将基准数交换到数组的末尾，遍历数组，将小于基准数的换到左边，大于基准数的换到右边，然后将基准数换到他们中间，这成为分区。快排就是不断分区的过程，完成第一个分区后，再对左右两边分成的数组进行分区，一直重复到排序完成。

function quickSort(arr){
    var len = arr.length;
    if(len<=1){
        return arr
    }
    var pivotIndex = Math.floor(len/2);
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [], right = [];
    for(var i = 0; i < len; i++){
        if(arr[i] < pivot){
            left.push(arr[i] )
        }else{
            right.push(arr[i] )
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}