七、排序算法

一、排序的概念与分类

排序的一般定义

 排序是计算机内经常进行的一种操作 ， 其目的是将一组“ 无序” 的数据元素调整为“ 有序” 的数据元素。

例如 ： 将下列关键字序列
52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

排序的数学定义
 假设含有n个数据元素的序列为{R1 , R2 , …, Rn },其相应的关键字序列为{ K1 , K2 , …, Kn }，这些关键字相互之间可以进行比较 ， 即在它们之间存在着这样一个关系：
Kp1 <= Kp2 <= …<=Kpn
按此固有关系将上式记录序列重新排列为
{ R p1 , R p2 , … ，R pn }
的操作称作 排序 。
排序的稳定性
如果在序列中有两个数据元素r[i]和r[j]，它们的关键字k[i ] ==k[j]，且在排序之前，对象r[i]排在r[j]。 如果在排序之后 ， 对象r[i]仍在对象r[j]的前面， 则称这个排序方法是稳定的。
多关键字排序

排序时需要比较的关键字多余一个
排序结果首先按关键字 1 进行排序
当关键字 1 相同时按关键字 2 进行排序
……
当关键字 n-1 相同时按关键字 n 进行排序

排序中的关键操作

比较：任意两个数据元素通过比较操作确定先后次序
交换： 数据元素之间需要交换才能得到预期结果

内排序和外排序

内排序：整个排序过程不需要访问外存便能完成
外排序：待排序的数据元素数量很大 ， 整个序列的排序过程不可能在内存中完成

排序的审判

时间性能：关键性能差异体现在比较和交换的数量
辅助存储空间：为完成排序操作需要的额外的存储空间；必要时可以“ 空间换时间”
算法的实现复杂性：过于复杂的排序法会影响代码的可读性和可维护性 ， 也可能影响排序的性能

二、基本的排序算法

选择排序
每一趟 ( 例如第i趟 ， i = 0, 1, … , n- 2)在后面n-i 个待排的数据元素中选出关键字最小的元素 , 作为有序元素序列的第 i 个元素。

插入排序
当插入第i(i>=1)个数据元素时，前面的V[0], V[1], … , V[i-1]已经排好序 。 这时 ,用 V[i]的关键字与 V[i-1], V[i-2], … 的关键字进行比较 , 找到插入位置即将 V[i]插入 , 原来位置上的对象向后顺移。

冒泡排序
设待排数据元素序列中的元素个数为 n。最多作 n-1趟，i = 1, 2, … … , n-1。在第 i 趟中从后向前， j = n-1, n-2, … … , i， 两两比较 V[j-1] 和 V[j]的关键字。如果发生逆序， 则交换 V[j-1] 和 V[j]。

希尔排序
将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。

将n个数据元素分为d个子序列：
{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}
{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}
...
{R[d]，R[2+d]，R[3+2d]，…，R[(k+1)d]}

其中,d称为增量，它的值在排序过程中从大到小逐渐缩小,直至最后一趟排序减为1.

快速排序
1) 任取待排序序列中的某个数据元素( 例如： 第一个元素) 作为基准, , 按照该元素的关键字大小将整个序列划分为左右两个子序列：
 左侧子序列中所有元素都小于或等于基准元素
 右侧子序列中所有元素都大于基准元素
 基准元素排在这两个子序列中间
2) 分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止 。

归并排序
将两个或两个以上的有序序列合并成一个新的有序序列
V[1] … V[m]和V[ m +1] … V[n] -------------------> V[1] … V[n]
这种归并方法称为2路归并。

总结：
希尔排序 ， 快速排序和归并排序将排序算法的时间复杂度提高到了 O(n*logn)
希尔排序和快速排序的排序结果是不稳定的
算法实现源码