java实现快速排序

快速排序

作者：Legend

QQ：158067568

快排是分治法的一个应用，快排主要是通过一个设定枢轴，然后以这个枢轴为标杆，将待排序列按大小分成比枢轴大的，和比枢轴小的两部分。然后在对划分完的子序列进行快排，知道子序列中元素的个数为1位置。

快速排序实现

快排是程序员必须掌握的，举一个例子来解释，如下图：

<!--[endif]-->

首先选定枢轴，一般设置low所对应的元素位置为枢轴，如图选定的枢轴为26。

在高位指针始终不小于低位指针的前提下：

高位指针开始判断其是否比枢轴值大，如果符合，高位指针减1，继续寻找，直到找到不符合的情况，然后把该值赋给此时低位所在位置。

低位指针开始判断其是否比枢轴值小，如果符合，低位指针加1，继续寻找，直到找到不符合情况，然后将该值赋给此时高位指针所指位置。

如此反复，知道低位与高位指针重合，此时，在讲当前的枢轴值赋给低位指针所指的值。这样就完成了一次排序。

此时枢轴值就到了其最终位置上，然后继续对以枢轴为轴的两部分进行排序。

JAVA实现快速排序

package cn.edu.heut.zcl;
 
public class QuickSort {
        
         /**
          * 快速排序，对整数型数组o进行
          * @param o
          * @param low
          * @param hight
          */
         public static void quiteSort( int[] o , int low , int hight ){
                   if(low < hight){
                            int povitePosition = adjust(o,low,hight);
                            quiteSort( o , low , povitePosition - 1);
                            quiteSort( o , povitePosition + 1 , hight );
                   }
         }
         /**
          * 进行调整
          * @param o
          * @param low
          * @param hight
          * @return
          */
         private static int adjust( int[] o , int low , int hight ){//选定枢轴为low所对应的值
                   int pivote = o[low];
                   while(low < hight){
                            while(hight > low && compare( pivote , o[hight] ) <= 0 ){// 高位找到比povite大，则符合要求，继续寻找
                                     hight -- ;
                            }
                            o[low] = o[hight] ;
                            while(low < hight && compare( pivote , o[low] ) >= 0){ //低位开始找到比povite小，符合要求，继续寻找
                                     low ++ ;
                            }
                            o[hight] = o[low];
                   }
                   o[low] = pivote ;
                   return low;
         }
        
         /**
          *
          * @param num1 减数
          * @param num2 被减数
          * @return
          */
         private static int compare(int num1, int num2) {
                   return num1 - num2 ;
         }
         /**
          * @param args
          */
         public static void main(String[] args) {
                   int[] i = {26,53,48,15,13,46,32,15};
                   quiteSort(i, 0, i.length-1);
                   for(int ii:i){
                            System.out.print(ii+" ");
                   }
         }
}

 

代码全在这，就不上传附件了。很久没有看算法了，今天去面试，居然写不出来快排，简直是耻辱。知错改错吧。

 

 

评论

7 楼 herber2010 2014-02-18  

图有错误~~

6 楼 chaiyuan1994 2013-11-24  

啊我懂了...请忽视LS评论，谢谢博主~方便留个联系方式以后有问题请教您么，我是一个软件工程专业大二学生

5 楼 chaiyuan1994 2013-11-24  

我是个菜鸡，在网上查快速排序的讲解，博主的这个版本是我看的最容易懂的一个...点赞！只是有一点不太明白，不知道是我理解有误还是作者不小心手滑了：
Line 31，作者的意思是不是对low位和high位的值进行交换？如果是的话，不是应该写成O[LOW]=TEMP;O[LOW]=O[HIGH];O[HIGH]=O[LOW]么。（Line 37同理）

4 楼 dai0_0dai 2013-08-19  

dai0_0dai 写道

这个排序是有问题的，会有数组越界的情况

自己写了一遍，没问题，哈哈

3 楼 dai0_0dai 2013-08-19  

这个排序是有问题的，会有数组越界的情况

2 楼 yinzhuo 2012-03-05  

yinzhuo 写道

int a[] = { 5, 3, 6, 2, 7, 1, 9, 4, 8};

用这个排序 会报错。  Eclipse编译执行。。   求解。  同样用C写了编译 确没问题。 而且就这个序列会报错。。

这是我滴方法

public static void qSort(int q[], int left, int right) {
int i = left + 1, j = right;
int m = q[left];
int temp;
while (i <= j) {
while (q[i] <= m && i <= j)
i++;
while (q[j] >= m && i <= j)
j--;
if (i < j) {
temp = q[i];
q[i] = q[j];
q[j] = temp;
i++;
j--;
}
}
if(j != left){
temp = q[j];
q[j] = m;
q[left] = temp;
}
System.out.println(j);
System.out.println("i:" + i);

if ( j- 1 > left)
qSort(q, left, j-1);
if (j + 1 < right)
qSort(q, j+1 , right);
}

1 楼 yinzhuo 2012-03-05  

int a[] = { 5, 3, 6, 2, 7, 1, 9, 4, 8};

用这个排序 会报错。  Eclipse编译执行。。   求解。  同样用C写了编译 确没问题。 而且就这个序列会报错。。