``````#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int  Position;
typedef int  ElemType;
typedef int Status;
int compare1=0,compare2=0,compare3=0,compare4=0,compare5=0,compare6=0;//比较次数
int move1 = 0, move2 = 0, move3 = 0, move4 = 0, move5 = 0, move6 = 0;//移动次数
ElemType*p, *q;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1;
#define TRUE 1;
#define FALSE 0;
#define ERROR 0;
#define OVERFLOW -2;
/*①SqList.h线性表的动态分配顺序存储结构*/
typedef struct
{
int key;
}lkey;
typedef  struct
{
lkey *elem;
int length;
int listsize;
}SqList;

/*②顺序表基本操作接口定义*/
//操作结果：构造一个空的线性表
Status InitList_Sq(SqList &L);
//操作结果：在L中第i个元素之前插入新的元素e,L的长度加1
Status ListInsert_Sq(SqList &L, int i, ElemType e);
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType));
//将元素e的值打印出来
Status visit_sp(ElemType e);
//直接插入排序
void InsertSort(SqList L);
//希尔排序
void ShellSort(SqList L, int dlta[], int t);
void Shell(SqList L, int dk);//一趟希尔插入排序
//起泡排序
void BubbleSort(SqList L);
//快速排序
void QuickSort(SqList L);
void Quick(SqList L, int low, int high);
int QsortPartion(SqList L, int low, int high);//一趟快速排序
//简单选择排序
void SelectSort(SqList L);
//堆排序
void HeapSort(SqList L);
void HeapAdjust(SqList L, int s, int m);//建大顶堆函数

//随机生成数构造线性表
Status InitList_Sq(SqList &L)
{
int i;
L.elem = (lkey*)malloc(LIST_INIT_SIZE * sizeof(lkey));
if (!L.elem)exit(-2);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
//srand((unsigned)time(NULL));
for (i = 1; i < 15; i++)
{
L.elem[i].key = rand() % 100 + 1;
ListInsert_Sq(L, i, L.elem[i].key);
}
return OK;
/*请参考课本上的算法2.3*/
}
//在L中第i个元素之前插入新的元素e,L的长度加1
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
if (i<1 || i>L.length + 1)
return ERROR;
if (L.length >= L.listsize)
{
lkey*newbase = (lkey*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(lkey));
if (!newbase)return ERROR;
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i - 1].key);
for (p = &(L.elem[L.length - 1].key); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
/*请参考课本上的算法2.4*/
}
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType))
{
int i;
for (i = 1; i <= L.length; i++)
(*visit)(L.elem[i - 1].key);
printf("\n");
return OK;
}
//将元素e的值打印出来
Status visit_sp(ElemType e)
{
printf("%d  ", e);
return OK;
}

//直接插入排序
void InsertSort(SqList L)
{
int compare1 = 0, move1 = 0;
int i=0, j=0;
lkey rc;
for (i = 1; i<L.length; ++i)//从第二个开始
{
compare1++;
if (L.elem[i].key < L.elem[i - 1].key)
{
move1 += 2;
rc = L.elem[i];
L.elem[i] = L.elem[i - 1];
for (j = i - 2; j >= 0 && rc.key < L.elem[j].key; --j)//从i-2个开始
{
compare1++;
L.elem[j + 1] = L.elem[j];
move1++;
}
L.elem[j + 1] = rc;
move1 += 3;
}
}
ListTraverse_Sq(L,visit_sp);
printf("%d %d\n", compare1, move1);
}

//希尔排序
void ShellSort(SqList L, int dlta[], int t)
{
ListTraverse_Sq(L, visit_sp);
int k;
for (k = 0; k < t; k++)
Shell(L, dlta[k]);
ListTraverse_Sq(L, visit_sp);
printf("%d %d\n", compare2, move2);
}
void Shell(SqList L, int dk)//一趟希尔插入排序
{
lkey rc;
int j;
for (int i = dk; i < L.length; i++)
{
compare2++;
if (L.elem[i].key < L.elem[i - dk].key)//比较i和i-dk
{
rc = L.elem[i];
move2++;
for (j = i - dk; j >= 0 && (rc.key < L.elem[j].key); j -= dk)//[6]和[3]，[0]比较
{
compare2++;
L.elem[j + dk] = L.elem[j];//记录后移，查找插入位置
move2++;
}
L.elem[j + dk] = rc;//插入
move2++;
}
}
}
int main()
{
SqList L;
int i;
int dita[3] = { 5,3,1 }, t = 3;
for (i = 0; i <= 5; i++)
{
printf("当前随机数为：\n");
InitList_Sq(L);
ListTraverse_Sq(L, visit_sp);
InsertSort(L);
ShellSort(L, dita, t);
//BubbleSort(L);
//QuickSort(L);
//SelectSort(L);
//HeapSort(L);
/*printf("------|-比较次数-||-移动次数-|\n");
printf("Insert|   %d     ||   %d     |\n", compare1, move1);
printf("Shell |   %d     ||   %d     |\n", compare2, move2);
printf("Bubble|   %d     ||   %d     |\n", compare3, move3);
printf("Quick |   %d     ||   %d     |\n", compare4, move4);
printf("Select|   %d     ||   %d     |\n", compare5, move5);
printf("Heap  |   %d     ||   %d     |\n", compare6, move6);*/
}
system("pause");
return 0;
}
``````

1个回答

2 个月之前 回复