C语言数据结构--排序之直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序和堆排序_利用随机函数产生50000个随机整数,分别用插入排序、希尔排序、起泡排序、选择排序

代码前面的声明：

#include <stdio.h>
#include <stdlib.h>
#include <time.h> //顺序表我是随机生成的伪随机数，引入time.h头文件

#define MAXSIZE 20 //顺序表的最大长度
#define EQ(a,b) ((a) == (b)) //a = b
#define LT(a,b) ((a) < (b))//a<b
#define LQ(a,b) ((a) <= (b))/a<=b
/*
字符串型关键字的比较
#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b)) < 0)
#define LQ(a,b) (strcmp((a),(b)) <= 0)
*/

typedef int KeyType;//设置关键字类型为整数类型
typedef char InfoType;

typedef struct{
	KeyType key;             //关键字项
	InfoType otherinfo;      //其它数据项
}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
14
15
16
17
18
19
20
21
22
23
24
25
26
27

首先创建顺序表，这里生成了20个伪随机数构成顺序表

SqList *CreateSqList(SqList *S){
	S = (SqList *)malloc((MAXSIZE+1)*sizeof(SqList));
	//生成20个伪随机数
	long t = time(NULL); //产生一个'随机'数
	srand(time(NULL));
	for(int i=1; i<=20; i++){
		S->r[i].key = rand() % 100;  //将'随机数'范围控制在0~100
	}
	S->length = 20;
	return S;
}
1
2
3
4
5
6
7
8
9
10
11

直接插入排序：

//直接插入排序
void InsertSort(SqList *L){
	for(int i=2; i<= L->length; ++i){
		if(LT(L->r[i].key,L->r[i-1].key)){//如果后一个元素比前一个元素小
			L->r[0] = L->r[i];     //复制为哨兵
			L->r[i] = L->r[i-1];   //交换位置
			for(int j=i-2; LT(L->r[0].key ,L->r[j].key); --j){
				L->r[j+1] = L->r[j];//再交换位置
			}
			L->r[j+1] = L->r[0];//插入元素，因为L-r[i].key > L->r[j].key,所以插入在 j+1的位置
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

希尔排序
希尔排序又称“缩小增量排序”
基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
就是多次执行增量逐渐减小的直接插入排序

//希尔排序
void ShellInsert(SqList *L, int dk){//dk是增量
	for(int i=dk+1;i<=L->length; i++){
		if(LT(L->r[i].key, L->r[i-dk].key)){//如果后面的数比前面小
			L->r[0] = L->r[i];      //L->r[i]的值暂存再L->r[0]中
			for(int j=i-dk; j>0&&
1
2
3
4
5