嵌入式LinuxC基础：排序
1.排序的稳定性
只有含有相同元素才有稳定性。相同元素的相对位置发生变化，怎不稳定。相对位置不变，则稳定。
2.直接插入排序
对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。
希尔排序也称为“缩小增量排序”，基本原理是：首先将待排序的元素分为多个子序列，使得每个子序的元素个数相对较少，对各个子序分别进行直接插入排序，待整个待排序序列“基本有序后”，再对所有元素进行一次直接插入排序。
具体步骤如下：
(1)选择一个步长序列t1, t2, ..., tk,满足ti > tj(i <ｊ)，tk = 1。
(2)按步长序列个数k，对待排序序列进行k趟排序。
(3)每趟排序，根据对应的步长ti，将待排序的序列分割成ti个子序列，分别对各个子序列进行直接插入排序。
希尔排序的特点：
时间复杂度：希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1.3）。
稳 定 性：不稳定
对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和交换位置后，n个记录中的最大记录将位于第n位；然后对前(n - 1)个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。
冒泡排序特点分析：
时间复杂度：总共比较 n(n-1)/2 次 时间复杂度为O(n2)
稳 定 性：稳定
快速排序是一种非常高效的排序方法，采用“分而治之”的思想，把大的拆分为小的，小的在拆分为更小的。
原理是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均为有序为止。
快速排序特点：
稳 定 性：不稳定
平均时间复杂度： O(nlog2n)
是一种简单直观的排序算法，他的基本原理是：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮排序，得到最小的记录并与第二个记录进行位置交换；重负该过程，直到进行比较的记录只有一个为止。
时间复杂度：总共比较 n(n-1)/2 次 ，移动次数最多n-1, 时间复杂度为O(n2)
稳定性：稳定。
7.堆排序
堆排序是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一棵完全二叉树，根节点的值小于(或大于)两个子节点的值，同时根节点的两个子树也分别是一个堆。堆排序主要包括两个过程：一是构建堆， 二是交换堆顶元素与最后一个元素的位置。
堆排序思想：
1. 将序列构造成一棵完全二叉树 ；
2. 把这棵普通的完全二叉树改造成堆，便可获取最小值 ；
3. 输出最小值 ；
4. 删除根结点，继续改造剩余树成堆，便可获取次小值 ；
5. 输出次小值 ；
6. 重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序 。
堆排序的特点：
稳 定 性：不稳定
时间复杂度：O(nlogn)
堆排序对记录较少的文件效果一般，但对于记录较多的文件很有效果，其运行时间主要耗费在创建堆与调整堆上
8.归并排序
利用递归与分治技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。
原理如下：对于给定的一组记录，首先将两个相邻的长度为1的子序列进行归并，得到n/2个长度为2或者1的有序子序列，在将其两两归并，反复执行此过程，直到得到一个有序的序列为止。
9.基数排序
基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。
主要分为两个过程：
(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
排序算法比较：
从平均情况看：堆排序、归并排序、快速排序胜过希尔排序。
从最好情况看：冒泡排序和直接插入排序更胜一筹。
从最差情况看：堆排序和归并排序强过快速排序。
虽然直接插入排序和冒泡排序速度比较慢，但是当初始序列整体或局部有序是，这两种算法的效率比较高。当初始序列整体或局部有序时，快速排序算法效率会下降。当排序序列较小且不要求稳定性是，直接排序效率较好；要求稳定性时，冒泡排序法效率较好