数据结构---排序的基本概念和分类

排序的定义

假设含有n个记录的序列为{$r_1$,$r_2$,…,$r_n$}，其相应的关键字分别为{$k_1$,$k_2$,…,$k_n$}，需确定1,2, 3, …, n的一种排列$p_1$,$k_p$,…,$p_n$，使其相应的关键字满足$k_{p1}$ ≤$k_{p2}$≤…≤$k_{pn}$非递减（或非递增）关系，即使得序列变成一个按关键字有序的序列{$r_{p1}$,$r_{p2}$,…,$r_{pn}$}

    在排序问题中，通常将数据元素称为记录，所以说可以把排序看成是线性表的一种操作。
    排序的依据是关键字之间的大小关系，那么对于同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。

排序的稳定性

假设$k_i$=$k_j$（1≤i≤n, 1≤j≤n,i≠j），且在排序前的序列中$r_i$领先$r_j$（即i < j）。如果排序后$r_i$仍然领先$r_j$，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中$r_j$领先$r_i$，则称所用的排序方法是不稳定的。

编号	姓名	总分
1	令狐冲	753
2	郭靖	573
3	杨过	682
4	张无忌	753

稳定排序：

编号	姓名	总分
1	令狐冲	753
4	张无忌	753
3	杨过	682
2	郭靖	573

不稳定排序：

编号	姓名	总分
4	张无忌	753
1	令狐冲	753
3	杨过	682
2	郭靖	573

排序的分类

    根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为：内排和外排
    内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序，排序算法性能主要受：

• 时间性能
• 辅助空间
• 算法复杂性(指算法本身的复杂性)