网站地图    收藏   

主页 > 前端 > javascript >

javascript实现9大排序,冒泡,插入等排序

来源:未知    时间:2020-05-07 15:37 作者:小飞侠 阅读:

[导读] 今天带来常见九大排序与基本算法JS篇。 下面一张图看9大排序... 由此可见 稳定: 如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定: 如果a原本在b的前面,而a=b,排序之后...

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

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

image.png

由此可见

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;

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

内排序:所有排序操作都在内存中完成;

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

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

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

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

image.png


源码:

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)


自学PHP网专注网站建设学习,PHP程序学习,平面设计学习,以及操作系统学习

京ICP备14009008号-1@版权所有www.zixuephp.com

网站声明:本站所有视频,教程都由网友上传,站长收集和分享给大家学习使用,如由牵扯版权问题请联系站长邮箱904561283@qq.com

添加评论