求索阁

冒泡：

第i个元素与第 i+1个元素俩俩相比然后互换位置，第一次循环会把最大的元素挪到最后，第二次是把第二大的元素挪到倒数第二。。。。。每次都会把最大的元素不断往后冒，与选择排序刚好相反。复杂度：n^2

选择：

用第i个元素比较后面的所有元素，从前往后比较，一直找到最小的一个挪到最左边，其实就是替换i的位置，与冒泡排序相反，第一次能找到最小的元素，第二次能找到第二小的元素。。。。复杂度：n^2

插入：

从前往后，把每个数往前面合适的地方插入。复杂度：n^2

归并：

把待排序队列分为n个有序的子队列，再合并他们，其实也是分治法思想的一种使用。复杂度：n*logn

快速：

冒泡排序的进化版，第一个数据把做全量对比，把比这个数小的放到它左边，大的放到右边，然后分别对左右两部分再进行快排，递归计算完成排序。也是分治法的使用，与归并某种意义上相反：归并是不断分成两份然后合并，快排是不断分成两个部分排序，快排一般会比归并快3倍，并且可以通过随机化快速排序规避最差情况(n^2)，保证nlgn复杂度。复杂度：n^2，但是平均情况很快，达到nlgn

树型选择排序：

是一种按锦标赛的思想进行排序的方法。
基本思想与体育比赛时的淘汰赛类似。首先将n个对象的排序码进行两两比较，得到n/2个比较的优胜者，作为第一步比较的结果保留下来；然后对这n/2个对象再进行排序码的两两比较，…，如此重复，知道选出一个排序码最小的对象为止。类似于一颗二叉树，只需要把每次比较出的最小值的结点重新设置为∞，再比较出新一轮的最小值出来。复杂度：n*logn

堆排序：

对树形排序的进一步改进，使用一个大根堆（或者小跟堆）进行排序。堆排序的两个问题：
1.如何由一个无序序列“建初堆”。
2.输出堆顶后，如何“筛选”。筛选指对一颗子树均为堆的完全二叉树，调整根节点，使整个二叉树也成为一个堆。循环输出堆顶。

统计排序：

适用于知道数据范围的整数排序，预先分配好固定范围数组，统计每一个数组中数值在待排数组中出现的频率，统计结束后也就知道了每一个数在“排序后”数组中的位置，知道待排数组都是10以内的正整数，如：1，2，2，3，2，4，7，7，1。我们用一个长度为10的数组统计这个数组，得到｛0，2，5，6，7，7，7，9，9，9｝分别对应0~9这个数字知道1在数组中出现2次，则1在“排序后数组”中应该出现在（0，1）这两个索引位置，2在数组中也出现3次，所以2应该在（2，3，4）这三个索引上，刚好对应上面统计数组中的index=1，2的值减一。复杂度：n

多关键字排序：

以扑克牌排序为例，每张扑克牌有两个关键字：花色和面值。可以先按花色排序，之后再按面值排序；也可以先按面值排序，之后再按花色排序。

基数排序：

类似于一堆0~999的数据，先按个位排序，再按十位排序，再按百位排序，得到的结果就是最终的排序结果。一般每个位的排序选择统计排序复杂度：n

以上排序思想可以做一个大概的分类，如下：

插入类排序：将无序子序列中的一个或几个记录插入到有序序列中，从而增加记录的有序子序列的长度。例：插入排序。
交换类排序：通过“交换”无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它加入有序子序列中。例：冒泡排序、快速排序。
选择类排序：从记录的无序子序列中，“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。例：简单选择排序，树型选择排序，堆排序。
归并类排序：将两个或两个以上的有序数据序列，合并成一个有序数据序列的过程。例：归并排序。
分配类排序：主要利用分配和收集两种基本操作，典型的就是基数排序和多关键字排序。

再介绍两个排序的相关概念：

比较排序：只允许比较操作，以上的排序都是比较排序。
决策树排序：通常会有n个元素需要排序，<a1,a2...an>，对于每一个内节点（非叶子节点），都会有一个下标i:j，i和j分别在1~n之间，这个节点表示我们要比较ai和aj，每个内节点下会分出两颗子树，左边的子树说明ai<aj的情况下，算法要做什么，后续会进行哪些比较，考虑到会有等于的情况，我们让左边子树代表ai<=aj的情况，右边子树对应大于的情况，而每一个叶节点代表一个排序，若某个排序是正解，这这个排序更好地表达了数的特定排序。比较排序都可以转换成决策树模型，决策树是排序的一种图形表示。