几种常见的排序（冒泡、选择、插入、希尔、堆排序）
内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏
1、顺序表结构
2、数据交换函数
3、数据打印
冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两⽐比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为⽌.
也可以反过来，每次都把最大的值放到末尾。
简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1<=i<=n) 个记录进行交换.
总结一句话就是(划重点)：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。
（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；
缺点:时间复杂度太高，效率慢；
选择排序优缺点：优点：一轮比较只需要换一次位置；
缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;
步骤1、将数据插入到有序表中与前一个比较，如果大于则不改变位置
2、如果插入数据小于前一个数据，则前面大的数据依次往后移动，然后找到合适位置插入该数据。
空间复杂度: O(1) 解读:在直接插⼊入排序中只使⽤用了了i,j,temp这三个辅助元素，与问题规模⽆无关，空间复杂度为O(1)
时间复杂度: O(n2)
希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插⼊排序算法排 序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个序列恰被分成 一组，算法便终止.
其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。
希尔排序通过增量进行了分组(分治)，比较的是L->r[j-increment]和L->[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。
也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。
需要注意的是：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
或者
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
如下图1为大顶堆：
下图为小顶堆：
我们用简单的公式来描述一下堆的定义就是：
大顶堆： arr[i] >= arr[2i] && arr[i] >= arr[2i+1]
小顶堆： arr[i] <= arr[2i] && arr[i] <= arr[2i+1]
1、用待排序序列构造一个大顶堆。
2、将其与末尾元素进行交换，此时末尾就为最大值。
3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4、如此反复执行，便能得到一个有序序列了。
我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：
利用堆结构特性，不断选出最大值，放到最后。
归并排序(Merging Sort) 就是利利⽤用归并的思想实现排序⽅方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的⼦子序列列. 每个⼦子序列列的⻓长度为1,然后两两合并.得 到[n/2]个⻓长度为2或1的有序⼦子序列列, 再两两归并. ......如此重复,直到得到⼀一个⻓长度为n 的有序序列列为此. 这种排序⽅方法称为2路路归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。
将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。
进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。
//6归并排序
首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
