n：數(shù)據(jù)規(guī)模；

穩(wěn)定:兩個(gè)相等的值在排序前后相對(duì)位置是否改變，如果不會(huì)改變則成為穩(wěn)定辆影，反之為不穩(wěn)定；

排序方式：內(nèi)排序In-place是指所有操作都在內(nèi)存中完成黍特；外排序Out-place把數(shù)據(jù)放在磁盤(pán)中蛙讥，排序通過(guò)磁盤(pán)和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；

時(shí)間復(fù)雜度：算法執(zhí)行所消耗的時(shí)間灭衷；

空間復(fù)雜度：算法執(zhí)行所需的內(nèi)存的大写温；

<b>快速排序基于冒泡今布、遞歸分治。他在大數(shù)據(jù)情況下是最快的排序算法之一拭抬，平均事件復(fù)雜度很低（見(jiàn)圖表）而且前面的系數(shù)很小部默，在大量隨機(jī)輸入的情況下最壞情況出現(xiàn)的概率是極小的。</b>

第一種看起來(lái)比較復(fù)雜造虎，但是內(nèi)存占用比較少傅蹂。

functionquickSort(arr, left, right){/*

? ? * len為數(shù)組的長(zhǎng)度;

? ? * left為需要數(shù)組中參與排序的起始點(diǎn)；right為數(shù)組中參與排序的終止點(diǎn);

? ? * left如果有傳數(shù)字那么就為left算凿，沒(méi)有傳參則為0份蝴；

? ? * right如果有傳參那么就為right，沒(méi)有傳參則為len-1;

? ? * 有傳參可能會(huì)部分排序可能不會(huì)排序氓轰，沒(méi)傳參默認(rèn)排序整個(gè)數(shù)組;

? ? * partitionIndex為分組界限;

? ? */varlen = arr.length,? ? ? ? partitionIndex,? ? ? ? left =typeofleft !=='number'?0: left,? ? ? ? right =typeofright !=='number'? len -1: right;// 如果需要排序的起始索引小于終止索引則執(zhí)行排序;遞歸的終止條件婚夫；if(left < right) {// partition的返回值作為partitionIndex來(lái)分隔數(shù)組；// 索引partitionIndex左邊的元素均小于arr[partitionIndex]署鸡；// 右邊的元素均大于arr[partitionIndex]案糙；partitionIndex = partition(arr, left, right);// 數(shù)組中小于arr[partitionIndex]的部分(索引left到partitionIndex-1)再次使用quickSort排序限嫌；quickSort(arr, left, partitionIndex -1);// 數(shù)組中大于arr[partitionIndex]的部分(索引partitionIndex+1到right)再次使用quickSort排序；quickSort(arr, partitionIndex +1, right);? ? }// 遞歸執(zhí)行直到不滿(mǎn)足left<right;返回本身时捌；returnarr;}functionpartition(arr, left, right){/*

? ? * 這部分是具體實(shí)現(xiàn)排序的部分怒医；

? ? * 將left賦值給pivot，作為參照物奢讨，因?yàn)閘eft在最左邊稚叹，只需要從左到右比較一遍即可判斷整個(gè)數(shù)組；

? ? * index索引是arr中待交換位置拿诸；

? ? */varpivot = left,? ? ? ? index = pivot +1;// for循環(huán)從參照物arr[pivot]下一個(gè)元素arr[pivot+1]開(kāi)始一直比較到子數(shù)組結(jié)束arr[right]扒袖；for(vari = index; i <= right; i++) {// 循環(huán)中如果有任何小于參照物的，就將他交換到index的位置佳镜，然后index向右移動(dòng)到下一個(gè)位置僚稿；if(arr[i] < arr[pivot]) {? ? ? ? ? ? swap(arr, i, index);? ? ? ? ? ? index++;? ? ? ? }? ? }/*

? ? * 因?yàn)槊看味际墙粨Q完后index移動(dòng)到下一個(gè)位置，所以在循環(huán)結(jié)束時(shí)蟀伸，index仍為待交換的位置蚀同；

? ? * 此時(shí)索引pivot+1到index-1的元素都小于參照物arr[pivot]；

? ? */// 交換pivot和index-1索引的值之后index-1索引左邊全都是小于arr[index-1]的元素啊掏；swap(arr, pivot, index -1);// 返回index-1作為拆分子數(shù)組的分界線(xiàn)蠢络；returnindex -1;}/*

* 普通的交換，將a[i]和a[j]的數(shù)值交換迟蜜；

*/functionswap(arr, i, j){vartemp = arr[i];? ? arr[i] = arr[j];? ? arr[j] = temp;}

第二種比較容易理解刹孔，但是內(nèi)存占用較多。

functionquickSort(arr){/*

? ? * 創(chuàng)建len保存數(shù)組的長(zhǎng)度娜睛，每次獲取數(shù)組的長(zhǎng)度都要實(shí)時(shí)查詢(xún)不利于性能髓霞；

? ? * index作為保存取到的中間值；

? ? * pivot保存比較參照物畦戒；

? ? * left方库、right作為子數(shù)組的容器；

? ? */varlen = arr.length,? ? ? ? index,? ? ? ? pivot,? ? ? ? left=[],? ? ? ? right=[];// 如果數(shù)組只有一位障斋，就直接返回?cái)?shù)組,遞歸的終止條件纵潦；if(len <=1)returnarr;//獲取中間值的索引，使用Math.floor向下取整垃环；index =Math.floor(len /2);// 使用splice截取中間值邀层，第一個(gè)參數(shù)為截取的索引，第二個(gè)參數(shù)為截取的長(zhǎng)度遂庄；// 如果此處使用pivot=arr[index]; 那么將會(huì)出現(xiàn)無(wú)限遞歸的錯(cuò)誤寥院；// splice影響原數(shù)組，原數(shù)組長(zhǎng)度減一涛目；pivot = arr.splice(index,1);? ? len -=1;// 小于arr[pivot]的存到left數(shù)組里只磷，大于arr[pivot]的存到right數(shù)組经磅；for(vari =0; i < len; i++) {if(pivot > arr[i]) {? ? ? ? ? ? left.push(arr[i]);? ? ? ? }else{? ? ? ? ? ? right.push(arr[i]);? ? ? ? }? ? }// 不斷把分割的左右子數(shù)組傳入quickSort，直到分割的只有一位直接返回子數(shù)組本身钮追，遞歸終止预厌；// 把每次分割的數(shù)組一層一層的用concat連接起來(lái)；// 每一層left里的元素都小于對(duì)應(yīng)的pivot,right里的元素都大于對(duì)應(yīng)的pivot元媚；returnquickSort(left).concat(pivot, quickSort(right));}