搞定Java快速排序

点击蓝字关注我们

全文字数：   921

阅读时间：   3 分钟

一

简介？

快速排序（Quicksort），简称快排，是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想分治法：即通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以使用递归实现。

二

算法思想？

快速排序算法的核心思想是分治法，先比大小，然后分区。下面我们通过生活中的一个例子来解释一下这个算法思想。假设一个房间中有六个人，排成了一队，他们的年纪分别是21,36,26,22,18,29。我们希望按照他们的年纪从小到达重新进行排列，快速排序的思想是，选一个人的年纪作为基准数，这里选21，然后让剩下的人分别和21比较，小于21的都站在他的左边，大于21的都站在他的右边，通过21把这些人分成了两部分，然后对这两部分重复上边的步骤，即选基准数比较，分成两部分，再重复。。。。。。

三

实现思路？

挖坑填数：以上面年龄排序为例

1.将第一个数21作为基准数，从队伍中站出来，队伍就空出了一个位，即形成了一个坑。

    i->                                                              <-j

2.从后向前找比21小的或等于21年纪的人，找到后让这个人站到前一个空的位置，形成一个新的空位。

  i->                                                  <-j

3.接着由前向后找比21年纪大或者等于21的人，找到后再让这个人站到前一个空的位置，又形成一个新的空位。

                i->                                    <-j

4.重复步骤2和3，直达前后标志位置i和j相遇,把基准数21放到i和j相遇的位置。

5.把21两边的部分重复上边的排序步骤。

第一趟排序结果{1} 21 {  26 ,22,36，29}

第二趟排序 {1} 21 {      ，22  ,36，29}

                   1，21 { 22 }26 {36，29}

第三趟排序 1，21 ，22 ，26   {      ，29}

                    1，21 ，22 ，26  { 29 ，36}

最终结果：1，21 ，22 ，26  ，29 ，36

四

代码实现？

   

    

     

      

     
     

      

       public class Sort {	
      
     
    

     

      

     
     

      

       public static void main(String[] args) {	
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      

       int array[]={21,36,26,22,18,29};	
      
     
    

     

      

     
     

      

       int start = 0;	
      
     
    

     

      

     
     

      

       int end = array.length - 1;	
      
     
    

     

      

     
     

      

       // 调用sort方法，排序 
      
     
    

     

      

     
     

      

       sort(array, start, end);	
      
     
    

     

      

     
     

      

       // 循环输出排序后的结果，看是否正确 
      
     
    

     

      

     
     

      

       for (int i = 0; i < array.length; i++) {	
      
     
    

     

      

     
     

      

       System.out.print(array[i]+"\t");	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      

       public static void sort(int array[], int low, int high) {	
      
     
    

     

      

     
     

      

       // start是list的第一位，end是list的最后一位，start和end都是数组的下标位置； 
      
     
    

     

      

     
     

      

       int start = low;	
      
     
    

     

      

     
     

      

       int end = high;	
      
     
    

     

      

     
     

      

       // value作为基准值，取未排序的第一位作为基准值 
      
     
    

     

      

     
     

      

       // 算法大体思路，就是拿value和剩下的数比较，排序， 
      
     
    

     

      

     
     

      

       // value值前都比value小，value值后都比value大 
      
     
    

     

      

     
     

      

       int value = array[low];	
      
     
    

     

      

     
     

      
 while (end > start) {	
      
     
    

     

      

     
     

      

       // 从后往前比较，找到小于等于value的值 
      
     
    

     

      

     
     

      

       while (end > start && array[end] >= value) {	
      
     
    

     

      

     
     

      

       end--;	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       if (array[end] <= value) {	
      
     
    

     

      

     
     

      

       // 把找到的数放到前一个空位 
      
     
    

     

      

     
     

      

       int keyStarts = array[start];	
      
     
    

     

      

     
     

      

       array[start]=array[end];	
      
     
    

     

      

     
     

      

       array[end]= keyStarts;	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       // 从前往后比较，找到大于等于value的值 
      
     
    

     

      

     
     

      

       while (end > start && array[start] <= value){	
      
     
    

     

      

     
     

      

       start++;	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       if (array[start] >= value) {	
      
     
    

     

      

     
     

      

       // 同理把找到的数放到前一个空位 
      
     
    

     

      

     
     

      

       int keyStarts = array[start];	
      
     
    

     

      

     
     

      

       array[start]= array[end];	
      
     
    

     

      

     
     

      

       array[end]= keyStarts;	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      
 //左边递归调用 
      
     
    

     

      

     
     

      

       if (start > low){	
      
     
    

     

      

     
     

      

       sort(array, low, start - 1);	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       //右边递归调用 
      
     
    

     

      

     
     

      

       if (end < high){	
      
     
    

     

      

     
     

      

       sort(array, end + 1, high);	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       }	
      
     
    

     

      

     
     

      

       }