当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

高级排序:快速排序

发表于: 2012-02-13   作者:dieslrae   来源:转载   浏览:
摘要: 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
    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)

高级排序:快速排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一、快速排序描述: 快速排序的基本思想是:将最右端的元素作为枢纽,然后将所有元素划分为两组,然
排序规则 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放
C 快速排序 快速排序描述 1.从数列中挑出一个元素,称为 "基准"(pivot) 2<span style
快速排序(QuickSort) 1、算法思想  快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用
快速排序和归并排序都是采用了分治法的策略 分治法是将大的问题逐渐分解成单位元素的问题,然后再从
4.快速排序 在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无
快速排序是一个速度非常快的交换排序方式,他的实现思路就是选取一个元素作为分界值,将数组小于分界
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后
(一) 简介: 快速排序是一种基于分治思想的算法, 分治,顾名思义,就是划整为零,将大问题化分成一
算法思想 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一次扫描,将待排序列分成两
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号