js前端算法---排序

目录 1.冒泡排序（两两对比换位）2.选择排序（每次检索一遍找出最小值换到前面）3.插入排序4.快速排序{取一个中枢、对比每个值、比它小放左边、比它大放右边}5.归并排序（两两分成一堆进行排序、多堆再合起来）6.二分搜索（前提是数列是有序的！）7.希尔排序

1.冒泡排序（两两对比换位）

function arrSort( arr ){
	for(let i=0;i<arr.length-1;i++){
		for(let j=0;j<arr.length-1-i;j++){
			if( arr[j] > arr[j+1]){
				let temp = arr[j];
				arr[j] =  arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}
let arr = [29,10,14,37,14];
console.log( arrSort( arr ) );

2.选择排序（每次检索一遍找出最小值换到前面）

function sortMin( arr ){
	let indexMin = 0;
	for( let i=0;i<arr.length-1;i++){
		indexMin = i;
		for( let j=i+1;j<arr.length;j++){
			if( arr[j] < arr[indexMin] ){
				indexMin = j;
			}
		}
		let temp = arr[i];
		arr[i] = arr[indexMin];
		arr[indexMin] = temp;
	}
	return arr;
}
let arr = [29,10,14,37,14];
console.log( sortMin(arr) );

3.插入排序

从第一个元素开始，该元素可以被认为已经被排序取出下一个元素，在已经排序号的序列中，从后往前扫描直到找到小于或者等于该元素的位置将该位置后面的所有已经排序的元素从后往前移动将该元素插入到该位置重复步骤（2-5）

function insertSort( arr ){
	let len = arr.length;
	for(let i=1;i<len;i++){
		let temp = arr[i];
		let j = i-1;//默认已排序的元素
		//在已经排序好的队列进行从后到前的扫描
		while( j>=0 && arr[j] > temp ){
			//已排序的元素大于新元素，将该元素移动到下一个位置
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = temp;
	}	
	return arr;
}
let arr = [5,3,4,2,1];
console.log(  insertSort(arr)  );

4.快速排序{取一个中枢、对比每个值、比它小放左边、比它大放右边}

let arr = [29,10,14,37,4];
function quickSort( arr ){
	if( arr.length <=1 ) return arr;
	let mid = Math.floor(  arr.length/2  );
	let pivot = arr.splice(mid,1)[0];
	let left =[];
	let right = [];
	for( let i=0;i<arr.length;i++){
		if( arr[i] <pivot ){
			left.push( arr[i] );
		}else{
			right.push( arr[i] );
		}
	}
	return quickSort(left).concat([pivot],quickSort(right));
}
console.log( quickSort(arr)  );

5.归并排序（两两分成一堆进行排序、多堆再合起来）

let arr = [8,4,5,7,1,3,6,2];
function mergeSort( arr ){
	if( arr.length < 2 ) return arr;
	let mid = Math.floor(  arr.length/2 );
	let merge = function(leftArr,rightArr){
		console.log( leftArr,rightArr );
		let resultArr = [];
		while( leftArr.length && rightArr.length ){
			resultArr.push(  leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift()   )
		}
		return resultArr.concat(leftArr).concat(rightArr);
	}
	return merge( 
		mergeSort(arr.slice(0,mid)),
		mergeSort(arr.slice(mid))
	);
}
console.log( mergeSort(arr)  );

6.二分搜索（前提是数列是有序的！）

let arr = [1,2,3,4,5,6,7];
let target = 6;
function search( arr , target ){
	let conut = 1;
	let start = 0;
	let end = arr.length-1;
	while(  start<=end  ){
		//取出中间值
		let middle = Math.floor( (start+end)/2 );
		let guess = arr[middle];
		//如果中间 == 目标值
		console.log( conut );
		if( guess== target ){
			return middle;//返回位置
		}
		if( guess > target ){
			end = middle;
		}
		if( guess < target ){
			start = middle + 1;
		}
		conut++;
	}
	return -1;
}
console.log( search( arr , target) );

7.希尔排序

希尔排序原理链接

//shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i < arr.length; i++) {
      let j = i;
      let temp = arr[j];
      for(; j> 0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));