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

快速排序(java)

发表于: 2012-09-03   作者:128kj   来源:转载   浏览:
摘要: 快速排序是典型的使用分治策略的一种交换排序. 一般步骤: 1)选择一个枢纽元素(关键点); 2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置; 3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。   由于关键点是用来比较的基准所以如果基准选择得当
快速排序是典型的使用分治策略的一种交换排序.
一般步骤:
1)选择一个枢纽元素(关键点);
2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置;
3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
 
由于关键点是用来比较的基准所以如果基准选择得当可以减少交换的次数, 从而提高算法效率 , 是比较有技巧的部分), 以该关键点元素作为基准, 从数组两头分别与之比较, 大的放右边,小的放左边,相等的无论哪边都成(干脆不动). 最后当遍历完数组一遍(即两头的标志指向同一个数组元素)时把关键点元素放到该位置(此时确定这里为分治点 ),完成一次排序.

例如:待排序的数组A的值分别是:(初始关键数据X:=49)
                 A[1]    A[2]    A[3]    A[4]    A[5]     A[6]    A[7]
                  49       38      65      97      76      13       27

进行第一次交换后: 27       38      65      97      76      13       49
进行第二次交换后: 27       38      49      97      76      13       65
进行第三次交换后: 27       38      13      97      76      49       65
进行第四次交换后: 27       38      13      49      76      97       65

经过一躺快速排序之后的结果是:
27       38      13      49      76      97       65
即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

     快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程:

初始状态    {49    38    65    97    76    13    27}  

进行一次快速排序之后划分为   {27    38    13}    49   {76    97    65}

分别对前后两部分进行快速排序后:
  {13}   27   {38}   49  { 65}   76   {97}

public class Quicksort {   
  
    private int getPivot(int begin, int end) {   
  
        return (begin + end) >> 1;   
    }   
  
    // 一次排序   
    private int partition(int[] array, int begin, int end) {   
        int pivot = getPivot(begin, end);   
         // int pivot=0; 也可以
        int tmp = array[pivot];   
        array[pivot] = array[end];   
        while (begin != end) {   
            while (array[begin] < tmp && begin < end)   
                begin++;   
            if (begin < end) {   
                array[end] = array[begin];   
                end--;   
            }   
            while (array[end] > tmp && end > begin)   
                end--;   
            if (end > begin) {   
                array[begin] = array[end];   
                begin++;   
            }   
        }   
        // 此时两个下标指向同一个元素.以这个位置左右分治(分治点)   
        array[begin] = tmp;   
        return begin;   
    }   
  
    private void qsort(int[] array, int begin, int end) {   
  
        if (end - begin < 1)   
            return;   
        int pivot = partition(array, begin, end);   
        qsort(array, begin, pivot);   
        qsort(array, pivot + 1, end);   
    }   
  
    public void sort(int[] array) {   
        qsort(array, 0, array.length - 1);   
    }   
  
    public static void main(String[] args) {   
       int[] array = { 3, 2, 2, 2, 3, 1, 4, 5, 1 };   
       // int[] array={49,38,65,97,76,13,27};
        new Quicksort().sort(array); 
        //new Quicksort().partition(array,0,6);   
        for (int i = 0; i < array.length; i++) {   
            System.out.print(array[i] + ", ");   
        }   
    }   
}  


下载源码:


                                                

快速排序(java)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
快速排序 作者:Legend QQ:158067568 快排是分治法的一个应用,快排主要是通过一个设定枢轴,然后
1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成
一、算法介绍: 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n l
快速排序的基本思想: 通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另
java实现快速排序(转) 说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都
思想: 采用分治策略。 每次排序会使一个元素落在最终位置,并且该元素之前的数据都比不比它大,之
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号