数据结构与算法——快速排序

84 阅读 0 评论 56 点赞

我是靠谱客的博主外向蓝天，最近开发中收集的这篇文章主要介绍数据结构与算法——快速排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

每次看大牛的博客都有一种感想：啥时候我也能成为大牛。。。。。插入一个：上两篇文章分别介绍了选择排序和冒泡排序，其思想都差不多，只是选择排序是比较完所有数据后确定最小的数再交换，而冒泡排序是比较相邻的两个数如果顺序不对就要交换：两者的时间复杂度都是o（n2）

下面是我在数组里面存在相同数据的结果：选择排序和冒泡排序的结果

选择排序的结果：
第1次排序结果：1	33	12	45	23	68	33	24	100	88	98	59	
第2次排序结果：1	12	33	45	23	68	33	24	100	88	98	59	
第3次排序结果：1	12	23	45	33	68	33	24	100	88	98	59	
第4次排序结果：1	12	23	24	33	68	33	45	100	88	98	59	
第5次排序结果：1	12	23	24	33	68	33	45	100	88	98	59	
第6次排序结果：1	12	23	24	33	33	68	45	100	88	98	59	
第7次排序结果：1	12	23	24	33	33	45	68	100	88	98	59	
第8次排序结果：1	12	23	24	33	33	45	68	100	88	98	59	
第9次排序结果：1	12	23	24	33	33	45	68	88	100	98	59	
第10次排序结果：1	12	23	24	33	33	45	68	88	98	100	59	
第11次排序结果：1	12	23	24	33	33	45	68	88	98	100	59	
第12次排序结果：1	12	23	24	33	33	45	68	88	98	100	59	
最终排序结果：1	12	23	24	33	33	45	68	88	98	100	59	
冒泡排序的结果：
第1次排序结果：12	23	24	33	33	45	68	88	98	100	59	1	
第2次排序结果：23	24	33	33	45	68	88	98	100	59	12	1	
第3次排序结果：24	33	33	45	68	88	98	100	59	23	12	1	
第4次排序结果：33	33	45	68	88	98	100	59	24	23	12	1	
第5次排序结果：33	45	68	88	98	100	59	33	24	23	12	1	
第6次排序结果：45	68	88	98	100	59	33	33	24	23	12	1	
第7次排序结果：68	88	98	100	59	45	33	33	24	23	12	1	
第8次排序结果：88	98	100	68	59	45	33	33	24	23	12	1	
第9次排序结果：98	100	88	68	59	45	33	33	24	23	12	1	
第10次排序结果：100	98	88	68	59	45	33	33	24	23	12	1	
第11次排序结果：100	98	88	68	59	45	33	33	24	23	12	1	
最终排序结果：100	98	88	68	59	45	33	33	24	23	12	1

快速排序的基本思想：

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。

[html]  
   view plain 
   copy 
    
   
 public int getMiddle(Integer[] list, int low, int high) {  
         int tmp = list[low];    //数组的第一个作为中轴  
         while (low < high) {  
             while (low < high && list[high] > tmp) {  
                 high--;  
             }  
             list[low] = list[high];   //比中轴小的记录移到低端  
             while (low < high && list[low] < tmp) {  
                 low++;  
             }  
             list[high] = list[low];   //比中轴大的记录移到高端  
         }  
         list[low] = tmp;              //中轴记录到尾  
         return low;                   //返回中轴的位置  
     }  

递归形式的分治排序算法：

[html]  
   view plain 
   copy 
    
   
 public void _quickSort(Integer[] list, int low, int high) {  
         if (low < high) {  
             int middle = getMiddle(list, low, high);  //将list数组进行一分为二  
             _quickSort(list, low, middle - 1);        //对低字表进行递归排序  
             _quickSort(list, middle + 1, high);       //对高字表进行递归排序  
         }  
     }  

[html]  
   view plain 
   copy 
    
   
 public void quick(Integer[] str) {  
         if (str.length > 0) {    //查看数组是否为空  
             _quickSort(str, 0, str.length - 1);  
         }  
     }  

编写测试方法：

[html]  
   view plain 
   copy 
    
   
 public class TestMain {  
   
     /**  
      * @param args  
      */  
     public static void main(String[] args) {  
         // TODO Auto-generated method stub  
          Integer[] list={34,3,53,2,23,7,14,10};  
          QuicSort qs=new QuicSort();  
          qs.quick(list);  
          for(int i=0;i<list.length;i++){  
              System.out.print(list[i]+" ");  
          }  
          System.out.println();  
     }  
   
 }  

看一下打印结果吧：

2 3 7 10 14 23 34 53

这样就排序好了，快速排序是对冒泡排序的一种改进，平均时间复杂度是O(nlogn)。

[html]  
    view plain 
    copy 
     
    
 public int getMiddle(Integer[] list, int low, int high) {  
         int tmp = list[low];    //数组的第一个作为中轴  
         while (low < high) {  
             while (low < high && list[high] > tmp) {  
                 high--;  
             }  
             list[low] = list[high];   //比中轴小的记录移到低端  
             while (low < high && list[low] < tmp) {  
                 low++;  
             }  
             list[high] = list[low];   //比中轴大的记录移到高端  
         }  
         list[low] = tmp;              //中轴记录到尾  
         return low;                   //返回中轴的位置  
     }  

递归形式的分治排序算法：

[html]  
    view plain 
    copy 
     
    
 public void _quickSort(Integer[] list, int low, int high) {  
         if (low < high) {  
             int middle = getMiddle(list, low, high);  //将list数组进行一分为二  
             _quickSort(list, low, middle - 1);        //对低字表进行递归排序  
             _quickSort(list, middle + 1, high);       //对高字表进行递归排序  
         }  
     }  

[html]  
    view plain 
    copy 
     
    
 public void quick(Integer[] str) {  
         if (str.length > 0) {    //查看数组是否为空  
             _quickSort(str, 0, str.length - 1);  
         }  
     }  

编写测试方法：

[html]  
    view plain 
    copy 
     
    
 public class TestMain {  
   
     /**  
      * @param args  
      */  
     public static void main(String[] args) {  
         // TODO Auto-generated method stub  
          Integer[] list={34,3,53,2,23,7,14,10};  
          QuicSort qs=new QuicSort();  
          qs.quick(list);  
          for(int i=0;i<list.length;i++){  
              System.out.print(list[i]+" ");  
          }  
          System.out.println();  
     }  
   
 }  