黑马程序员技术交流社区

标题: 简单的排序问题 [打印本页]
作者: 余明辉    时间: 2012-6-28 23:58
标题: 简单的排序问题
本帖最后由 刘蕴学 于 2012-7-1 15:43 编辑

2个排序，1个快速排序，1个冒泡排序，我怎么感觉2种排序方法都差不多，只是一个从前向后遍历，一个从后向前遍历而已。为什么还要区分个名字？下面是源码
//快速排序
int a[] = {1, 2, 5, 7, 4, 3, 6, 9, 8};
                int temp;
                for(int i=0; i<a.length; i++) {
                        for(int j=i+1; j<a.length; j++) {
                                if(a[j]<a) {
                                        temp = a[j];
                                        a[j] = a;
                                        a = temp;
                                }
                        }
                }
                for(int i:a) {
                        System.out.print(i + " ");
                }
//冒泡排序
int a[] = {1, 2, 5, 7, 4, 3, 6, 9, 8};
                int temp;
                for(int i=0; i<a.length; i++) {
                        for(int j=a.length-1; j>i; j--) {
                                if(a[j]<a) {
                                        temp = a[j];
                                        a[j] = a;
                                        a = temp;
                                }
                        }
                }
                for(int i:a) {
                        System.out.print(i + " ");
                }
作者: 常佳杰    时间: 2012-6-29 00:07
冒泡排序是数组中相邻两个元素的比较，取其中大值或小值...
快速排序是数组中第一个元素和后边的每个元素比一遍取最大或最小值..再用第二元素和后边的每个元素比一遍取最大或最小值..
//快速排序
int a[] = {1, 2, 5, 7, 4, 3, 6, 9, 8};
                int temp;
                for(int i=0; i<a.length; i++) {
                        for(int j=i+1; j<a.length; j++) {
                                if(a[j]<a) {//这儿体现了第一个元素和后边的每个元素比一遍..第二元素和后边的每个元素比一遍..
                                        temp = a[j];
                                        a[j] = a;
                                        a = temp;
                                }
                        }
                }
                for(int i:a) {
                        System.out.print(i + " ");
                }
//冒泡排序
int a[] = {1, 2, 5, 7, 4, 3, 6, 9, 8};
                int temp;
                for(int i=0; i<a.length; i++) {
                        for(int j=a.length-1; j>i; j--) {
                                if(a[j]<a) {//相邻两个元素的比较
                                        temp = a[j];
                                        a[j] = a;
                                        a = temp;
                                }
                        }
                }
                for(int i:a) {
                        System.out.print(i + " ");
                }
作者: 常佳杰    时间: 2012-6-29 00:08
这字体怎么回事？ 看着都晕...
作者: 周刚    时间: 2012-6-29 00:14
      LZ你说的”快速排序“不对，快速排序是比较高级的排序算法，实现起来的代码也决非是上面写那的那么简单。大致原理是：先从数据序列中选一个元素,
并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1。快速排序的时间复杂度的
平均时间复杂度为O(nlogn)，而冒泡排序的时间复杂度为O(n^2)。你可以参考数据结构查找、排序部分的内容。
作者: 周刚    时间: 2012-6-29 00:23
可能你说的快速排序是指这个简单选择排序，简单选择择排序例是和冒泡排序是同一个等级的，
代码实现起来也比较简单，时间复杂度都为O(n^2)。
思路是设置一个临时变量，存储最小值。
首先在1到n个数中，使用for循环依次比较把较小的数的下标赋值给k，直到最小的下标被确定，
便与第一个数交换位置。接着i++，便在第二个数开始的数列中选择最小的与第二个数交换，依次类推，
直到i++跳出循环便比较完毕。
作者: 邵阳    时间: 2012-6-29 06:56
我也补充一下，那个确实不叫快速排序，怎么没人给楼主说那个叫选择排序啊。所以要分清哪个是真么排序，要不闹笑话。

另外说一下选择排序和冒泡排序的大致区别吧，快速排序咱没学习就不写啦
选择排序主要是每一个元素要和其他元素都要比较，判断最大最小值然后互换位置。但是这个是思想，如果转换成代码，就如楼上朋友说的
选择排序是数组中第一个元素和后边的每个元素比一遍取最大或最小值..再用第二元素和后边的每个元素比一遍取最大或最小值..但是朋友说的比较浅。我说一下三点注意。
1：按思想来说只要每一元素和其他元素比较都行，所以对于首先对比的元素的位置选择都可以，意思就是我拿第二个或第三个元素和其他元素比较，从而比较出最大值或最小值放在一边，依次进行便得出排序后的数组。但是以我目前的基础没有办法变成代码的形式，但是肯定有。当然不用这种办法主要还是因为效率太低。
2：不一定要从第一个元素往后依次比较，也可以从后往前依次比较。这两种方式的效率是相同的。但重点是按顺序依次
3：还有就是可以提高效率的两个小地方。
（1）是拿某个元素和别的元素都比后，在该元素原来在数组中的位置的元素不用再和其他元素比较，因为这个已经是最大最小值了
（2）当遍历到最后或第一个元素时，就不用拿这个元素和其他元素比较了。
冒泡排序时冒泡排序是数组中相邻两个元素的比较，取其中大值或小值...
其注意事项同上吧

码字不容易，原创更不容易啊，支持原创，打击盗版
作者: 孙飞    时间: 2012-6-29 08:33
本帖最后由 feigecal 于 2012-6-29 08:49 编辑

你的第一种是选择排序，它是一个从前向后的遍历，外循环从0角标开始控制循环次数，内循环从外循环的角标加1开始，即每一次都拿外循环的开始角标位与它后面的数也就是内循环中的灵敏都比较一下，按你写的是把比较后小值放在左边，从0角标开始。如图

第二种是冒泡排序，和第一种是不一样的，冒泡排序是第一次都从0角标开始依次和相邻角标位的值进行比较，把大值向右传，外循环控制内循环的次数，内循环的每一次执行都有一个当次循环最大的值跑到当次循环的最大角标位上，而下次内循环就不用再参与比较以节省运算。但是你写的第二种不是冒泡排序，只是一个从后向前的遍历正确的应该这样写：
public static void bubbleSort(int[] arr)
        {
                for(int x=0; x<arr.length-1; x++)
                {                                                                        
                        for(int y=0; y<arr.length-x-1; y++)//-x是让每一次比较的元素减少，-1是因为下面和arr[y+1]比较避免角标越界。
                        {
                                if(arr[y]>arr[y+1])
                                {
                                        int temp = arr[y+1];
                                        arr[y+1] = arr[y];
                                        arr[y] = temp;
                                }
                        }
                }
        }


作者: 余明辉    时间: 2012-7-1 00:08
谢谢各位，我已经懂了。
不过这个帖要怎么设成已解决呢？



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