黑马程序员技术交流社区

标题: [邱烙考黑马]关于排序算法扩展 [打印本页]
作者: 小爷邱烙    时间: 2014-11-6 00:02
标题: [邱烙考黑马]关于排序算法扩展
本帖最后由 小爷邱烙 于 2014-11-6 00:07 编辑

最近看完数组排序，查些资料对排序进行了一点总结
1、排序的分类
           排序
                |------内部排序（只使用内存排序）
                                   |------插入排序
                                                  |------直接插入排序
                                                  |------希尔排序
                                  |------选择排序
                                                  |------简单选择排序
                                                  |------堆排序
                                  |------交换排序
                                                  |------冒泡排序
                                                  |------快速排序
                                 |------归并排序
                                 |------基数排序
                |------外部排序（使用内存和外存结合，大数据量，内存存储不下的情况，太高端，不研究）
2、常见的java排序算法主要就是四种：快速排序，简单选择排序，冒泡排序，插入排序
     毕老师的视频里已经详细讲解了简单选择排序和冒泡排序，这里主要说一下快速排序，插入排序，顺便提一下毕老师提到的希尔排序
3、提到排序，一定会说效率，这里简单说一下常见排序的效率比较
            *正常情况：数组中数据随机，数据大小分布平均（可以理解为数组中的每一个元素都是通过随机数产生的）
            *最好情况：数组元素按照由小到大的顺序排列（顺序）
            *最坏情况：数组中的元素按照从大到小的顺序排列（逆序）
       冒泡排序三种情况下都是所有排序中效率最低的（所以只适合当成一种算法来研究）
       最好情况下：选择排序跟冒泡一样慢，其他排序效率都很快（选择排序三种情况下也很慢，也不适合使用）
       正常情况下和最坏情况下：选择和插入排序较慢，快速和希尔排序较快
4、快速排序
         快速排序是最常用的排序，Arrays.sort();方法底层用的就是快速排序。
         其思想是取数组中的任意一个元素（一般是第一个元素）作为基准，遍历数组，将小于基准的元素放在基准元素左边，大于基准的元素放在基准元素         的右边，此时基准元素已经处于正确的位置。将基准左边的元素看作一个新的数组，将基准右边的元素看作一个新的数组，通过递归，重复上边的操
         作，直到每个元素都处于正确的位置。
         代码实现
         
  1. public class FastSort {
  2.         public static void fastSort(int[] arr,int min,int max){
  3.                 if(min<max){
  4.                         int mid = getMiddle(arr, min, max);
  5.                         fastSort(arr, min, mid-1);
  6.                         fastSort(arr, mid+1, max);
  7.                 }
  8.         }
  9.         public static int getMiddle(int[] arr,int min,int max){
  10.                 int temp = arr[min];
  11.                 while(min<max){
  12.                         while(min<max&&arr[max]>=temp){
  13.                                 max--;
  14.                         }
  15.                         arr[min] = arr[max];
  16.                         while(min<max&&arr[min]<=temp){
  17.                                 min++;
  18.                         }
  19.                         arr[max] = arr[min];
  20.                 }
  21.                 arr[min] = temp;
  22.                 return min;
  23.         }
  24. }
复制代码
5、插入排序
         遍历数组依次取出每个元素，当取出第N个元素时，假设前面N-1个元素已经排好顺序，将第N个元素按照从小到大的规则，插入到前面的序列中
         插入排序比较好理解，代码实现：
         
  1. public static void insertSort(int[] arr){               
  2.                 for(int i=0;i<arr.length;i++){
  3.                         for(int j=i;j>0;j--){
  4.                                 if(arr[j]<arr[j-1]){
  5.                                         int temp = arr[j];
  6.                                         arr[j] = arr[j-1];
  7.                                         arr[j-1] = temp;
  8.                                 }else
  9.                                         break;
  10.                         }
  11.                 }
  12.         }
复制代码
6、希尔排序
           希尔排序是插入排序的一种改进，其底层使用的还是插入排序的方法，只不过把数组按照一定的规则，由大到小，分成不同的区域，再依次使用插入排           序，由于插入排序在处理小数据量的时候效率明显，希尔排序能有效提高速度，了解一下就行
           代码实现：
         
  1. public static void shellSort(int[] arr){
  2.                 for(int i=arr.length/2;i>0;i/=2){
  3.                         for(int j=i;j<arr.length;j++){
  4.                                 for(int k=j;k>=i;k-=i){
  5.                                         if(arr[k-i]>arr[k]){
  6.                                                 int temp = arr[k];
  7.                                                 arr[k] = arr[k-i];
  8.                                                 arr[k-i] = temp;
  9.                                         }
  10.                                 }
  11.                         }
  12.                 }
  13.         }
复制代码





作者: 小爷邱烙    时间: 2014-11-6 00:10
好吧，看来任何想排版好看点的行为都是徒劳的，大家凑合看吧
作者: jacoblx    时间: 2014-11-6 04:49
小爷邱烙 发表于 2014-11-6 00:10
好吧，看来任何想排版好看点的行为都是徒劳的，大家凑合看吧

总结的很好啊

ps：我也受不了黑马论坛的编辑器，尤其是代码插入，没缩进没高亮，你这已经不错了，32个赞
作者: 郑飞    时间: 2014-11-6 09:24
楼主 希尔最后间隔步长排序 理论上是可以使用任何排序方法吧? 那会不会有人递归希尔呢?
作者: huoxy    时间: 2014-11-6 09:44
很详细，32个赞！
作者: 小爷邱烙    时间: 2014-11-6 09:50
郑飞 发表于 2014-11-6 09:24
楼主 希尔最后间隔步长排序 理论上是可以使用任何排序方法吧? 那会不会有人递归希尔呢?  ...

我的理解是，希尔排序的出现就是为了改进插入排序，因为插入排序有两个优点，第一是小数组排序快，第二是最好情况，也就是正序情况下排序快
（Arrays.sort();当数组长度小于7的时候，用的是插入排序）
希尔排序正是利用这两个优点，将大数组隔步分成小数组，而最后一次步长为1时，排序情况已经很好了。
快速排序和冒泡排序没法用步长分割。而选择排序，正序时恰恰是排序最慢的情况。
作者: 郑飞    时间: 2014-11-6 10:20
小爷邱烙 发表于 2014-11-6 09:50
我的理解是，希尔排序的出现就是为了改进插入排序，因为插入排序有两个优点，第一是小数组排序快，第二是 ...

嗯 这个帖子很适合刚接触排序的朋友 思路简单 代码清晰 入门的好帖子 学习了 :handshake
作者: 小爷邱烙    时间: 2014-11-6 10:23
郑飞 发表于 2014-11-6 10:20
嗯 这个帖子很适合刚接触排序的朋友 思路简单 代码清晰 入门的好帖子 学习了  ...

说句题外话，我能说，你是我眼中的大神么，当我刚注册论坛，还是个菜鸟的时候，就是看着你的帖子成长起来的
作者: 郑飞    时间: 2014-11-6 10:55
本帖最后由 郑飞 于 2014-11-6 13:11 编辑

希尔的第二层循环 好像只要循环最后一个步长就可以了 我改了下代码
for(int j = arr.length/i*(i-1)+arr.length%i ; j<arr.length;j++)
比如 1-10-20-30-37 那么只要循环 28-37这10个数为最后一个元素的数组
不是钻牛角尖哈 只是我在看的时候看了好久 看不懂为什么要全部循环 所以按自己想法改了下 应该是对的吧 ?
====================
注:以上内容经过验证 是有问题的 大家不要借鉴;P


作者: 郑飞    时间: 2014-11-6 11:28
小爷邱烙 发表于 2014-11-6 10:23
说句题外话，我能说，你是我眼中的大神么，当我刚注册论坛，还是个菜鸟的时候，就是看着你的帖子成长起来 ...

呵呵 回你的题外话: 说起来惭愧 这么久了都没混进黑马 :L 大神 真的是抬举了
作者: dong53821713    时间: 2014-11-6 11:43
很详细的总结 学习
作者: 小爷邱烙    时间: 2014-11-6 12:15
郑飞 发表于 2014-11-6 10:55
希尔的第二层循环 好像只要循环最后一个步长就可以了 我改了下代码
for(int j = arr.length/i*(i-1)+arr.le ...

我想了一下，按你的写法，第一个步长的循环没有变化，最后一个步长为1的时候也没有变化，但是当步长在中间的时候，循环的是一部分元素，而不是整个数组，不能达到尽量将数组转为正序的结果吧
你想，数组长度为8，步长为2的时候，循环的是4-7的情况。虽然最后步长为1的时候全排序了，但是0-4的优化就没有做到，数据量大的时候起不到加速的作用。
作者: 郑飞    时间: 2014-11-6 13:09
小爷邱烙 发表于 2014-11-6 12:15
我想了一下，按你的写法，第一个步长的循环没有变化，最后一个步长为1的时候也没有变化，但是当步长在中 ...

嗯 是我想多了  后面就是一个插入排序而已:L
作者: 奋斗的蜗牛ksd    时间: 2014-11-13 19:49
他是你眼中的大神，你就是我眼中的大神！ 我刚学到第10天，以为自己每天研究的很透彻了，看了你得帖子，觉得自愧不如，  朋友 我要赶上你 ！



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