2.4.2 查找和排序

排序

复习1：冒泡排序

function BubbleSort(arr){
  for(let i=0;i<arr.length-1;i++){
    for(let j=0;j<arr.length-1-i;j++){
      let temp;
      if(arr[j]>arr[j+1]){
        temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
      }
    }
  }
}

复习2：快速排序

function QuickSort(arr){
  quicksort(arr,0,arr.length-1);
}
function quicksort(arr,first,end){
  if(end>first){
    let pivotIndex=partitial(arr,first,end);
    quicksort(arr,first,pivotIndex-1);
  quicksort(arr,pivotIndex+1,end);
  }
}

function partitial(arr,first,end){
  let low=first+1;
  let high=end;
  let pivot=arr[first];
  while(low<high){
      while(low<=high&&arr[low]<=pivot)
        low++;
      while(low<=high&&arr[high]>pivot)
        high--;
      if(low<high){
        let temp=arr[low];
        arr[low]=arr[high];
        arr[high]=temp;
      }
  }
  
  while(arr[high]>pivot&&high>first)
    high--;
  
  if(arr[high]<pivot){
    arr[first]=arr[high];
    arr[high]=pivot;
    return high;
  }   
  else
    return first;
}

查找

1）顺序查找
2）二分查找

function binirySerch(arr,ele){
  let low=0;
  let high=ele.length-1;
   while(low<=high){
       mid=low+(high-low)/2;
       if(ele===arr[mid]){
         return mid; 
        }
       else if(ele<arr[mid]){
        high=mid-1;
      }
       else
           low=mid+1;
   }
  return -1;
}

3）哈希表查找
4）二叉排序树查找