js实现高级排序（希尔排序和快速排序）

数据结构已经学完了，整体对于数据结构有所了解，但是还是处于入门阶段吧，对各种场景下，数据结构的选择和算法实现不能给灵活的运用，主要是对算法的认识不够深刻，关键点把握不够牢固，通过这个文章，记录一下我对高级排序的实现方式，从而对前面所学的内容进行回顾

1.希尔排序

原理

希尔排序是在插入排序的基础上进行的更加深刻的优化，其中也体现出了希尔对插入排序算法的深刻理解。

希尔排序核心思想是通过挑选一定的间隔，来对一组数据进行大小排序，尽可能的使最小的数字距离正确位置更近一些，随着间隔的减小，直到间隔为1，就是简单排序中的插入排序了。

注意要点

• 希尔排序关键要找出一个合适的间隔，希尔采用的是每次循环间隔大小是N/2。
• 排序方式使用插入排序

实现代码

function shellSort(arr){
  let gap = Math.floor(arr.length/2);
  while(gap>0){
    for(let i=gap;i<arr.length;i++){
      let tmp = arr[i];
      let k = i;//内层插入初始化变量，注意下面循环查找是从后往前查找并插入的。
      while( tmp < arr[k-gap]&&k>0 ){
        arr[k] = arr[k-gap];
        k -= gap;
      }
      arr[k] = tmp;
    }  
  	gap = Math.floor(gap/2);
  }
	return arr;
}

2. 快速排序

原理

快速排序利用了分而治之的思想，从一堆数中拿出来一个，其他的按照大的放左边，小的放右边，这样就可以确定，拿出来的这个就是正确位置了的，接下来就分别多左边指针和右边指针再次分而治之，直到最后指针大小都一样。

注意要点

• 快速排序需要用到递归，但是递归的结束条件是传入的开始元素指针必须要大于结束元素
• 挑选第一个数也比较重要，尽可能挑选到接近中间的数，这样可以让算法更均匀

代码实现

//获取中间数数据，作为第一个被挑出来的
function getMiddle(arr,start,end){
  let middle = Math.floor((start+end)/2);
  let tmp;
  //下面使用了冒泡排序挑选出最中间的数
  if(arr[start]>arr[middle]){
    tmp = arr[start];
    arr[start] = arr[middle];
    arr[middle] = tmp;
  }
  if(arr[middle]>arr[end]){
    tmp = arr[middle];
    arr[middle] = arr[end];
    arr[end] = tmp;
  }
  if(arr[start]>arr[middle]){
    tmp = arr[start];
    arr[start] = arr[middle];
    arr[middle] = tmp;
  }
  return {pivot:middle,arr};
}
function quickSort(arr,start=0,end=arr.length-1){
  let {pivot,arr:newArr} = getMiddle(arr,start,end);
  arr = newArr;
  let left,right,tmp;//定义双指针
  tmp = arr[pivot];
  arr[pivot] = arr[end-1];
  arr[end-1] = tmp;
  pivot = end-1;
  left = start;
  right = pivot;
  while(left<right){
    //因为经getMiddle 已经把两端的位置大小排好了
    if(arr[left] > arr[right]){
      tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
    }
    while(arr[++left]<arr[pivot]){}
    while(arr[--right]>arr[pivot]){}
  }
  if(pivot != left){
    tmp = arr[pivot];
    arr[pivot] = arr[left];
    arr[left] = arr[pivot];
    pivot = left;
  }
  if(pivot - 1 >start){
   arr = quickSort(arr,start,pivot-1);
  }
  if(end > pivot+1){
   arr = quickSort(arr,pivot+1,end);
  }
  return arr;
}