首页 > itarticle > 快速排序

快速排序

admin 1月 23, 2021 0

1、快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2、时间复杂度

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)　

3、动态演示

4、算法实现

package sort;

public class  {

   public static void main(String[] args) {
     
     int [] a= {1,2,7,4,3,2};
        quickSort(a,0,a.length-1);
       printArr(a);
 }
    
 public static void quickSort(int [] a,int left,int right) {
       if(left>right) {
         return;
     }
        
     int key=a[left];
        
     int low=left;
       int high=right;
     
     while(low!=high) {
          //从右往左找
         while(a[high]>key && low<high) {
              high=high-1;
         }   
         
         //从左往右找
         while(a[low]<key && low<high) {
               low=low+1;
           }
            
         //如果low和high没有相遇，则交换
            if(low<high) {
               int temp=a[low];
                a[low]=a[high];
              a[high]=temp;
            }   
     }
        
     //key值归位
        a[left]=a[low];
      a[low]=key;
      
     //递归调用子数组
       quickSort(a,left,low-1);
     quickSort(a,low+1,right);
    }
    
 public static void printArr(int [] a) {
     for(int i=0;i<a.length;i++) {
           System.out.println(a[i]);
        }
    }

}