相关算法排序安排

原创
2019/02/27 10:18
阅读数 68
1排序算法分类

冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 推排序 计数排序 桶排序 基数排序

2 计算代码如下

  冒泡排序 function bubbleSort(arr) {

 let len = arr.length;
 for(let i = 0;j<len-1-i;j++){
    for(let j = 0;j< len-1-i;j++) {
	   if(arr[j]>arr[j+1]){
	       [arr[j+1],arr[j]] = [arr[j],arr[j+1]];
	   }
	}
 }
  return arr;
}

//快排demo:
    function quickSort(arr,left,right) {
      let len = arr.length;
      let partitionIndex;
      left = typeof left != 'number'? 0 :left;
      right = typeof right !='number'? len -1 :right;
      if(left<right) {
        partitionIndex = partition(arr,left,right);
	    quickSort(arr,left,partitionIndex-1);
	    quickSort(arr,partitionIndex+1,right);
      }
     return arr;
  }
function partition(arr,left,right) {
  let pivot = left;
  let index = pivot + 1;
  for(let i = index;i<=right;i++) {
  if(arr[i]<arr[pivot]){
      [arr[i],arr[index]] = [arr[index],arr[i]];
	  index++;
    }
  }
 [arr[pivot],arr[index-1]] = [arr[index-1],arr[pivot]];
  return index-1
}
// 选择demo 
  function selectionSort (arr){
  let len = arr.length;
  let minIndex;
  for(let i=0;i<len-1;i++) {
  minIndex = i;
  for (let j=i+1;j<len;j++) {
    if (arr[j] < arr[minIndex]) {     //寻找最小的数
		    minIndex = j;                 //将最小数的索引保存
	    }
    }
	[arr[i],arr[minIndex]] = [arr[minIdenx],arr[i]];
  }
  return  arr
}

// 插入排序:每次排一个数组项,假设数组的第一项已经排序,接着,把第二项与第一项进行对比,第二项是该插入到第一项之前还是之后,第三项是该    插入到第一项之前还是第一项之后还是第三项
function insertionSort(arr) {
  let len = arr.length;
  let preIndex,current;
  for(let i<len;i++) {
     preIndex = i -1;
	 current = arr[i];
	 while (preIndex >=0 && arr[preIndex]>current) {
	     arr[preIndex+1] = arr[preIndex];
		 preIndex--;
	 }
	 arr[preIndex+1] = current;
  }
   return arr;
}
// 归并排序:Mozilla Firefox 使用归并排序作为Array.prototype.sort的实现,而chrome使用快速排序的一个变体实现的,前面三种算法性能不好,但归并排序性能不错 算法复杂度O(nlog^n)
 function mergeSort (arr) {
   let len = arr.length;
   if(len<2) {
     return arr 
   }
    let middle = Math.floor(len/2),
	left = arr.slice(0,middle);
	return merge(mergeSort(left),mergeSort(right));
	
 }
 
function merge(left, right){
let result = [];
while (left.length && right.length) {
    if (left[0] <= right[0]) {
        result.push(left.shift());
    } else {
        result.push(right.shift());
    }
}
result.push(...left);
result.push(...right);
return result;
 //堆排序:堆排序把数组当中二叉树来排序而得名。
   var len;
function buildMaxHeap(arr) {
      len = arr.length;
	  for(let i = Math.floor(len/2;i>=0;i--){
	      heapify(arr,i)
	  }
   }
 function heapify(arr,i) {
     let left = 2* i+1;
	 let right = 2*i+2;
	 let largest = i;
	 if(left<len && arr[left]> arr[largest]) {
	     largest = left;
	 }
	 if(right < len && arr[right]>arr[largest]){
	  largest = right;
	 }
	 if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest);
    }
  }
function heapSort(arr) {
   buildMaxHeap(arr);
  for (let i = arr.length - 1; i > 0; i--) {
		[arr[0],arr[i]]=[arr[i],arr[0]];
		len--;
		heapify(arr, 0);
  }
  return arr;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部