快速排序

基本思想：找到一个数作为参考，比这个数字大的放在数字左边，比它小的放在右边； 然后分别再对左边和右变的序列做相同的操作(递归).
第一种

image.png

设定第一个值为分界的值，选取两个指针，j为小于v的最后一个值，i为当前要比较的值，当arr[i]<v则让arr[i]与大于v的第一个值交换，也就是小于v的最后一个值得下一个值交换，当arr[i]>v则直接i++，最后让分界值与j交换这样，j左边的值就是全小于v，右边的值全大于v

function quickSort(arr,l,r){
    if(l >= r)
      return;
    var p = partition(arr,l,r);
    quickSort(arr,l,p-1);
    quickSort(arr,p+1,r);
  }

  function partition(arr,l,r){
    var v = arr[l];

    var j=l;
    for(var i=l+1;i<=r;i++){
      if(arr[i] < v){
        [arr[i],arr[j+1]] = [arr[j+1],arr[i]];
        j++;
      }
    }
    [arr[l],arr[j]] = [arr[j],arr[l]];
    return j;
  }

  var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
  quickSort(arr,0,arr.length-1);
  console.log(arr);

改进1
大量相等数据会让生成的树极度不平衡，因此我们改进之前的算法，分成两部分，从两头遍历，当左边访问的值小于v的时候，直接i++,直到访问的值大于等于v的时候停止，同理，当右边访问的值大于v的时候，直接j--，直到访问的值小于等于v的时候停止，这样，交换i和j的值，就将两边分成了<=v和>=v两部分，分散了==v的部分。

image.png

  function quickSort(arr,l,r){
    if(l >= r)
      return;
    var p = partition2(arr,l,r);
    quickSort(arr,l,p-1);
    quickSort(arr,p+1,r);
  }

function partition2(arr,l,r){
  //随机选取一个值，并不是始终选择第一个值
  var t = Math.floor(Math.random()*(r-l+1)+l);
  [arr[t],arr[l]] = [arr[l],arr[t]];
  var v = arr[l];

  var i = l+1, j = r;
  while( true ){
    while( arr[i] < v && i <= r)  
      i++;
    while( arr[j] > v && j >= l+1)  
      j--;
    if(i > j) 
      break;
    [arr[i],arr[j]] = [arr[j],arr[i]];
    i++;
    j--;
  } 
  [arr[l],arr[j]] = [arr[j],arr[l]]; 
  return j;
}

  var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
  quickSort(arr,0,arr.length-1);
  console.log(arr);

改进2---------三路快速排序
直接将数组分成三部分

image.png

function quick3ways(arr,l,r){
  if(l >= r)
      return;
  //随机选取一个值，并不是始终选择第一个值
  var t = Math.floor(Math.random()*(r-l+1)+l);
  [arr[t],arr[l]] = [arr[l],arr[t]];
  var v = arr[l];

  var lt = l, gt = r+1;
  var i=l+1;
  while( i < gt ){
    if( arr[i] < v){
        [arr[i],arr[lt+1]] = [arr[lt+1],arr[i]];
        lt++;
        i++;
    }else if( arr[i] > v){
        [arr[i],arr[gt-1]] = [arr[gt-1],arr[i]];
        gt--;
    }else
        i++;
  } 
  [arr[lt],arr[l]] = [arr[l],arr[lt]];
  quick3ways(arr,l,lt-1);
  quick3ways(arr,gt,r);
}

  var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
  quick3ways(arr,0,arr.length-1);
  console.log(arr);