A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© guhaibin 中级黑马   /  2014-2-5 20:13  /  1626 人查看  /  6 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 guhaibin 于 2014-2-10 22:17 编辑

数组的排序有:冒泡,选择,插入,快速排序。。。。想请问大家是如何理解快速排序的。原理是什么。

评分

参与人数 1技术分 +1 收起 理由
黄晓东 + 1

查看全部评分

6 个回复

倒序浏览
本帖最后由 乐宝myhoney 于 2014-2-5 21:38 编辑

1.快速排序的基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两    部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
2.效率最高的排序是希尔排序,其基本思想是:先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。3.希尔排序的具体实现:
public class Demo {
        public static void main(String[] args) {
                ShellSort shellSort = new ShellSort() ;
                System.out.println("希尔排序已经完成");
        }
}
/*
* 希尔排序的实现
*/
class ShellSort {
        //shellSort构造函数
        public ShellSort() {
                //定义一个整型数组,里面有十个整数
                int arr[] = { 1, 26, 9, 66, 77, 274, 123, 82, 13, 58 };
                /* 定义一个双精度型的变量d1,用来存放数组的长度,为什么是双精度型的呢,因为后面我要用这个d1,这个d1是在不断地变化,
                 * 而且是在不断的变化,第一次是这个数组的长度除以2娶向上的整数。然后以此类推,每次都是除以2。其实这个d1就是前面所提
                 * 到的增量。数组根据这个增量分成好几个组。
                 */
                 double d1 = arr.length;
                 //定一个整型的临时变量,用来存放两个数中临时比较的数。
                 int temp = 0;
                 while (true) {
                     //定义一个增量,增量向上取整,而且这个增量每次都在变化。这个就是上面的d1,这就是为什么d1必须要取double的原因。
                     d1 = Math.ceil(d1 / 2);   
                     // 然后把这个d1强制转换成int类型。用于底下的和整型的数相加,否则会出现类型转换不一致问题。
                     int d = (int) d1;   
                     //这一层循环是把当前这个增量里面的每一组数据比较一边
                     for (int x = 0; x < d; x++) {
                         //这一层循环式比较已经确定了的那几个数   ,比如以d等于2,那么这里比较的数据就是第一个和第三个还有第五个,一次类推
                         for (int i = x + d; i < arr.length; i += d) {  
                         //让j等于每一组里面的第一个数
                                int j = i - d;
                                //当前要比较的数的后面一个数放到临时变量里面                           
                                temp = arr[j]
;   
                                //比较当前的数和后面的数                     
                                for (; j >= 0 && temp < arr[j]; j -= d) {   
                                   //如果后面的数小于前面的数,则把它们交换
                                   arr[j + d] = arr[j];
                                }
                                arr[j + d] = temp;
                     }
            }
            if (d == 1)//如果最后增量变为1就结束了,因为1就是只有相邻的两个比,这两个都已经是排好序的了,所以就不用比了,说明排序好了
            break;
            }
            //打印出这个已经排好序的数组。
            System.out.print(“[”);

            for (int i = 0; i < arr.length; i++)
            {
               if(i!=arr.length-1)
                  System.out.print(arr
+",");
               else
                 System.out.println(arr
+"]");
            }
     }
}



评分

参与人数 1技术分 +1 收起 理由
黄晓东 + 1

查看全部评分

回复 使用道具 举报
最后打印排序好的那段代码,不知道为什么显示不出来,其实是arr[i],对不住了啊,请注意一下!
回复 使用道具 举报
乐宝myhoney 发表于 2014-2-5 21:39
最后打印排序好的那段代码,不知道为什么显示不出来,其实是arr,对不住了啊,请注意一下! ...

谢谢,辛苦了,快速排序能不能也举例下
回复 使用道具 举报
本帖最后由 杨殿生 于 2014-2-8 22:17 编辑

举个例子30  3    45    6    67    87    8    98    9     45
以第一个数为基准小于30的在左面大于30的在右面实现方法是




评分

参与人数 1技术分 +1 收起 理由
黄晓东 + 1

查看全部评分

回复 使用道具 举报
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]赋给A[i];
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]赋给A[j];
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
回复 使用道具 举报
谢谢各位的帮助
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马