排序
排序:是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程。关键字可以是记录的主关键字,也可以是次关键字或若干数据项的组合。
内部排序:在排序过程中,若整个数据表都是存放在内存中处理,排序时不涉及数据的内、外存交换。
外排序:排序过程中要进行数据的内、外存交换。
内部排序的分类:是否基于关键字的比较,分为基于比较的排序算法和不基于比较的排序。(插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法。基数排序是不基于比较的排序算法。)
算法的稳定性:如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,称这种排序方法是稳定的;反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。
正序:待排序记录的关键字顺序正好和要排序顺序相同。
反序:若待排序记录的关键字顺序正好和要排序顺序相反。
评价排序算法的标准:执行时间和所需的辅助空间,其次是算法的稳定性。时间是由比较和移动的次数之和确定的,两个记录的一次交换一般需要3次移动。
插入排序
插入排序:每一趟将一个待排序的记录,按其关键字值的大小插入到已经排序的部分文件中适当位置上,直到全部插入完成。
直接插入排序
直接插入排序:依次将每个记录插入到一个有序的序列中去。初始时,有序区只有一个元素R[0],i=1~n-1,共经过n-1趟排序。
代码实现:
// ------ 待排记录的数据类型--------
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
typedef struct { // 记录类型
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项,具体类型在主程中定义
} RedType;
typedef struct { // 顺序表类型
RedType r[MAXSIZE + 1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
} SqList;
void InsertSort(RedType R[], int n)
{
int i, j;
RedType tmp;
for (i=1;i<n;i++){ //从第二个元素即R[1]开始的
if (R[i-1].key>R[i].key){
tmp=R[i]; //取出无序区的第一个元素R[i]
j=i-1; //在R[0..i-1]中找R[i]的插入位置
do{
R[j+1]=R[j]; //将关键字大于tmp.key的元素后移
j--; //继续向前比较
} while (j>=0 && R[j].key>tmp.key);
R[j+1]=tmp; //在j+1处插入R[i]
}
}
}
//设置哨兵
void InsertSort(SqList &L)
{
// 对顺序表L作直接插入排序。算法10.1
int i, j;
for(i = 2; i <= L.length; ++i)
// <,需将L.r[i]插入有序子表
if (LT(L.r[i].key, L.r[i - 1].key)) {
L.r[0] = L.r[i]; // 复制为哨兵
for(j = i - 1; LT(L.r[0].key, L.r[j].key); --j)
L.r[j + 1] = L.r[j]; // 记录后移
L.r[j + 1] = L.r[0]; // 插入到正确位置
}
}
折半插入排序
折半插入排序:有序区的有序性。可以采用折半查找方法先在R[0..i-1]中找到插入位置,再通过移动记录进行插入。这样的插入排序称为折半插入排序或二分插入排序。折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变逐个移动为集中移动。
代码实现:
void binSort(RedType a[],int n)//按递增序进行二分法插入排序
{
int i,j,left,mid,right;
for (i=1;i<n;i++){
left=0;right=i-1; 循环寻找位置
while (left<=right){
mid=(left+right)/2;
if (a[i].key<a[mid].key)
right=mid-1;
else
left=mid+1;
}
for(j=i-1;j>=left;j--)
a[j+1]=a[j];//将排序大于ki 的记录后移插入
if(left!=i)
a[left]=a[i];
}
}
希尔排序
希尔排序:(缩小增量排序)先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序。然后取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
代码实现:
//取d1= n/2,di+1=⌊di/2⌋时
void ShellSort(RedType R[],int n)
{
int i,j,d;
RedType tmp;
d=n/2; //增量置初值
while (d>0){
for (i=d;i<n;i++){
tmp=R[i]; //对所有相隔d位置的记录组采用直接插入排序
j=i-d;
while (j>=0 && tmp.key<R[j].key){
R[j+d]=R[j];
j=j-d;
}
R[j+d]=tmp;
}
d=d/2; //减小增量
}
}
void ShellInsert(SqList &L, int dk)
{
// 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比,
// 作了以下修改:
// 1.前后记录位置的增量是dk,而不是1;
// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
int i, j;
for(i = dk + 1; i <= L.length; ++i)
if (LT(L.r[i].key, L.r[i - dk].key) ) {
// 需将L.r[i]插入有序增量子表
L.r[0] = L.r[i]; // 暂存在L.r[0]
for(j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
L.r[j + dk] = L.r[j]; // 记录后移,查找插入位置
L.r[j + dk] = L.r[0]; // 插入
}
}
交换排序
交换排序:交换排序是一类基于“交换”的排序,系统地交换反序的记录的偶对,直到不再有这样的偶对为止。交换排序的基本思路:两两比较待排序记录的关键字,并交换不满足次序要求的那些偶对,直到全部满足为止。
冒泡排序
冒泡排序:设待排序记录序列中的记录个数为n。最多作n-1 趟冒泡,i = 1, 2, 。。, n-1。在第i 趟中从后向前,j = n-1, n-2, 。。, i,顺次两两比较r[j-1].key和r[j].key。如果发生逆序,即r[j-1].key>r[j].key ,则交换r[j-1].key和r[j].key。
代码实现:
void BubbleSort(RedType R[],int n)
{
int i,j,exchange;
RedType tmp;
for(i=0;i<n-1;i++){
exchange=0; //本趟排序前置exchange为0
for (j=n-1;j>i;j--) //比较,找出最小关键字的记录
if(R[j].key<R[j-1].key){
tmp=R[j]; //R[j]与R[j-1]进行交换,
R[j]=R[j-1]; //将最小关键字记录前移
R[j-1]=tmp;
exchange=1; //本趟排序发生交换置exchange为1
}
if (exchange==0) //本趟未发生交换时结束算法
return;
}
}
快速排序
快速排序:找一个记录(例如取第一个记录) ,以它的关键字作为“枢轴”(基准);凡其关键字小于枢轴的记录均移动至该记录之前;凡其关键字大于枢轴的记录均移动至该记录之后。即对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行快速排序。
代码实现:
int Partition(SqList &L, int low, int high)
{
// 交换顺序表L中子表r[low..high]的记录,枢轴记录到位,并返回其
// 所在位置,此时在它之前(后)的记录均不大(小)于它。算法10.6(b)
KeyType pivotkey;
L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
pivotkey = L.r[low].key; // 枢轴记录关键字
while(low < high) {
// 从表的两端交替地向中间扫描
while(low < high && L.r[high].key >= pivotkey)
--high;
L.r[low] = L.r[high]; // 将比枢轴记录小的记录移到低端
while(low < high && L.r[low].key <= pivotkey)
++low;
L.r[high] = L.r[low]; // 将比枢轴记录大的记录移到高端
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; // 返回枢轴位置
}
void QSort(SqList &L, int low, int high)
{
// 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
int pivotloc;
if(low < high) { // 长度大于1
// 将L.r[low..high]一分为二
pivotloc = Partition(L, low, high);
// 对低子表递归排序,pivotloc是枢轴位置
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, high); // 对高子表递归排序
}
}
void QuickSort(SqList &L)
{
// 对顺序表L作快速排序。算法10.8
QSort(L, 1, L.length);
}
选择排序
选择排序:每一趟(例如第i 趟, i = 1, …, n-1) 在后面n-i+1 个待排序记录序列中选出关键字值最小的记录,作为有序记录序列的第i 个记录。待到第n-1 趟作完,待排序记录只剩下1 个, 就不用再选了。选择排序的每一趟可把有序区扩大,直到n-1趟后即可把有序区扩大到整个待排序序列。
简单选择排序
简单选择排序:在一组记录r[i]~r[n] 中选择具有最小关键字的记录;若它不是这组记录中的第一个记录,则将它与这组记录中的第一个记录对调;在这组记录中剔除这个具有最小关键字值的记录。在剩下的记录r[i+1]~r[n] 中重复执行前两步,直到剩余记录只有一个为止。
代码实现:
int SelectMinKey(SqList L, int i)
{
// 返回在L.r[i..L.length]中key最小的记录的序号
KeyType min;
int j, k;
k = i; // 设第i个为最小
min = L.r[i].key;
for(j = i + 1; j <= L.length; j++)
if(L.r[j].key < min) { // 找到更小的
k = j;
min = L.r[j].key;
}
return k;
}
void SelectSort(SqList &L)
{
// 对顺序表L作简单选择排序。算法10.9
int i, j;
RedType t;
for(i = 1; i < L.length; ++i) { //选择第i小的记录,并交换到位
// 在L.r[i..L.length]中选择key最小的记录
j = SelectMinKey(L, i);
if(i != j) { //与第i个记录交换
t = L.r[i];
L.r[i] = L.r[j];
L.r[j] = t;
}
}
}
树型排序
树型排序:又称锦标赛排序。对n 个记录的关键字进行两两比较,然后再[n/2]个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一棵有n 个叶子结点的完全二叉树表示。
堆排序
堆:若将该记录序列视作完全二叉树,则:r2i 是ri 的左孩子;r2i+1 是ri 的右孩子。
堆排序:对树型排序的进一步改进。是利用堆的特性对记录序列进行排序。堆排序采用堆结构选择最大(最小)元素。如果每个结点的关键字均大于等于其所有孩子结点的关键字,称为大根堆。如果每个结点的关键字均小于等于其所有孩子结点的关键字,称为小根堆。
- 从最后一个分支结点(编号为n/2)开始到根结点(编号为1)通过多次调用筛选算法建立初始堆。
- 将R[1](无序区中最大记录)与无序区最后一个记录交换,归位无序区最后一个记录,无序区减少一个记录。
- 再筛选,重复进行,直到无序区只有一个记录。
代码实现:
typedef SqList HeapType; // 堆采用顺序表存储表示
//调整堆
void HeapAdjust(HeapType &H, int s, int m)
{
// 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数
// RedType rc;调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)。算法10.10
int j;
rc = H.r[s];
for(j = 2 * s; j <= m; j *= 2) {
// 沿key较大的孩子结点向下筛选
if(j < m && LT(H.r[j].key, H.r[j + 1].key))
++j; // j为key较大的记录的下标
if(!LT(rc.key, H.r[j].key))
break; // rc应插入在位置s上
H.r[s] = H.r[j];
s = j;
}
H.r[s] = rc; // 插入
}
void HeapSort(HeapType &H)
{
// 对顺序表H进行堆排序。算法10.11
RedType t;
int i;
// 把H.r[1..H.length]建成大顶堆
for(i = H.length / 2; i > 0; --i)
HeapAdjust(H, i, H.length);
// 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
for(i = H.length; i > 1; --i) {
t = H.r[1];
H.r[1] = H.r[i];
H.r[i] = t;
HeapAdjust(H, 1, i - 1); // 将H.r[1..i-1]重新调整为大顶堆
}
}
归并排序
归并排序:通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。多次将两个或两个以上的有序表合并成一个新的有序表。通常采用的是2-路归并排序。即:将两个位置相邻的记录有序子序列归并为一个记录的有序序列。
代码实现:
void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{
// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12
int j, k, l;
// 将SR中记录由小到大地并入TR
for(j = m + 1, k = i; i <= m && j <= n; ++k)
if LQ(SR[i].key, SR[j].key)
TR[k] = SR[i++];
else
TR[k] = SR[j++];
if(i <= m)
for(l = 0; l <= m - i; l++)
TR[k + l] = SR[i + l]; // 将剩余的SR[i..m]复制到TR
if(j <= n)
for(l = 0; l <= n - j; l++)
TR[k + l] = SR[j + l]; // 将剩余的SR[j..n]复制到TR
}
void MSort(RedType SR[], RedType TR1[], int s, int t)
{
// 将SR[s..t]归并排序为TR1[s..t]。算法10.13
int m;
RedType TR2[MAX_SIZE + 1];
if(s == t)
TR1[s] = SR[s];
else {
m = (s + t) / 2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
// 递归地将SR[s..m]归并为有序的TR2[s..m]
MSort(SR, TR2, s, m);
// 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
MSort(SR, TR2, m + 1, t);
// 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
Merge(TR2, TR1, s, m, t);
}
}
void MergeSort(SqList &L)
{
// 对顺序表L作归并排序。算法10.14
MSort(L.r, L.r, 1, L.length);
}
基数排序
基数排序:采用“分配”与“收集”的办法,用对多关键字进行排序的思想实现对单关键字进行排序的方法。
两种常用方法:最高位优先MSD (Most Significant Digit first )、最低位优先LSD (Least Significant Digit first)
最高位优先法:
- 先根据最高位关键字K1排序, 得到若干元素组,元素组中各元素都有相同关键字K1。
- 再分别对每组中元素根据关键字K2 进行排序,按K2 值的不同, 再分成若干个更小的子组, 每个子组中的元素具有相同的K1和K2值。
- 依此重复, 直到对关键字Kd完成排序为止。
- 最后, 把所有子组中的元素依次连接起来,就得到一个有序的元素序列。
最低位优先法:
- 首先依据最低位关键字Kd对所有元素进行一趟排序;再依据次低位关键字Kd-1对上一趟排序的结果再排序,依次重复,直到依据关键字K1最后一趟排序完成,就可以得到一个有序的序列。
- 这种排序方法对每个关键字进行排序时,不需要再分组,而是整个元素组都参加排序。
链式基数排序:是典型的LSD排序方法, 利用“分配”和“收集”对单关键字进行排序。在这种方法中,把单关键字Ki 看成是一个d 元组。其中的每一个分量也可看成是一个关键字。分量有radix 种取值, 称radix 为基数。基数排序以静态链表作为它们的存储结构。
代码实现:
typedef struct node{
int key;
anytype data;
int *next;
}List_Node;
List_Node *radixsort( List_Node *h,int d,int r)
{
n=10; m=1;
for(i=1; i<=d;i++){ //共“分配”、“收集”d 次
for(j=0;j<=9;j++){ //初始化队列
f[j]=NULL;t[j]=NULL;
}
p=h;
while(p) {
k=p->key%n/m // “分离”
if(f[k]==NULL) f[k]=p; //入队
else t[k]->next=p;
t[k]=p;
p=p->next; //从单链表中获取下一个结点
}
m=m*10; n=n*10;
h=NULL; p=NULL; //“收集”
for(j=0;j<r;j++)
if (f[j]) {
if (!h) {
h=f[j];
p =t[j];
}else {
p->next=f[j];p=t[j];
}
}
}
return(h);
}
时间复杂度 | |||||
---|---|---|---|---|---|
最好情况 | 最坏情况 | 平均情况 | 空间复杂度 | 稳定性 | |
直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
折半插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
希尔排序 | O(n2/3) | O(1) | 不稳定 | ||
冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n) | 不稳定 |
简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 稳定 |
总结:
- 就平均时间性能而言,快速排序最佳。但在最坏情况下不如堆排序和归并排序。(归并排序对n较大时适用)
- 当序列中的记录“基本有序”或n 值较小时,直接插入排序是最佳的方法,因此常将它与其他排序方法结合使用,如快速排序、归并排序等。
- 基数排序的时间复杂度也可写成O(d*n),因此它最适用于n 值很大而关键字较小的序列。
- 稳定的排序方法:基数排序、简单排序。
- 不稳定的排序方法:快速排序、堆排序、希尔排序(时间性能较好)。
留言