黑马程序员技术交流社区

标题: 排序算法问题 [打印本页]

---

作者: guhaibin    时间: 2014-2-5 20:13
标题: 排序算法问题


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

---

作者: 乐宝myhoney    时间: 2014-2-5 21:10


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+"]");
            }
     }
}

---

作者: 乐宝myhoney    时间: 2014-2-5 21:39
最后打印排序好的那段代码，不知道为什么显示不出来，其实是arr[i],对不住了啊，请注意一下！

---

作者: guhaibin    时间: 2014-2-5 22:32

乐宝myhoney 发表于 2014-2-5 21:39
最后打印排序好的那段代码，不知道为什么显示不出来，其实是arr,对不住了啊，请注意一下！ ...

谢谢，辛苦了，快速排序能不能也举例下

---

作者: 杨殿生    时间: 2014-2-8 22:16


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

---

作者: 张志明    时间: 2014-2-9 23:49
一趟快速排序的算法是：
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-完成的时候，此时令循环结束）。

---

作者: guhaibin    时间: 2014-2-10 22:16
谢谢各位的帮助

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2