n：数据规模；
稳定:两个相等的值在排序前后相对位置是否改变，如果不会改变则成为稳定，反之为不稳定；
排序方式：内排序In-place是指所有操作都在内存中完成；外排序Out-place把数据放在磁盘中，排序通过磁盘和内存的数据传输才能进行；
时间复杂度：算法执行所消耗的时间；
空间复杂度：算法执行所需的内存的大小；
<b>快速排序基于冒泡、递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低（见图表）而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。</b>
第一种看起来比较复杂，但是内存占用比较少。
functionquickSort(arr, left, right){/*
* len为数组的长度;
* left为需要数组中参与排序的起始点；right为数组中参与排序的终止点;
* left如果有传数字那么就为left，没有传参则为0；
* right如果有传参那么就为right，没有传参则为len-1;
* 有传参可能会部分排序可能不会排序，没传参默认排序整个数组;
* partitionIndex为分组界限;
*/varlen = arr.length, partitionIndex, left =typeofleft !=='number'?0: left, right =typeofright !=='number'? len -1: right;// 如果需要排序的起始索引小于终止索引则执行排序;递归的终止条件；if(left < right) {// partition的返回值作为partitionIndex来分隔数组；// 索引partitionIndex左边的元素均小于arr[partitionIndex]；// 右边的元素均大于arr[partitionIndex]；partitionIndex = partition(arr, left, right);// 数组中小于arr[partitionIndex]的部分(索引left到partitionIndex-1)再次使用quickSort排序；quickSort(arr, left, partitionIndex -1);// 数组中大于arr[partitionIndex]的部分(索引partitionIndex+1到right)再次使用quickSort排序；quickSort(arr, partitionIndex +1, right); }// 递归执行直到不满足left<right;返回本身；returnarr;}functionpartition(arr, left, right){/*
* 这部分是具体实现排序的部分；
* 将left赋值给pivot，作为参照物，因为left在最左边，只需要从左到右比较一遍即可判断整个数组；
* index索引是arr中待交换位置；
*/varpivot = left, index = pivot +1;// for循环从参照物arr[pivot]下一个元素arr[pivot+1]开始一直比较到子数组结束arr[right]；for(vari = index; i <= right; i++) {// 循环中如果有任何小于参照物的，就将他交换到index的位置，然后index向右移动到下一个位置；if(arr[i] < arr[pivot]) { swap(arr, i, index); index++; } }/*
* 因为每次都是交换完后index移动到下一个位置，所以在循环结束时，index仍为待交换的位置；
* 此时索引pivot+1到index-1的元素都小于参照物arr[pivot]；
*/// 交换pivot和index-1索引的值之后index-1索引左边全都是小于arr[index-1]的元素；swap(arr, pivot, index -1);// 返回index-1作为拆分子数组的分界线；returnindex -1;}/*
* 普通的交换，将a[i]和a[j]的数值交换；
*/functionswap(arr, i, j){vartemp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}
第二种比较容易理解，但是内存占用较多。
functionquickSort(arr){/*
* 创建len保存数组的长度，每次获取数组的长度都要实时查询不利于性能；
* index作为保存取到的中间值；
* pivot保存比较参照物；
* left、right作为子数组的容器；
*/varlen = arr.length, index, pivot, left=[], right=[];// 如果数组只有一位，就直接返回数组,递归的终止条件；if(len <=1)returnarr;//获取中间值的索引，使用Math.floor向下取整；index =Math.floor(len /2);// 使用splice截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；// 如果此处使用pivot=arr[index]; 那么将会出现无限递归的错误；// splice影响原数组，原数组长度减一；pivot = arr.splice(index,1); len -=1;// 小于arr[pivot]的存到left数组里，大于arr[pivot]的存到right数组；for(vari =0; i < len; i++) {if(pivot > arr[i]) { left.push(arr[i]); }else{ right.push(arr[i]); } }// 不断把分割的左右子数组传入quickSort，直到分割的只有一位直接返回子数组本身，递归终止；// 把每次分割的数组一层一层的用concat连接起来；// 每一层left里的元素都小于对应的pivot,right里的元素都大于对应的pivot；returnquickSort(left).concat(pivot, quickSort(right));}
