其中快速排序通过设计巧妙的原地分区函数，实现原地排序，可以将空间复杂度降低到O(1)。
Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数。
为什么要考察排序算法的稳定性呢：
很多数据结构和算法课程，在讲排序的时候，都是用整数来举例，但在真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.2动图演示
functionbubbleSort(arr){varlen=arr.length;for(vari=0;i
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
functioninsertionSort(arr){varlen=arr.length;varpreIndex,current;for(vari=1;i
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
//修改于2019-03-06functionshellSort(arr){varlen=arr.length;for(vargap=Math.floor(len/2);gap>0;gap=Math.floor(gap/2)){//注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行for(vari=gap;i 理解归并排序的重点是理解递推公式和merge()合并函数。 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 分解的过程用递归来实现，而合并的过程： 我们申请一个临时数组tmp，大小与A[p...r]相同。我们用两个游标i和j，分别指向A[p...q]和A[q+1...r]的第一个元素。比较这两个元素A[i]和A[j]，如果A[i]<=A[j]，我们就把A[i]放入到临时数组tmp，并且i后移一位，否则将A[j]放入到数组tmp，j后移一位。 继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组tmp中的数据拷贝到原数组A[p...r]中。 理解快排的重点是理解递推公式以及partition()分区函数。 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： functionquickSort(arr,left,right){varlen=arr.length,partitionIndex,left=typeofleft!='number'0:left,right=typeofright!='number'len-1:right;if(left 快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？ 原地分区函数的实现思路非常巧妙： partition(A,p,r){pivot:=A[r]i:=pforj:=ptor-1do{ifA[j] 分区的整个过程： 那什么样的分区点是好的分区点呢？或者说如何来选择分区点呢？ 最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。 我这里介绍两个比较常用、比较简单的分区算法，你可以直观地感受一下。 我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。 快速排序是用递归来实现的，递归要警惕堆栈溢出。为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。 以下1、2为大顶堆，3为小顶堆，4不是堆 应用实例： 高考查分数系统：我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？ 计数排序的算法思想就是这么简单，跟桶排序非常类似，只是桶的大小粒度不一样。 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序(Bucketsort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。 基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。 虽说qsort()从名字上看，很像是基于快速排序算法实现的，实际上它并不仅仅用了快排这一种算法。 但如果数据量太大，就跟我们前面提到的，排序100MB的数据，这个时候我们再用归并排序就不合适了。所以，要排序的数据量比较大的时候，qsort()会改为用快速排序算法来排序。 那qsort()是如何选择快速排序算法的分区点的呢？如果去看源码，你就会发现，qsort()选择分区点的方法就是“三数取中法”。 还有递归太深会导致堆栈溢出的问题，qsort()是通过自己实现一个堆上的栈，手动模拟递归来解决的。 假设k=1000，c=200，当我们对小规模数据（比如n=100）排序时，n2的值实际上比knlogn+c还要小。