面试题10-快速排序

题目要求

快速排序

题目解析

思路一：

• 分析

首先选择一个枢轴值，和两个下标值分别为low和high。
首先比较是否枢纽值与low下标所代表的值的大小，如果大于，那么检查low+1的值。
如果小于的话将low的值移动至数组右侧。
然后比较是否枢纽值与high下标所代表的值的大小，如果小于，那么检查high-1的值。
如果小于的话将low的值移动至数组左侧。
再分别在分开的两个区间进行快速排序

• 代码段

public static int[] order(int[] data) {
        
        if(data == null || data.length == 0) {
            return null ;
        }
        
        //确定中间值为枢轴值
        int tempId = (data.length - 1 + 0 ) / 2 ;
        int temp = data[(data.length - 1 + 0 ) / 2] ;
        
        int low = 0 ;
        int high = data.length-1 ;
        
        //移动元素完成一波快速排序
        while(low < high) {
            while(low < tempId && data[low] <= temp) {
                low ++ ;}
            data[tempId] = data[low] ;
            tempId = low ;
            low++ ;
            while(tempId < high && data[high] >= temp) {
                high -- ;}
            data[tempId] = data[high] ;
            tempId = high ;
            high-- ;
        }
        
        data[tempId] = temp ;
        
        //处理枢轴左边的数组区间
        if(tempId > 0) {
            int[] leftData = order(Arrays.copyOfRange(data, 0 , tempId)) ;
            
            for(int i = 0 ; i < tempId ; i++ ) {
                data[i] = leftData[i] ;
            }
        }
        //处理枢轴右边的数组区间
        if(tempId+1 < data.length ) {
            int[] rightData = order(Arrays.copyOfRange(data, tempId+1 , data.length)) ;
            
            for(int i = tempId+1 ; i < data.length ; i++) {
                data[i] = rightData[i - (tempId+1)] ;
            }
        }
        
        return data ;
        
    }

测试代码

public static void main(String[] args) {
        
        int[] data = {46,68,12,25,33,80,19,33} ;
        
        data = order(data) ;
        if(data != null)
        for(int i = 0 ; i < data.length ; i++) {
            System.out.print( data[i] + ((i==data.length-1) ? "":",") );
        }
        
    }

运行结果

t排序前
46,68,12,25,33,80,19,33

>>>>>>>>>>>>>>>>>>>>>>>>>>
排序后
12,19,25,33,33,46,68,80

看完整源码戳源码地址