冒泡排序:核心:冒泡,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。
function bubbleSort(arr) {
for(let i=arr.length;i>0;i--)
for(let j=0;j<i-1;j++){
let temp;
if(arr[j]>=arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
return arr;
}

选择排序:不断地选择剩余元素中的最小者。

  1. 找到数组中最小元素并将其和数组第一个元素交换位置。
  2. 在剩下的元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序
    function chooseSort(arr) {
     for(let i=0;i<arr.length-1;i++)
         for(let j=i+1;j<arr.length;j++){
             let temp;
             if(arr[i]>=arr[j]){
                 temp=arr[i];
                 arr[i]=arr[j];
                 arr[j]=temp;
             }
         }
     return arr;
    }

快速排序:快排是一种采用分治思想的排序算法,大致分为三个步骤。

  1. 定基准——首先随机选择一个元素最为基准
  2. 划分区——所有比基准小的元素置于基准左侧,比基准大的元素置于右侧
  3. 递归调用——递归地调用此切分过程
    function quickSort(arr){
     if(arr.length<2){
         return arr;
     }
     let left=[];
     let right=[];
     let point=arr[0];
     for(let i=0;i<arr.length;i++){
         if(arr[i]<point){
             left.push(arr[i]);
         }else{
             right.push(arr[i]);
         }
     }
     return quickSort(left).concat(point,quickSort(right));
    }

归并排序:将两个有序对数组归并成一个更大的有序数组。通常做法为递归排序,并将两个不同的有序数组归并到第三个数组中。
function merge(left,right) {
let res=[];
while(left.length>0&&right.length>0){
if(left[0]<=right[0]){
res.push(left.shift());
}else{
res.push(right.shift());
}
}
return res.concat(left).concat(right);
}
function mergeSort(arr) {
let len=arr.length;
if(len<2)
return arr;
let mid=Math.floor(len/2);
let left=arr.slice(0,mid);
let right=arr.slice(mid);
return merge(mergeSort(left),mergeSort(right));
}

插入排序:通过构建有序序列,对于未排序序列,在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历),找到相应位置并插入。
function insertSort(a) {
for(var i=0;i<a.length;i++){
var temp=a[i];
for(var j=i-1;j>=0&&a[j]>temp;j--){
a[j+1]=a[j];
}
a[j+1]=temp;
}
return a;
}

希尔排序:基于插入排序,使数组中任意间隔为h的元素都是有序的,即将全部元素分为h个区域使用插入排序。其实现可类似于插入排序但使用不同增量。
function shellSort(a) {
for(let grep=Math.floor(a.length/2);grep>0;grep=Math.floor(grep/2)){
// 内层循环与插入排序的写法基本一致,只是每次移动的步长变为 grep
for(let i=grep;i<a.length;i++){
let j;
let temp=a[i];
for(j=i-grep;j>=0&&temp<a[j];j-=grep){
a[j+grep]=a[j];
}
a[j+grep]=temp;
}
}
return a;
}