排序（Sorting）是将一组数据序列按照关键字的非减或非增的顺序排列起来的操作。将待排序内容全部放在内存中的排序叫做内部排序，一次放不进来需要多次读取外存的叫外部排序，现在介绍内部排序。
内部排序有许多方法，常见的有：Straight Insertion Sort，Shell Sort，Quick Sort等。可以分为如下几类：
下面分别简要介绍其排序原理（无代码）：
设想在打牌的时候，在牌堆里摸一张牌后，我们需要对新加入的牌和已有的牌进行比较，将新牌插入手中的牌中。插入类排序基本就是基于这样的思想，将乱序的部分看成牌堆，有序的部分看成手中的牌，然后依次从无序的中选择一个进行插入。主要有下面几种实现：
这是最简单的方法，首先，从第2个元素开始，把现在的元素左边的元素作为已经排序好的（后面的叙述中默认我们要求的排序是升序排列），如果这个元素比左边有序序列的最后一个，也就是该元素的前一个大，那么就不管它，继续向右移动，如果比有序的最后一个小，那么说明要进行插入操作，那么从有序序列的右边向左边依次比较，找到第一个比待插入元素小的元素，那么待插入元素就应该插在它的右边。依次对所有元素进行，就可以实现直接插入排序。
为了排序方便，我们常将数组的第一个元素设置成【哨兵】，即如果需要插入操作的话，首先将待插入元素放入哨兵，然后每比较一次如果比哨兵大，那么可以直接右移，因为最右边的已经在哨兵中暂存了。如此直到一个小鱼哨兵的位置，这时候我们把哨兵的元素放到它的右边就可以了。
折半插入排序是将直接插入的查找过程通过二分查找实现，利用了已经排序好的序列部分的有序的性质，可以减少比较次数，但是由于移动次数不变，因此时间复杂度和空间复杂度与直接插入一样。也是稳定排序。适合初始记录无序，n较大的情况。
希尔排序本质上是一种【分组插入排序】， 希尔排序维护一个增量序列【d1，…，dn】，每次从增量序列中递增地取一个值dk，然后以dk为间隔，在要排序的数列中取值，得到间隔为dk的一组值，然后进行插排，然后同样间隔右移一个单位，重复上述操作，等都重复完了以后，再取dk+1间隔，仍然以这样的一组为单位进行插排。因此直接插排可以看成是增量序列为【1】的特殊的Shell 排序。
可以这样理解，shell sort把数据分成了d1，d2，。。。，dn个组（间隔数就是组数，因为考虑到要移动 0 – dk-1 ）然后分组插排，这样的好处就是通过大间隔的插排，使得数列已经基本有序，这样对于普通的插排可以提高效率。
增量序列的取法要满足：所有序列中的数字没有除了1以外的公因数。并且最后增量为1。
所谓交换类排序的思路是，遇到一个不符合前小后大的两个数，都进行一次交换，这样就可以把所有的都排整齐。
实际上，这种思路归结起来就是四个字：消除逆序。只要逆序全部消除，排序就完成了。最常见也是思路和实现最简单的是冒泡，bubble sort，有的地方也叫起泡排序。还有另一种特殊的复杂一点的交换方法，就是QuickSort，快排。下面分别说明：
实际上，这个排序方法就是依次进行相邻两个数的逆序消除，从无序部分的第一个到最后一个的依次遍历就是一趟，（确切的说，所谓一趟的定义是，使得有序序列中增加一个元素），因为每次这样都可以把最大的从左到右沉下去，而遍历多趟以后慢慢将小数冒出来，这就是冒泡排的名字的由来。设想如果从左到右，最大值每次都会和右边比较一下，所以它一定会一路把右边的值都推上去，从而自己沉在最下面，每次拿出一个最大值就把无序的长度减一，这样再把次大的拿出来，依次类推，即可全部排好。
冒泡是稳定的，由于两两比较，然后要比较的序列长度也是线性减少，所以明显为O(n^2)，空间复杂度就是交换的那一临时变量，所以是O(1)。
QuickSort是一种较为特殊的交换排序，instead of 冒泡的相邻两两交换，快排可以一次性消除多个逆序。比如对于一个数列【4 2 3 1】，冒泡的话需要 42 43 41 才能交换到【2 3 1 4】，然后到【2 1 3 4】，再到【1 2 3 4】，而快排的想法是，如果我们直接把 1和4调换位置，那么可以只用一次，就消除了所有逆序。
快排是这样操作的，首先，选中一个数字，把它作为枢轴（pivot），将小鱼pivot的放到pivot的左边，大于的放到右边，这就是我们的目的。那么如何放呢？首先，我们维护两个指针，一个low，一个high，如果low小于high，也就是说还可以移动，那么当low指向的key小鱼pivot的话，就把low往高出移动，而同样的，如果high大于pivot，则向低处移动。这样很明显，如果都满足的话，它们会在pivot在有序数组中应在的位置相遇。那么如果不满足，即比如low指向的反而大于pivot，或者high指向的小鱼pivot，那么我们将这两个数交换，就可以消除这种逆序。
具体的实现方法是这样：首先，把最左边的元素作为pivot，然后把low放在最左边的pivot位置，high放到最右边，当然这个过程中还要维护一个pivotkey变量来暂存这个值，为交换腾出空间。这样先移动high，直到找到一个比pivotkey小的值，于是high停下来，把指向的内容赋予low，然后low开始右移，直到比pivotkey大的，low停下，把内容给high，然后high在继续。。。如此下去，知道low==high，此时的位置就是pivotkey的位置。为甚么捏？因为low移动的条件是，high指向的某个小鱼pivotkey的元素已经被交换到low此时的位置上了，所以low指向的位置小鱼pivotkey了，所以low才能走。也就是说，low移动到了某个位置，说明它前面的位置必然都小鱼pivotkey，high指针同理，所以这个相遇点就是pivot应在的位置，于是把pivotkey赋予这个位置。
实际上，每次我们都能以pivot为中心，左边小鱼pivotkey，右边大于。那么递归调用，把high用pivot，low用上次的low，以及low用pivot+1，high用上次的high。由此下去，即可得到全部的排列。
快排由于移动或者交换是非顺次交换的，所以不稳定，适合于初始无序，n较大，在平均情况下最快。
选择类排序的基本思路是：把要排序的数组的最小值选出来，放在最小的位置，然后从第二个开始，再选次小的，。。。以此下去就可以排好。
基本思路很简单，就是从左到右，依次选择后面无序序列中最小的，放在有序的后面，使得有序长度加1。具体实现是这样：首先把想要放到的位置记做i，也就是无序的第一个位置，然后在后面找到最小的返回其位置k，if not k == i，则需要把i和k对应的元素交换，两重循环下去就可以排好，外循环用来移动i，内循环找min的下标。
既然选择排序中含有选择min 的过程，因此可以就这个进行优化，如何选择最小值，不需要逐个遍历，我们可以利用之前选择最小值时得到的信息，来简化后面的选择。树形选择就是这个思想的一个实现。我们把要排序的n个数作为叶子，然后两两比较，将最小的放到上面做子树的根，这样就可以得到最小的。得到后，把最小的那个数在叶子上置为inf，从这个点网上，重新比较这一条路径，直到root，这时候就是次小，以此类推。
这个比较一次就是tree的深度，要n次比较，所以O(nlogn)，但是需要额外的空间，叶子n个，所以总共node也是n的线性倍数。
堆排序利用了最大堆的调整过程，通过堆来实现在O(1)里对list进行选择排序。首先，建立最大堆，也叫大根堆，顾名思义就是根节点的key大于两个儿子的key，建立好以后，我们就得到了最大值，然后把最大值放在最后，也就是和堆的最后一个元素交换，并且不考虑这个元素，把剩下的n-1个元素重新调整为堆，依次下去，就可以得到一个排序。
堆排序的时间复杂度取决于筛选法调整堆的过程，筛选n-1次，每次都有logn的级别的操作，所以时间复杂度是O(nlogn)，而空间复杂度显然是常数，就是交换根和最后一个元素的时候的中间变量。
堆排是不稳定的。
归并类排序是针对两个已经排好的序列，merge一下，重新整合成一个有序序列的过程。
利用递归，把merge sort 的过程一直下放到两两merge，然后逐层递归回来，就可以得到多个数的排序结果。
每趟归并不超过n个key，共需要logn趟，所以为O(nlogn)。归并需要中间变量，就是merge 的输出的存放的空间，所以空间为O(n)。
对于特殊情况的排序，可以突破排序的O(nlogn)的界限，达到O(n)。
先根据个位数分配，在收集，在根据十位数分配，再收集，。。。依次下去，就可以得到每个位置都是顺序的结果。利用了多关键词排序的方法。
美妙的假设被丑陋的事实扼杀，这是科学之大悲剧 —— 博物学家， 托马斯 亨利 赫胥黎