基本思想：找到一個數(shù)作為參考，比這個數(shù)字大的放在數(shù)字左邊，比它小的放在右邊； 然后分別再對左邊和右變的序列做相同的操作(遞歸).
第一種

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
大量相等數(shù)據(jù)會讓生成的樹極度不平衡，因此我們改進之前的算法，分成兩部分，從兩頭遍歷，當左邊訪問的值小于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---------三路快速排序
直接將數(shù)組分成三部分

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);