今天带来常见九大排序与基本算法JS篇。

下面一张图看9大排序...

由此可见

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序：所有排序操作都在内存中完成；

外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度： 一个算法执行所耗费的时间。 

空间复杂度：运行完一个程序所需内存的大小。

选择一个排序是由业务决定的。

源码：

var arr =  [3,4,2,6,7,8,2,14,57,8,99,0,45,32,12,1,1,1,1,45,0,9,8,7,6,5,4,3,2,115,67,68,56,55,43,21];

console.log('原始数组-----',arr);

//冒泡排序
//冒泡法：第一趟：相邻的两数相比，大的往下沉。最后一个元素是最大的。
//第二趟：相邻的两数相比，大的往下沉。最后一个元素不用比。
function sortMaopao(_arr,_type){
	var s,arr = _arr;
	for (let i = 0; i <arr.length; i++) {
		for(let j=0; j<arr.length; j++){
			if(arr[j] > arr[j+1] && _type == "asc"){
				s = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = s;
			}else if(arr[j] < arr[j+1] && _type == "desc"){
				s = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = s;
			}
		}
	}

	console.log('排序后数组-----',arr);
}

//插入排序
//列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
// 每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
function sortCharu(_arr,_type){
	var s,arr = _arr;
	for(let i=1;i<arr.length;i++){
		for(let j = i;j>0;j--){
			if(arr[j] < arr[j -1] && _type == "asc"){
				s = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = s;
			}else if(arr[j] > arr[j -1] && _type == "desc"){
				s = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = s;
			}

		}
	}
	console.log('排序后数组-----',arr);
}




//选择排序
//选择排序法：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部排完。
function sortXuanze(_arr){
	var s;
	for (var i = 0; i < _arr.length; i++) {
		for(var j= i+1; j<_arr.length;j++){
			if(_arr[i] > _arr[j]){
				s = _arr[i];
				_arr[i] = _arr[j];
				_arr[j] = s;
			
			}
		}
	}
		console.log('排序后数组-----',_arr);
}

//快速排序
//基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
function sortFast(_arr){
	if(_arr.length <= 1){ return _arr;}
	var pIndex = Math.floor(_arr.length / 2);
	var p = _arr.splice(pIndex,1);
	var Ldata = [],Rdata = [];
	
	for(var i=0; i<_arr.length;i++){
		if(_arr[i] < p){
			Ldata.push(_arr[i]);
		}else{
			Rdata.push(_arr[i]);
		}
	}
	return sortFast(Ldata).concat(p,sortFast(Rdata));
}


// sortMaopao(arr,"asc");
// sortCharu(arr,'asc');
// sortXuanze(arr);
var newData = sortFast(arr);
console.log('*********',newData);

新增堆排序：

堆排序理解教程=》https://www.cnblogs.com/chengxiao/p/6129630.html

//    var arr = [10,7,5,6,3,4,2,9,8,1];
    var arr = [9,8,7,6,5,4,3,2,1,0];
    var sorts = function(){}
    sorts.prototype.sort = function(_arr){
        console.log('初始化数组-->',_arr);
        //1.构建大顶堆
        for(var i=Math.floor(_arr.length/2)-1;i>=0;i--){
            console.log('大顶锥第一次循环---数组--A> i-',i,'v-',_arr[i],_arr);
            this.adjustHeap(_arr,i,_arr.length);
            console.log('大顶锥第一次循环---数组--B> i-',i,'v-',_arr[i],_arr);
        }

        console.log('大顶锥第2次---->',_arr);

        //2.调整堆结构+交换堆顶元素与末尾元素
        for(var j=_arr.length-1;j>0;j--){
            console.log('大顶锥第2次---->A-换位置之前 ',_arr,'J '+j);
            this.swap(_arr,0,j);//将堆顶元素与末尾元素进行交换
            console.log('大顶锥第2次---->B-换位置之后 ',_arr,'J '+j);
            this.adjustHeap(_arr,0,j);//重新对堆进行调整
            console.log('大顶锥第2次---->c-排序结果 ',_arr,'J '+j);
        }

        console.log('大顶锥第3次---->',_arr);
    }
    //排序
    sorts.prototype.adjustHeap = function(arr,i,len){

        //console.log('排序 ---->i:'+i+"-len:"+len);

        var temp = arr[i];//先取出当前元素i
        for(var k=i*2+1;k<len;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<len && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                console.log('当前 K ++ ---->',k,i);
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }

            console.log('参加循环------'+'i:'+i+"-len:"+len);
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    sorts.prototype.swap = function(arr,a,b){
        var item = arr[a];
        arr[a] = arr[b];
        arr[b] = item;
    }

    var sortsNew = new sorts();
    sortsNew.sort(arr)