【面试】常遇手写算法（一）快速排序

喜欢ヅ旅行 2022-09-04 00:51 161阅读 0赞

面试遇到十几次让手写快速排序！！！！

## 快速排序完整代码如下： ##

public class QuckSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        32,1,1,51,221,7,12,3,8,9,88,12,888};
            quckSort(arr,0,arr.length-1);
        }
    
       public static void  quckSort(int arr[],int low,int high){
        
            if (low<high){
        
                int index = getIndex(arr,low,high);
                quckSort(arr,low,index-1);
                quckSort(arr,index+1,high);
            }
        }
    
       public static int  getIndex(int arr[],int low,int high){
        
            int temp = arr[low];
            while (low <high){
        
                while (low <high&&arr[high]>=temp){
        
                    high--;
                }
                arr[low] = arr[high];
                while (low <high&&arr[low]<=temp){
        
                    low ++;
                }
                arr[high] = arr[low];
            }
            arr[low]=temp;
            return low;
        }
    }

基本逻辑：  
1、取初值：low=0、high=arr.length-1、temp=arr\[0\];  
2、从数组后末尾开始比较：

1.  当low<high且arr\[high\]>=temp时；high–,直到arr\[high\]<temp时，将arr\[low\]=arr\[high\],比较方向转换到低位；
2.  当low<high且arr\[low\]<=temp时；low++,直到arr\[low\]>temp时，将arr\[high\]=arr\[low\],比较方向转换到高位；
3.  当low == high时此轮结束，将temp值放入arr\[low\]并且返回low的值；
4.  使用递归方法重复调用，直到所有的low==high，结束计算；  
    易错点：  
    1、temp 取值 为 arr \[low\]。  
    2、while (low <high&&arr\[low\]<=temp) 容易少写=号。  
    3、每一轮结束需要将temp值放入数组位置 ：arr\[low\] = temp。  
    4、递归的参数设置容易出错。

quckSort(arr,low,index-1);
     quckSort(arr,index+1,high);==》错误设置为；quckSort(arr,index,high);

## 一般会接着问你的算法复杂度是多少？ ##