发布于

跟我学算法（六）——直接插入的改进希尔排序

在跟我学算法（四）——简单的插入排序一节中我们共同学习了插入排序算法，插入算法主要就是比较和移动两个操作，造成了时间复杂度大的问题。但是插入算法在序列本身有序时能达到O(N)的时间复杂度，也就是说实际上如果序列本身有一定的有序性，那么效率也会更高。而且如果序列本身很短的话，插入排序的效率很是很好的。

希尔排序算法就是在插入排序算法的基础上改进产生的。

希尔排序的基本思想是：把序列按照一定的增量分割成多个子序列。而这个子序列不是连续的，而是通过前面提到的增量，按照一定相隔的增量进行分割的，然后对各个子序列进行插入排序，然后增量逐渐减小，最终减小到1即直接使用插入排序处理序列。

这里增量的选择要求每次都要减少，直至最后一次变为1为止。

上面那样子描述可能让我们很难理解，我们这里再来举个例子。

举个栗子

 

这里我们采用首选增量为n/2，并且每次选择的增量都为前一次的1/2 。

初始序列：592、401、874、141、348、72、911、887、820、283 。

这里有10个数，我们按照上面说的首选增量设置为10/2即5，那么做如下处理：

 

希尔排序

 

这里解释一下：我们的增量是5，所以我们选择第一组序列的时候选择第一个和第六个，第二组序列自然是第二个和第七个，以此类推。分别选出5组序列，每组序列两个数，用直接插入排序算法排序。

这里72需要插入到592的前面，也就是第一组数变为72、592，第二组数不变，第三组数不变，第四组同样不变，第五组数需要变为283、348 。这时候我们的数组就变成了图中显示的结果，即72、401、874、141、283、592、911、887、820、348 。这是第一趟排序。

这里特别说明一下，希尔排序用的还是原本的数组，根本上还是在每组序列中使用的插入排序，忘记的同学自己去回顾一下插入排序去。

第二趟增量是5/2=2，所以我们就是做如下分组，总共分了两组，分别进行插入排序，第三趟增量是2/2=1了，于是就是直接的插入排序了。接下来我就直接上图了。

希尔排序

 

最后我们总结一下，这个希尔排序实际上只是使用了一种增量的方式改进插入排序。不管序列总数有多少，刚开始增量很大，所以每次的插入排序实际上都很块，因为规模很小。尽管在之后规模慢慢变大，但是那时候这个序列已经越来越基本有序了，所以插入排序算法的速度也是越来越好。

在时间复杂度这一点上，由于增量的序列不一定，时间复杂度也不确定。这在数学上还无法给出确切的结果。我们在上面采用的是简单的除2方式，但是据研究，有几种推荐的序列：

1：N/3+1，N/3^2+1，N/3^3+1…（据说在序列数N<10w时最优）

2：2^k-1，2^(k-1)-1，2^(k-2)-1…（设k为总趟数）

大家有兴趣可以试试上述两种方式的增量处理，其实思想都一样，建议第一种方式，比较简单，效率也比较好。

本文原创于本人博客，请访问 http://irfen.me

发布于

跟我学算法（五）——简单选择排序

上节我们一起学习了简单插入排序，不过插入排序既然很慢，和冒泡排序真是患难兄弟了。但是插入排序也有一个好处就是所占空间很少，额外空间只有一个存储临时变量的空间就够了。

这节我们一起来学习一下简单选择排序算法。

简单选择排序的基本思想就是（以从小到大为例）：在要排序的一组数中，选出最小的一个数与第一个数交换，然后再在第二个数到最后一个数中找到最小的一个数与第二个数交换，以此类推，知道倒数第二个书与最后一个数比较为止。

这个比较好理解了。下面距离说明。

初始序列为3、1、5、7、2、4、9

第一趟排序结果：1、3、5、7、2、4、9

第二趟排序结果：1、2、5、7、3、4、9

第三趟排序结果：1、2、3、7、5、4、9

第四趟排序结果：1、2、3、4、5、7、9

第五趟排序结果：1、2、3、4、5、7、9

第六趟排序结果：1、2、3、4、5、7、9

这里分析一下复杂度，在最好的情况下，数字串本身就是有序的，则一次都不需要交换；在最坏的情况下，待排序字串是逆序的，则交换次数最多（次数是3(n-1)）。

选择排序的交换操作介于0和(n-1)次之间；比较操作为n(n-1)/2次之间；赋值操作介于0和3(n-1)次之间。比较次数与本身的序列是无关的，只与长度有关。所以进行比较的时间复杂度是O(N²)，而移动操作的时间复杂度是O(N)。实际上交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

最后大家可以想想，这个选择排序还有没有什么可以优化的地方？

给大家提示一下，我们每次都是找最小的去交换，如果我们在里面每次都把最小的和最大的都找出来，一次交换两个呢？实际上这就是一个对选择排序的改进，二元选择排序算法。

本文原创于本人博客，请访问 http://irfen.me

 

发布于

跟我学算法（四）——简单的插入排序

上一节我们一起看了快速排序，是不是很给力。这节我们来学习一个简单的排序，思想简单，实现起来也很简单。

插入排序，插入排序有两种，一种是直接插入，一种是二分插入。我们这里暂时先介绍直接插入，二分插入这个之后我们在说二分查找法的时候会提到。大家如果迫不及待的话，也可以在网上搜索一下相关的内容。这两种方法只是插入的方式不同而已。

插入排序，顾名思义就是把数字列表以一个一个元素的插入的方式来排序。

遍历整个数字列表，然后根据数字的位置插入到应该的位置完成排序。

我们以下面的数字序列为例介绍：6、9、3、10、4、5、1 。我们要排序这样的序列，

首先我们需要存储这个列表：

插入排序

 

然后我们开始插入，首先6也就是第一个元素可以直接插入我们不用管，我们从第二个元素开始处理。

接着我们开始插入9，发现9比6大，所以不需要管，9就该在6后面。

这时候我们接着开始排序3，3和上一位比，发现3比9小，所以我们需要把9向后移动变为下图样子：

插入排序

发现也比6小，于是6也移动变为下图样子：

插入排序

 

发现已经到头了，所以把3插入到空位（首位），使序列变为

3、6、9、10、4、5、1 。

接着我们排序10，先与上一个比较，发现比9大不需要操作，继续排4，发现比10小，则10需要后移，发现比9小，9后移，比6小，6后移，发现比3大，所以可以把4放在原有的6的位置上。

5、1也是如此排序。

这样插入排序就完成了。这里实现的代码也很简单，我就先放上来了。之后我会总结之前所讲的所有的代码实现。

    public static void main(String[] args) {
        int[] x = {6, 9, 3, 10, 4, 5, 1};
        insertionSort(x);
        for (int i : x) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
 
    private static void insertionSort(int[] unsorted) {
        for (int i = 1; i < unsorted.length; i++) {
            if (unsorted[i] < unsorted[i - 1]) {                 int temp = unsorted[i];                 int j = i;                 while (j > 0 && unsorted[j - 1] > temp) {
                    unsorted[j] = unsorted[j - 1];
                    j--;
                }
                unsorted[j] = temp;
            }
        }
    }

最后总结一下时间复杂度吧，因为是双重循环，所以时间复杂度还是O(N²)，空间复杂度是O(1)，其实只是需要一个空间去存储一下这个待比较值而已，并没有需要额外的空间，还是用的以前的空间去排序的。

本文原创于本人博客，请访问 http://irfen.me

发布于

跟我学算法（三）——最常用的快速排序

上一节学习的是冒泡排序，时间复杂度是O(N²)，如果我们的计算机每秒运算10亿次，排序1亿个数字，那么最开始我们介绍的桶排序只需要0.1秒，而冒泡排序则需要1千万秒，换算成天也就是115天，这，…

那么有没有什么排序是既省时，又省空间的呢？下面我们就来学习一下快速排序。

现在我们要对6、1、2、7、9、3、4、5、10、8这十个数字进行排序。按照快速排序的思想，先找一个数字作为基准数（这只是个专用名词，不可怕，不可怕…）。为了方便，我们就用第一个数字6作为这个基准数吧。那么下面我们就需要把所有小于6的数字放到6的左边，大于6的数字放到右边。

其实就是在初始的时候，我们的6这个数字在第一位，现在我想把它移动到中间某个位置k，现在就需要寻找这个k，并且已k为分界点，左边的数字都小于6，右边的数字都大于6 。大家相出怎么做了吗？这里提示一下我们的冒泡排序是怎么做的，但是那样交换太累了，大家有没有更好的方式？

快速排序是这样操作的，分别从序列的两端开始看，先是从右往左找一个小于6的数，再从左往右照一个大于6的数，然后交换他们。从左往右的变量就设为i吧，从右往左的变量就设为j。

首先j先从最右往左移动（即j–），这里需要注意一下，因为我们的基准数是第一个数，所以必须先从j开始移动（这里大家想想是为什么），直到j找到一个比6小的数字停下来，然后i开始从左往右找一个比6大的数字停下来，在这里i和j所指的数字交换位置。

在我们这个例子中，结果如下图：

快速排序

 

交换后的数字序列上图也展示了，即是6、1、2、5、9、3、4、7、10、8 。

这样第一次交换完成，再然后j–继续，找到4比6小，i++也继续，发现9比6大，于是ihej所指的数继续交换，结果即是6、1、2、5、4、3、9、7、10、8 。这时候j还是应该执行j–操作，发现3比6小，但是i++之后发现与j相遇了即i==j，这时候就应该停止了，但是还有一步就是需要交换3和基准数6，然后就完成了一次交换动作。

这次之后，序列变为了3、1、2、5、4、6、9、7、10、8 。此时就已经完成了6前面的数都小于6，6后面的数都大于6这个任务了。最后我们在总结一下，实际上j是为了找小于基准数的数字，i是为了找大于基准数的数字，直到i、j碰头。此时的6其实已经完成了排序，因为他正好前面的数都小于他，后面的数都大于他。

我们接下来只需要再继续分别排序左右两边的序列就行了。

先看左边的序列，3、1、2、5、4，我们以3为基准数，用上面的方法进行排序，大家可以自己先拿出笔来试试。

这里我们还是设i和j，首先j开始做j–操作，一直到2发现2比3小，i开始做i++操作，但是走到2的时候与j碰面了，于是交换2和3完成这次排序，这时候3已经完成了排序。序列为2、1、3、5、4 。

再然后就是分别排序2、1和5、4，这里我们再举例一下2、1，同样设置2为基准数，j–，发现1比2小，i++发现到1时与j相等，此时交换。如果是本来就排好序的，那么j一直从最尾到j==0也没有需要交换的，说明基准数本来就在正确位置上。

就这么下去，我们接着排好了5、4，9、7、10、8，最终就完成了排序。

快速排序是不是也很简单呢？快速排序实际上就是在冒泡排序的基础上改进而来的，冒泡排序每次都只能相邻的两个交换，而冒泡排序是跳跃的，交换的距离很大，因此总的比较和交换次数就少了很多。当然也就提速咯~

但是最坏的情况下还是和冒泡排序一样，时间复杂度还是O(N²)，但是它的平均时间复杂度是O(NlogN)。这种算法思想实际上是一种分治法思想，顾名思义就是分而治之的意思。

快速排序是C. A. R. Hoare（东尼•霍尔，Charles Antony Richard Hoare）在1960年提出来的，后续也有很多改进，如果你对快速排序感兴趣可以去看看东尼•霍尔1962年在Computer Journal发表的论文“Quicksort”以及《算法导论》的第七章。这个人也是在ALGOL X这个语言中发明了case语法，也被我们很多现在很流行的语言使用着呢。

本文原创于本人博客，请访问 http://irfen.me

发布于

跟我学算法（二）——咕嘟咕嘟的冒泡排序

上节介绍了桶排序，虽然说他很快，但是也有一个弊端，如果我们的数值范围很大，比如我们数值的范围是0~2亿，我们就需要2亿+1个桶，就算只有五个数要排序，我们也要准备那么多桶，这个空间消耗太吓人了。还有一个情况是如果我们的数值有小数，这个桶该怎么解决？这也很难。

下面我们就来看一个新的算法——冒泡排序。

冒泡排序的主要思路就是每次都比较相邻的两个元素，根据大小交换位置。

例如我们要把12、35、99、18、76这5个数从大到小进行排序，那么我们就要把越小的数越放到后面。冒泡排序的思想就是每次遍历未排序的序列，把最小的移动到最后或最前（在这里从大到小，就是把最小的移到最后）。

首先比较前两个数，发现12比35小，就交换位置。序列就变成了35、12、99、18、76，下面在比较第二和第三个数，发现12比99小，于是也交换位置。序列变成了35、99、12、18、76，一次列推，最终序列会变成35、99、18、76、12 。现在最小的一个数12已经移动到了最后。

我们现在可以准备排序前四个数了，第五个数已经排序完成了。

还是按照上面的方法，排序后的序列编程35、99、76、18、  (12)。

这样在排序前三个，一层一层的排序，就好像最小的一个一个冒泡的最后面一样，所以叫冒泡排序。这里总共有N个数，实际上就需要重复上述操作N-1次。这个算法让我想起了拍集体照的时候小个儿总是一个一个的被往后推，是不是就是受了这个影响发明的算法。

最后看一下时间复杂度，实际上这个算法是个双重循环，所以它的时间复杂度是O(N²) 。这个时间复杂度很高，冒泡排序在1956年开始就有人开始研究，后续也有很多人对这个算法进行改进，但结果都很惨，1974年图灵奖获得者所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”

本文原创与本人博客，更多请访问 http://irfen.me

发布于

跟我学算法（一）——超快而简单的排序——桶排序

排序充斥着我们的生活，站队、排队买票、考试排名、苦逼的公司业绩排名、email中邮件按时间排序、qq好友列表里红名靠前等等。

下面举个例子介绍下排序算法：

举个栗子

 

期末考试，老师要把大家的分数排序，比如有5个学生，分别考5、3、5、2、8分（满分十分），从大到小排序应该是8、5、5、3、2，大家有没有办法能够写段程序随机读入5个数，然后排序呢？

 

这里应该给自己点时间自己想想。就5分钟把，想想再往下看。

提示一下，用个一维数组就可以咯~

 

这里用一个数组，长度为11，刚开始的时候值都初始化为0。

Int [] a = new int[11];

数组

 

下面开始处理，遍历考分，多少分，就在多少下标处的值加1。如第一个5分，就a[5]的值加1。

数组

 

以此类推下面的就直接上图。

数组

 

数组‘

最终如下：

数组

 

这里其实a[0]~a[10]就是0-10分，每个里面的值就是得这个分的人数。接下来我们只需要倒序将有分数的值打印出相应的次数就行了。

 

这种排序我们暂且先叫他桶排序，但实际上真正的桶排序要比这个复杂的多，这个我们以后再说。

 

这个算法就好比我们有11个桶，编号从0-10，每出现一个值，就在对应桶里放一个小旗，最后只需要按顺序数下每个桶里的旗子个数就行了。

 

最后就是算法里很重要的一点，时间复杂度，一个是桶子个数M的循环，一个是排序数字个数的循环N，分别都要循环两次，所以时间复杂度是O(2*(M+N))，忽略常熟记为O(M+N)。空间复杂度是O(M+N)，当然，如果数值范围非常大，桶的个数特别多，空间的代价肯定也是不切实际的，所以这个算法也是有所局限的。

 

最后，再跟大家分享一个情况，就是如果排序的数字中，每个数字都是唯一的，我们还能更加精简空间，这里就可以不使用int类型而是用boolean类型，就可以了。实际每位占用空间只有1个bit。（算法上来说是这样，或者有的语言有bit类型）

说到这里在给大家分享一个java虚拟机里内存存储的相关知识。

虽然boolean只占1个bit就够了，但是java实际的情况是占用多少不确定，但肯定比1bit多。在咱们的数组的情况下是占1字节。

关于这个的更多内容可以参考http://irfen.me/java-basic-data-type-space