5种基本排序 娱乐版开脑解析

假设有那么一群富豪，需要将他们的资产排名。（从少到多）

以下9个想法，分别代表一种排序逻辑。

想法1:

最普通的的想法是除了富豪们之外，有个助理一趟一趟的找，每趟找最富的，出列。----直接选择排序

想法2： 想法1改进一点点

想法1中，每趟找的时候，你都得做比较，这个避免不了，但是你不能白比较啊，比较了的话你可以让比较的俩人交换位置，这样起码部分人已经排好序了，进一步就可以整个标志，记录你这趟比较是否交换位置，如果没交换说明已经排好了，这算是一定程度上利用了你做比较，防止浪费精力啊。----冒泡排序。

想法3:

还有一个很正常的想法是，不用助理，就让富豪们中间的一个人（假如排在第一个的），喊一声谁的钱少于1000万的站在我的左边，大于1000万的站在我右边。（这个富豪就是有1000万），排好后，这个人就不动了，两边的人再分别找第一个人喊，直到排玩。---快速排序

想法4：

你也可以这样，先让第一个出列，再让第二个出列，肯定先和第一个出列的比较下看排在哪，接着让第三个出列，再先和当前排第二的比，比他钱多的话，就站他后面否则跟第一个比较。依次类推。---直接插入排序

想法5：想法4再改进一点点

想法4中有的时候还可以更快点，就是利用有序数列的特点进行二分查找。假如已经排了7个，第8个人出列了，他可以先和前7已经排好的中间的那个人开始比，即第3个人，比他有钱的话再从他后边的4个人的中间的那个人比较。直到找到正确的位置。--折半插入排序（二分插入排序）

想法6：想法5再改进一点点（字挺多，但是逻辑很简单）

其实对于插入排序的话，如果最初始的队伍比较有序的话，对于接下来的排序肯定有好处的，极端情况下是本来就是排好的，第一出列了，第二出列和第一比较直接插在后面，第三出列和第二比较直接插在后边….假如有一两个没排好，排的话依然很快。所以可以想个办法让队伍再进行最后一次直接插入排序之前队伍有序一些。但是又不能花费太大（主要还是利用直接插入，想的这个办法只是起到辅助作用），所以先有个间隔gap，让第1和第6先比较，第2和第7比较…

这样他们间隔挺大的，每个子序列只有2个人比较，会很快，然后缩小gap，让1和4和7比较，这样每次子序列的人多了，但是gap量少了，比较还是比较快的，当然gap选取很重要啦，需要智慧的。---希尔排序

想法7：

你还可以这样想，两个人，两个人组成组，你们内部先比较，比较完之后，再和别的组比较，这个逻辑很普通，就像我们tao.哥如果想统计全国哪个县长最有money，肯定显示交给各个省长，各个省长交给市长，各个市内部先比较，再往上交个省。省里在比较各个市的最多的….这就是归并排序。当然不同两个市里的县长还是要比较的。这样其实是有好处的，毕竟每个市还是比较小的，比较的很快，同时能保证全国这样一个队伍中，这一部分是有序的。效率可想而知，相对还是比较不错的，因为生活中到处再用（适者生存）！！

想法8：

这个思维的跨度有点大，堆排序是选择排序的一种，直接选择是普通人最正常的想法，但是又是很笨的。

可以想像人站成这种形状（完全二叉树）。第一步，50和97交换位置，第二步，（13，27，65）这3个人找出最小的放在现在65的地方，显然13会代替65，之后是（38，50，76）这3个人，如果此时50是最小的（假如38被99代替）那么50上去之后，对（50，97）这两个人有影响的，需要将换下来的99和97再调整。这个过程叫做建堆，这个堆特殊点，父节点都比孩子节点大，但是左右孩子节点没特殊要求。每次从堆顶取出最小的，让最后的一个补上去，此时会再调整堆。但是这个时候调整的话就是沿着某一条线走下去，如（49，38，97，50）这条线或者是（49，38，76）有点二分查找的味道。

想法9

其实不同的事情，排序肯定依照情况而定。上述方法有限，举个最常见的例子，假如想将扑克牌排序，黑>红>梅>方，1>K>Q…

这个时候，上述排序好像不太好用，常见办法先是分成4组，黑、红、梅、方。再利用上面的排序方法排序，这个是基数排序的一种。

纠结了几天，终于写完了。睡觉。（自己写的java代码见附件)

（上次传的代码快排中有一点小问题，抱歉，已经修改，重新上传了）

评论

13 楼 rmn190 2012-03-30  

很亲切， 我也想过给Hibernate框架里的每一个类编一角色， 并以此导演故事， 不过，因为太复杂没进行下去。

12 楼 十三月的 2012-03-29  

akon405 写道

lz很有创意嘛，这样的学习方式就是轻松加愉快。

有创意不敢当啊，平时就这样学，有时候想搞的通俗，理解深一些花的时间和精力就多点，进度可能慢.轻松加愉快，这个词很给力啊

11 楼 akon405 2012-03-29  

lz很有创意嘛，这样的学习方式就是轻松加愉快。

10 楼 十三月的 2012-03-29  

有个问题谁帮忙解答下，为什么有人留言了最近访问记录却没有他呢？

9 楼 十三月的 2012-03-29  

java_age 写道

哈哈，不错。学习到了
不过LZ，直接选择排序貌似有问题。
交换的时候问什么要加这个判断
//交换
if(i!=k){
int tmp=data[k];
data[k]=data[data.length-1-i];
data[data.length-1-i]=tmp;
}

int data[] = {9,1,3,6,5};

你试试。

这个可以不要，当初是基于这样的考虑：如果遍历到第i次应该方的位置是data.length-1-i，如果相等就不用交换位置了。判断条件是data.length-1-i)!=k 你觉的呢

8 楼 java_age 2012-03-29  

哈哈，不错。学习到了
不过LZ，直接选择排序貌似有问题。
交换的时候问什么要加这个判断
//交换
if(i!=k){
int tmp=data[k];
data[k]=data[data.length-1-i];
data[data.length-1-i]=tmp;
}

int data[] = {9,1,3,6,5};

你试试。

7 楼 SoCoolMan 2012-03-28  

给力 再学习学习

6 楼 十三月的 2012-03-28  

guxinglei5920 写道

不错 不错!  有意思...

过奖过奖 通俗些...

5 楼 十三月的 2012-03-28  

345,7,32,5,4,3,12,23,110,7

jdkleo 写道

哥们，快速排序算法是错的，给你一组值，你测下:
int[] a = {345,7,32,5,4,3,12,23,110,7};

哦 代码中的1改为0
    // 递归
     if (position >= 0) {
      quicSort(data, start, position - 1);
      quicSort(data, position + 1, end);
}

position>=1改为position>=0，抱歉啊，当时看见后面的参数position-1，测试数据时候没有测到一种情况是：确定的position之后，position左边没数，全在右边，这个时候就没能再递归...谢谢了

4 楼 jdkleo 2012-03-28  

哥们，快速排序算法是错的，给你一组值，你测下:
int[] a = {345,7,32,5,4,3,12,23,110,7};

3 楼 guxinglei5920 2012-03-28  

不错 不错!  有意思...

2 楼 十三月的 2012-03-28  

郭广川 写道

少年给力呀，顶个

必须的！！

1 楼 郭广川 2012-03-28  

少年给力呀，顶个