判断参数合理性, 获取数组长度
- function quick_sort(arr){
- if(arr==null){
- return;
- }
- _quick_sort(arr,0,arr.length-1);
- return arr;
- }
将一段数组分成两部分, 左边全小于某个数, 右边全大于某个数, 返回此数的 key;
- function getmid(arr,start,end){
- var stand=arr[start];
- var left=start;
- var right=end;
- while(left<right){
- while(left<right && arr[right]>stand){
- right--;
- }
- while(left<right && arr[left]<stand){
- left++
- }
- if(left!=right){
- var a=arr[right];
- arr[right]=arr[left];
- arr[left]=a;
- }
- }
- return right;
- }
循环执行上述排序
- function _quick_sort(arr,start,end){
- if(start>=end){
- return;
- }
- var mid=getmid(arr,start,end);
- _quick_sort(arr,start,mid-1);
- _quick_sort(arr,mid+1,end);
- }
测试一下:
- function getmid(arr,start,end){
- var stand=arr[start];
- var left=start;
- var right=end;
- while(left<right){
- while(left<right && arr[right]>stand){
- right--;
- }
- while(left<right && arr[left]<stand){
- left++
- }
- if(left!=right){
- var a=arr[right];
- arr[right]=arr[left];
- arr[left]=a;
- }
- }
- return right;
- }
- function _quick_sort(arr,start,end){
- if(start>=end){
- return;
- }
- var mid=getmid(arr,start,end);
- _quick_sort(arr,start,mid-1);
- _quick_sort(arr,mid+1,end);
- }
- function quick_sort(arr){
- if(arr==null){
- return;
- }
- _quick_sort(arr,0,arr.length-1);
- return arr;
- }
- console.log(quick_sort([3,2,6,1,4]));
来源: http://www.qdfuns.com/article/17431/21a534015e326ebd01971f4773829746.html