经典算法之快速排序
快速排序
算法概念
了解一个知识，必须先要从其含义开始。 什么是快速排序呢，顾名思义，快速的排序，快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。 怎么解释呢，一个例子让你大概理解快速排序：🌰苹果质量大小排序例子。 在面前有8个苹果，分别为[2,8,7,1,3,5,6,4]，其质量大小和其编号一致。先需要其按照大小顺序排列。
使用快速排序进行排序。简单的讲就是将取一个苹果作为中间值，将剩余苹果以这个苹果为基准，小苹果放在前面，大苹果放在右面，再将这个苹果插入到两堆苹果之间。然后在对前面小苹果以此再次排序，直到剩余苹果个数为1时，则取消排序，再紧接着对大苹果进行排序，直到剩余苹果个数为1；
首先，将数组最后一个作为基准，将基准与前面元素比较，4大于2，将2分为小苹果；4小于8，将8分为大苹果；7大于4，将7分为大苹果；1小于4；将1分为小苹果，并将1号放置到小苹果最后面的位置，也就是8号苹果的位置，将其1与8互换位置。此时的顺序为【2,1,7,8,3,5,6,4】；接下来比较3小于4，则3和7互换位置。此时顺序为【2,1,3,8,7,5,6,4】;继续比较，5、6大于4;位置不变。最后，将基准元素与大苹果堆的第一个元素互换位置。此时的元素顺序为【2,1,3,4,7,5,6,8】，然后再返回标记基准的位置，当做下一次的最大区间；也就是参数当中的r。然后再一次调用方法quickSort方法。当长度为1时，才进行对大区间进行再一次排序。直至完成全部排序。
算法图例（部分)
代码实现
var arr =[2,8,7,1,3,5,6,4]
var partition=function(a,p,r){
var x=a[r];
var i=p-1;
for(var j=p;j<r;j++){
if(a[j]<x){
i++;
var tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
var tmp=a[i+1];
a[i+1]=a[r];
a[r]=tmp;
return i+1;
}
var quickSort=function(a,p,r){
if(p< r){
var q=partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,p+1,r);
}
}代码解析
方法quickSort
var quickSort=function(a,p,r){
if(p< r){
var q=partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,p+1,r);
}
}参数｛ a:：待排数组 p：开始排序的下标 r:结束区间下标 ｝ 当p<r为true时，进入方法
var q=partition(a,p,r);调用排序方法，将大小苹果与基准比较分开，并返回基准的下标
quickSort(a,p,q-1);递归调用，将获取的最小区间位置再进行排序，直到小区间小于1时，结束排序。接着进行大区间排序
大区间排序
quickSort(a,p+1,r);排序方法 partition
var partition=function(a,p,r){
var x=a[r];
var i=p-1;
for(var j=p;j<r;j++){
if(a[j]<x){
i++;
var tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
var tmp=a[i+1];
a[i+1]=a[r];
a[r]=tmp;
return i+1;
}获取基准的值
var x=a[r];最小边界值的前一位（目的是当为了在if方法不进入时，能够将自身的值赋给自身）
var i=p-1;交换区域内比较大小的值
for(var j=p;j<r;j++){
if(a[j]<x){
i++;
var tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}将基准与最大区域的最小值调换位置
var tmp=a[i+1];
a[i+1]=a[r];
a[r]=tmp;
return i+1;总结
快速排序利用递归方法，将数组不断分成小区间与大区间，直至所有的数组都按住从小到大进行排列。
腾讯云开发者
