高级排序:快速排序 博客分类： Sort

    public void quickSort(int[] array){
        this.quickSort(array, 0, array.length - 1);
    }
    
    public void quickSort(int[] array,int left,int right){
        if(right - left <= 0){
           return;
        }else{
            int partition = this.partition(array, left, right);
            
            this.quickSort(array, left, partition - 1);
            this.quickSort(array, partition + 1, right);
        }
    }

    private int partition(int[] array,int left,int right){
        int leftScan = left;
        int rightScan = right - 1;
        int middle = left + (right - left)/2;
        
        if(array[middle] < array[right] && array[middle] > array[left]){
            this.swap(array, right, middle);
        }else if(array[left] < array[right] && array[left] > array[middle]){
            this.swap(array, right, left);
        }
        
        int pivot = array[right];
        
        while(true){
            for(;leftScan <= right - 1;leftScan++){
                if(array[leftScan] > pivot)break;
            }
            
            for(;rightScan >= left;rightScan--){
                if(array[rightScan] < pivot)break;
            }
            
            if(leftScan >= rightScan){
                break;
            }else{
                this.swap(array, leftScan, rightScan);
            }
        }
        this.swap(array, leftScan, right);
        
        return leftScan;
    }
    
    private void swap(int[] array,int index1,int index2){
        int temp = array[index2];
        array[index2] = array[index1];
        array[index1] = temp;
    }

效率:
快速排序是对冒泡排序的改进,基本思想是选取一个支点,使支点左边全部小于支点,右边全部大于支点.如果支点选择不当,会造成排序极度缓慢(时间复杂度变成O(N^2)),比如选取最后边为支点而数组是逆序的.所以一般采用比较最右端,最左端和中间的元素,选择中间大小的作为支点.时间复杂度为:O(N*logN)