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

image.png

設(shè)定第一個(gè)值為分界的值骏庸，選取兩個(gè)指針毛甲，j為小于v的最后一個(gè)值，i為當(dāng)前要比較的值具被，當(dāng)arr[i]<v則讓arr[i]與大于v的第一個(gè)值交換玻募，也就是小于v的最后一個(gè)值得下一個(gè)值交換，當(dāng)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);

改進(jìn)1
大量相等數(shù)據(jù)會(huì)讓生成的樹(shù)極度不平衡叮叹，因此我們改進(jìn)之前的算法艾栋，分成兩部分，從兩頭遍歷蛉顽，當(dāng)左邊訪(fǎng)問(wèn)的值小于v的時(shí)候裹粤，直接i++,直到訪(fǎng)問(wèn)的值大于等于v的時(shí)候停止，同理蜂林，當(dāng)右邊訪(fǎng)問(wèn)的值大于v的時(shí)候遥诉，直接j--，直到訪(fǎng)問(wèn)的值小于等于v的時(shí)候停止噪叙，這樣矮锈，交換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){
  //隨機(jī)選取一個(gè)值，并不是始終選擇第一個(gè)值
  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);

改進(jìn)2---------三路快速排序
直接將數(shù)組分成三部分

image.png

function quick3ways(arr,l,r){
  if(l >= r)
      return;
  //隨機(jī)選取一個(gè)值子眶，并不是始終選擇第一個(gè)值
  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);