排序

定义：排序是计算机内经常进行的一种操作，其目的是将一组无序的数组元素调整为有序的数组元素。假设含n个数据元素的序列为{R1，R2，…,Rn}其相应的关键字序列为{K1，K2，….,Kn}z这些关键字相互之间可以进行比较，存在这样一个关系Kp1<=Kp2<=…<=Kpn按此固有关系将上式记录序列重新排列为{Rp1，Rp2，…,Rpn}

的操作称作排序。

稳定性：如果在序列中有两个数据元素r[i]和r[j]他们的关键字k[i]=k[j],且在排序之前对象r[i]在r[j]的前面，排序后对象r[i]仍在r[j]的前面，称这个排序方法是稳定的。

关键操作：比较、交换

多关键字排序：只要在比较操作时同时考虑多个关键字即可，与单关键字无本质区别

分类：

内排序-整个排序过程不需要访问外存便能完成。

外排序-待排序的数据元素数量很大，整个序列的排序过程不可能在内存中完成。

审判：

时间性能-关键性能差异体现在比较和交换的数量；

辅助存储空间-为完成排序操作需要额外的存储空间必要时可以空间换时间；

算法的实现复杂性-过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能。

方法：

选择排序：每一趟（例如第i趟）在后面n-i个待排的数据元素中选出关键字最小的元素，作为有序元素序列的第i个元素。从第0趟开始。

插入排序：当插入第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].

上面这3种算法时间复杂度为O（n*n）,排序结果稳定。

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

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

归并排序：将两个或两个以上的有序序列合并成一个新的有序序列（2路归并、3路归并、多路归并）当i和j都在两个序列内变化时，根据关键码的大小将较小的数据元素排放到新序列k所指的位置中，当i与j有一个已经超出序列时，将另一个序列中的剩余部分照抄到新序列中。

上面3种排序复杂度提高到了O(n*logn),除归并排序结果稳定之外其他不稳定。