前端开发

今天带来常见九大排序与基本算法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[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;i0;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);