Java 常用的八种排序算法与代码实现

2017-09-12 00:14 出处:csdn 人气: 评论(0

写排序算法是一个大工程,估计得好多天才可以写完。。。就慢慢写吧。未完待续。。。。

内部排序和外部排序

内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。

排序算法的稳定性?

排序算法可以根据稳定性分为两种:稳定和非稳定算法。那么怎么区分它们?如果链表中存在两个相同元素,稳定排序算法可以在排序之后保持他两原来的次序,而非稳定性的则不能保证。
这里写图片描述

算法稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。

排序分类

简单排序类别:

两种简单排序算法分别是插入排序和选择排序,两个都是数据量小时效率高。实际中插入排序一般快于选择排序,由于更少的比较和在有差不多有序的集合表现更好的性能。

有效算法:

冒泡排序和变体类别:

  • 冒泡排序、
  • 希尔排序、
  • 梳排序
    这种类别的算法在实际中很少使用到,因为效率低下,但在理论教学中常常提到。

线性时间的排序:

1. 直接插入排序

  • 思想:
    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
  • 要点:设立哨兵,作为临时存储和判断数组边界之用。
  • 流程图
    这里写图片描述
  • 做法:
首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入。
设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
将当前数放置到空着的位置,即j+1

代码实现:

privatestaticint[] insertionSort(int[] arrayToSort) {
        int length = arrayToSort.length;
        int insertNum; //要插入的数for (int i = 1; i < length; i++) { // 排序多少次,第一个数不用排序
            insertNum = arrayToSort[i];
            int j = i - 1; //已经排序好的序列元素个数while (j >= 0 && arrayToSort[j] > insertNum) {
                arrayToSort[j + 1] = arrayToSort[j]; //j 位元素大于insertNum, j 以后元素都往后移动一格
                j--;
            }
            arrayToSort[j + 1] = insertNum;//比较到第j 位时 小于 insertNum ,所以insertNum 应该放在 j+1 位
        }
        return arrayToSort;
    }

2. 希尔排序

3. 简单选择排序

4. 堆排序

5. 冒泡排序

6. 快速排序

快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

7. 归并排序

8. 基数排序

未完待续。。。

本文主要摘引自三篇排序文章,我只是进行删减、拼接和添加一些自己的理解,并编码实现。权且认作是我原创文章。如有侵犯,联系我,我会妥善处理。
源码地址:https://github.com/527515025/JavaTest/tree/master/src/main/java/com/us/acm
参考资料:
https://zhuanlan.zhihu.com/p/27005757
http://blog.csdn.net/hguisu/article/details/7776068/
http://blog.csdn.net/langbinhui/article/details/23614331

本文标签:

相关文章

网站内容来源于互联网,仅供用于技术学习,请遵循相关法律 规,如有侵权,请联系管理员删除

Copyright © 2002-2017 JISHUX. 技术栈 版权所有

京ICP备15061484号-3