以下内容为数据结构一门课程的摘要笔记
排序
简单排序
冒泡排序
（从小到大排序）存在10个不同大小的气泡，第一次由底至上地把较少的气泡逐步地向上升，这样经过遍历一次后，最小的气泡就会被上升到顶（下标为0），第二次的时候最小的气泡不参与排序，再从底至上地这样升，循环直至十个气泡大小有序。
在冒泡排序中，最重要的思想是两两比较，将两者较少的升上去
冒泡排序最坏情况的时间复杂度是O(n²)
插入排序
每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
如果排序记录是随机的，那么根据概率相同的原则，在平均情况下的排序码比较次数和对象移动次数约为n^2/4，因此，直接插入排序的时间复杂度为O(n2)。
例子：
以下面5个无序的数据为例：
65 27 59 64 58
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
其中，排序时第一个数字不动，从第二个数字开始做排序，27<65故将65右移，右移后左侧没有元素，将27放在此处；第二次插入数字为59，59<65故65右移，59>27故59放在此处，依此类推完成排序。
逆序对
对于下标i<j,如果a[i]>a[j]，则称（i，j）为一对逆序对。
选择排序
从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。选择排序大致可以分为两个步骤，寻找最小元，最小位置与最小元交换，然后这两步循环进行；其中寻找最小元需要做一次循环，外层仍要一次循环，故复杂度为O（N^2）。
其他排序
堆排序
- 堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。
- 由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。
shell排序
shell排序是对插入排序的一个改装，它每次排序把序列的元素按照某个增量分成几个子序列（即每隔增量个元素提取原序列构成子序列），对这几个子序列进行插入排序，然后不断的缩小增量扩大每个子序列的元素数量，直到增量为一的时候子序列就和原先的待排列序列一样了，此时只需要做少量的比较和移动就可以完成对序列的排序了。为了高效完成，所有增量元素起码需要互质。
例子：
上图中，首先每隔5个元素做一次提取，例如第一次提取为（81，35，41），对此子序列进行插入排序。而后第二次提取为（94，17，75），再对此子序列进行排序，依此进行，直至5间隔排序完成。再进行3间隔排序，3间隔排序完成后进行1间隔排序。1间隔排序后即完成整个序列排序。
归并排序
- 设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。
- 归并排序常作为外部排序使用的算法。外部排序的定义： 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
快速排序
该方法的基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
快速排序对小规模的数据（例如N不到100）可能还不如插入排序快，为此，当数据小于一定规模时应当停止递归直接调用简单排序。
间接排序
复制/移动元素代价很高时，另外设置一个数组，其中每个元素是指向原数组元素的指针，针对这个指针数组进行交换等操作.举例:
排序前:
索引数组：0 1 2 3 4
待排数组：4 3 1 2 5
排序后：
索引数组：2 3 1 0 4
待排数组：4 3 1 2 5
上面例子中，排序后为了获得有序数组，利用索引数组的下标去取待排数组中的值即可得到有序数组：
a[2]:1 a[3]:2 a[1]:3 a[0]:4 a[4]:5
桶排序
例如待排数字[6 2 4 1 5 9]，准备10个空桶,最大数个空桶
[6 2 4 1 5 9] 待排数组
[0 0 0 0 0 0 0 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]
[6 2 4 1 5 9] 待排数组
[0 0 0 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶
[6 2 4 1 5 9] 待排数组
[0 0 2 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
3,4,5,6省略,过程一样,全部入桶后变成下边这样
[6 2 4 1 5 9] 待排数组
[0 1 2 0 4 5 6 0 0 9] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9
基数排序
按照下面的一组数字做出说明：12、 104、 13、 7、 9
- 按个位数排序是12、13、104、7、9
- 再根据十位排序104、7、9、12、13
- 再根据百位排序7、9、12、13、104
各种排序方法的比较
