欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每日一提:三分钟理解的快速排序

程序员文章站 2022-04-02 11:46:31
...

简单原理

  1. 快速排序是给定一个基准值然后进行比较小于他和大于他的数,
  2. 小于他的数放左边,大于他的放右边
  3. 然后再以他的左边为整体,再选出一个基准值,然后重复①②直到左边为一个数就不用排序了,右边也如此
  4. 为了不纠结基准值,默认就选择第一个,
  5. 两个指针作为辅助,一个left,一个right,最左和最右,交替比较(如果left小就移动指针继续判断left,right大就移动right)
  6. 但是如果left大于temp就arr[right]=arr[left],然后right减一位,判断right指针方便等会去覆盖left的值,交替比较

每日一提:三分钟理解的快速排序

代码实现:

QuickSort.java

public class QuickSort {
 public int[] qsort(int arr[],int start,int end) {        
     int pivot = arr[start];        
     int i = start;        
     int j = end;        
     while (i<j) {            
         while ((i<j)&&(arr[j]>pivot)) {                
             j--;            
         }            
         while ((i<j)&&(arr[i]<pivot)) {                
             i++;            
         }            
         if ((arr[i]==arr[j])&&(i<j)) {                
             i++;            
         } else {                
             int temp = arr[i];                
             arr[i] = arr[j];                
             arr[j] = temp;            
         }        
     }        
     if (i-1>start) arr=qsort(arr,start,i-1);        
     if (j+1<end) arr=qsort(arr,j+1,end);        
     return (arr);    
 }    
}

Test.java

public class Test {
 public static void main(String[] args) {
  // TODO 自动生成的方法存根
            QuickSort quick=new QuickSort();
      int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        
      int len = arr.length-1;        
      arr=quick.qsort(arr,0,len);        
      for (int i:arr) {            
          System.out.print(i+"\t");    
      }      
 }
}
//输出结果3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344 

进大厂必熟背

每日一提:三分钟理解的快速排序

上图可知快速排序并不是最优排序,但能用于有基准值排序的场景,不稳定,
O(1), O(n), O(logn), O(nlogn) 的区别-》https://blog.csdn.net/ted_cs/article/details/82881831

相关标签: 十大排序算法