Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1148654
  • 博文数量: 103
  • 博客积分: 1897
  • 博客等级: 上尉
  • 技术积分: 1717
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-19 21:02
文章分类

全部博文(103)

文章存档

2013年(19)

2012年(84)

分类: Java

2012-05-03 17:47:52

   最近在整理以前学过的一些算法,下面就来介绍 一个搞的我最近头都有点大的算法--江湖人称“快速排序”
其实快速排序的原理还是比较简单的,但是,真正编码实现起来,还是有一定难度的。
  快速排序就是在待排序的元素中挑取一个作为分区的一个标准,让元素左边的数值都小于该元素,元素右边的则相反,然后分别对两边的分区进行同样的分区操作,最后达到让元素达到有序的状态。
  下面贴一下我写的代码:
package lwq.com;
//快排算法的实现
public class QuickSort{

   
    public static void quickSort(int[] num,int low,int high){
        int l = low;
        int h = high;
        int mid = (l+h)/2;
        int x =num[mid]; //设置分区的值
        while(l<=h){
            while((l                l++;
            while((h>low)&&(num[h]>x))
                h--;
            if(l<=h){ //等于号是说可能是奇数个时,也以将区间分开
// 交换两边的元素
                int tmp = num[l];
                num[l] = num[h];
                num[h] = tmp;
                l++;
                h--;
            }
           
        }
//继续分区
        if(l            quickSort(num,l,high);
        if(h>low)
            quickSort(num,low,h);
    }
   

   
    public  static void main(String args[]){
        int[] num = {1,34,3,3,4};
       
        quickSort(num,0,num.length-1);
        for(int n:num)
            System.out.println(n);
    }
}

每次分区的时候,我都会以元组的中值作为排序的中心元素,再依次对两边的元素进行递归操作,这个算法实现看起来不难,但是,其实,里面的很多临界条件都是需要自己慢慢琢磨的,一不小心就会出错,我下午就是把一个小于号写成小于等于,结果死活都不对。。,郁闷了好久。。

顺便说一下,这个快排是不稳定的排序算法,所谓的稳定的算法就是说两个相同的元素在排列前后的相对位置不变,比如5,6,5,3,4,排序之后,两个五的先后顺序是不变的,那么该排序算法就是稳定的排序算法。快排的时间复杂度最坏是o(n2),但是最好是nlogn,相对冒泡,选择来说,还是不错的排序算法。。


阅读(1891) | 评论(3) | 转发(3) |
给主人留下些什么吧!~~

-小Y头-2012-05-06 11:19:15

呵呵,新人前来报道~~最近刚刚在学各种排序

thomaslwq2012-05-05 00:45:24

147189385: 快速排序是不稳定的算法 吧?.....
是的,快排不是稳定的排序算法来的。。不过快排还是比较好用的。。

1471893852012-05-04 22:17:37

快速排序是不稳定的算法 吧?