排序及其相关的数据结构

排序（Sorting）是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。

排序的稳定性

当排序记录中的关键字Ki（i = 1, 2, …, n）都不相同时，则任何一个记录的无序序列经排序 后得到的结果唯一；反之，当待排序的序列中存在两个或两个以上关键字相等的记录时，则排 序所得的结果不唯一。假设Ki = Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj ，（即i<j），若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使 排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。

排序的分类

  • （1）插入类：将无序子序列中的一个或几个记录插入有序序列，从而增加记录的有序子序 列的长度。主要包括直接插入排序、折半插入排序和希尔排序。
  • （2）交换类：通过交换无序序列中的记录从而得到其中关键字最小或最大的记录，并 将它加入有序子序列中，以此方法增加记录的有序子序列的长度。主要包括冒泡排序和快速 排序。
  • （3）选择类：从记录的无序子序列中选择关键字最小或最大的记录，并将它加入有序子 序列中，以此方法增加记录的有序子序列的长度。主要包括简单选择排序、树形选择排序和堆 排序。
  • （4）归并类：通过归并两个或两个以上的记录有序子序列，逐步增加记录有序序列的长 度。2-路归并排序是最为常见的归并排序方法。
  • （5）分配类：是唯一一类不需要进行关键字比较的排序方法，排序时主要利用分配和收集 两种基本操作来完成。基数排序是主要的分配排序方法。

待排序记录的存储方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAXSIZE 20
#define EQ(a,b) ((a)==(b))
#define LT(a, b) ((a) < (b))
#define LQ(a,b) ((a)<=(b))


typedef int KeyType; //关键字类型为整型
typedef char InfoType; //关键字所含有的其他信息类型，这里定义为字符

typedef struct {
	KeyType key;
	InfoType* info;
}RedType;

typedef struct {
	RedType r[MAXSIZE + 1];//r[0]作为闲置或者哨兵单元
	int length;//顺序表长度
}SqList;

插入排序

插入排序的方法是，先假定第一个元素是“有序”的，然后依次将第二个元素插入前面“有序”的序列中，在此过程中，可以用哨兵单元暂存需要插入的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(SqList* list){
    for(int i=2;i<=list.length;++i){ //注意从2开始，且是++i
        if(LT(list->r[i]->key,list-r[i-1]->key)){ //如果前大后小
            list->r[0]->key=list->r[i]->key; //将这个关键字存入哨兵单元
            list->r[i]->key=list->r[i-1]->key； //将其后移
        }
       int j=i-2;
        for(j=i-2;j>=0&&LT( list->r[0]->key, list->r[j]->key),--j){
            list->r[j+1]->key=list->r[j]->key;
        }
        list->r[j+1]->key=list->r[0]->key;
    }
}