当前位置:   article > 正文

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

利用随机函数产生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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/839086
推荐阅读
相关标签
  

闽ICP备14008679号