快速排序，是对冒泡排序的一种改进，快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归。
简单的说就是，先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证：其左边的元素都不大于它，其右边的元素都不小于它。这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。
例：将数组arr=[8,2,5,7,4,3,6,9]进行排序；
（1）首先设置一个临时变量用来存放随机取出数组中的一个数，一般取数组的第一个元素。temp=a[0];
（2）设置指针i，j分别指向数组的第一个元素和数组的最后一个元素；
（3）让j从后向前查询，j--，直到找到第一个小于a[i]的元素，则将j指向的元素和i指向的元素交换位置；
（4）让i从前向后查询 ，i++，直到找到第一个大于a[j]的元素，则将i指向的元素和j指向的元素交换位置
（5）重复（3）（4），当i，j指针都指向目标元素后。一遍排序完成
实现
c++代码实现
#include<stdio.h>
#include<stdlib.h>
#define N 8;
int partition(int arr[],int low,int high){
int key;
key=arr[low];
while(low<high){
while(low<high&&arr[high]>=key){
high--;
}
if(low<high){
arr[low++]=arr[high];
}
while(low<high&&arr[low]<=key){
low++;
}
if(low<high){
arr[high--]=arr[low];
}
}
arr[low] = key;
return low;
}
void quick_sort(int arr[],int start,int end){
int pos;
if(start<end){
pos=partition(arr,start,end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
int main(void){
int i;
int arr[N]={8,2,5,7,4,3,6,9};
quick_sort(arr,0,N-1);
}
js写法
<script>
function quickSort(array){
var len =array.length;//数组长度
if(len<=1){ //数组长度为1，则不需要排序
return array;
}
var pivot = array[0];//选第一个元素为基准
var leftArr = [];//存储比基准小的元素
var rightArr = [];//存储比基准的大的元素
for(var i=1;i<len;i++){
if(array[i]<pivot){
leftArr.push(array[i]);
}
else{
rightArr.push(array[i]);
}
}
return quickSort(leftArr).concat(pivot,quickSort(rightArr));
}
var array=[8,2,5,7,4,3,6,9];
alert(quickSort(array));
</script>