频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
java快速排序实现教程
2017-12-06 10:18:23      个评论    来源:一个被代码耽搁了的法师  
收藏   我要投稿

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序在笔试面试中也是高频考点。

假设我们要对7,4,5,6,1,8,9,3,2这几个数进行排序,我们首先要找一个基准数,为了方便,我们取第一个数7当作基准数,我们要将这些数字中比7小的放在7的左边,比7大的放在7的右边。其实每一趟排序就是要将基准数放在合适的位置。我们先从右边(先从右边是因为基准数选在了最左边)找出第一个比7小的数,再从左边找出第一个比7大的数,交换它们的位置,继续从两头找,直到左右相遇在一个数,就将这个数与基准数交换,至此,一趟排序完成,7的左边全是比它小的,7的右边全是比它大的。然后分别将左边的序列和右边的序列进行递归快速排序。

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。

public static void main(String[] args) {
    System.out.println("请输入数组长度:");
    Scanner in=new Scanner(System.in);
     while(in.hasNext()){
         int m=in.nextInt(); 
         int[] arr=new int[m];
         System.out.println("请输入数组:");
         for(int i=0;iright)
        return;
    temp = arr[left];   //temp中存基准数
    i = left;
    j = right;
    while(i!=j) {
        while(arr[j]>=temp&&i

}

“`

点击复制链接 与好友分享!回本站首页
上一篇:如何将编译后的class文件打成jar包?
下一篇:Java的变量和常量讲解
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站