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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 小爷邱烙 高级黑马   /  2014-11-6 00:02  /  1729 人查看  /  13 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 小爷邱烙 于 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.         }
复制代码





评分

参与人数 2技术分 +2 黑马币 +10 收起 理由
郑飞 + 10 正好这两天在看排序 学习了
杨佳名 + 2 赞一个!

查看全部评分

13 个回复

倒序浏览
好吧,看来任何想排版好看点的行为都是徒劳的,大家凑合看吧
回复 使用道具 举报
小爷邱烙 发表于 2014-11-6 00:10
好吧,看来任何想排版好看点的行为都是徒劳的,大家凑合看吧

总结的很好啊

ps:我也受不了黑马论坛的编辑器,尤其是代码插入,没缩进没高亮,你这已经不错了,32个赞
回复 使用道具 举报
楼主 希尔最后间隔步长排序 理论上是可以使用任何排序方法吧? 那会不会有人递归希尔呢?
回复 使用道具 举报
很详细,32个赞!
回复 使用道具 举报
郑飞 发表于 2014-11-6 09:24
楼主 希尔最后间隔步长排序 理论上是可以使用任何排序方法吧? 那会不会有人递归希尔呢?  ...

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

嗯 这个帖子很适合刚接触排序的朋友 思路简单 代码清晰 入门的好帖子 学习了 :handshake
回复 使用道具 举报
郑飞 发表于 2014-11-6 10:20
嗯 这个帖子很适合刚接触排序的朋友 思路简单 代码清晰 入门的好帖子 学习了  ...

说句题外话,我能说,你是我眼中的大神么,当我刚注册论坛,还是个菜鸟的时候,就是看着你的帖子成长起来的
回复 使用道具 举报
郑飞 高级黑马 2014-11-6 10:55:45
9#
本帖最后由 郑飞 于 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 10:23
说句题外话,我能说,你是我眼中的大神么,当我刚注册论坛,还是个菜鸟的时候,就是看着你的帖子成长起来 ...

呵呵 回你的题外话: 说起来惭愧 这么久了都没混进黑马 :L 大神 真的是抬举了
回复 使用道具 举报
很详细的总结 学习
回复 使用道具 举报
郑飞 发表于 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 12:15
我想了一下,按你的写法,第一个步长的循环没有变化,最后一个步长为1的时候也没有变化,但是当步长在中 ...

嗯 是我想多了  后面就是一个插入排序而已:L
回复 使用道具 举报
他是你眼中的大神,你就是我眼中的大神! 我刚学到第10天,以为自己每天研究的很透彻了,看了你得帖子,觉得自愧不如,  朋友 我要赶上你 !
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马