欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言学习历程(十七)数据结构与排序(冒泡、选择、希尔排序)算法

程序员文章站 2022-07-15 08:47:05
...

include

define MAXSIZE 10

typedef struct SqList
{
int data[MAXSIZE+1]; /设置一个哨兵data【0】/
int length;
}SqList;

int swap(SqList L,int i,int j) /交换函数*/
{
int t = L -> data[i];
L -> data[i] = L -> data[j];
L -> data[j] = t;
}

int Bubblesort(SqList L) /冒泡排序初级*/
{
int i,j;
for(i = 1; i < L -> length;i++) /i只需要比较到倒数第二个/
{
for(j = i + 1;i <= L -> length;j++) /j从i之后开始比较/
{
if(L -> data[i] > L -> data[j]) /最终把最小值交换到第i个/
swap(L,i,j);
}
}
return 0;
}

int Bubblesort1(SqList L) /冒泡排序正宗*/
{
int i,j;
for(i = 1;i < L -> length;i++) /i从1走到倒数第二个/
{
for(j = L -> length;j > i;j–) /j从最后一个倒序比较/
if(L -> data[j] > L -> data[j-1]) /两个两个相比较/
swap(L,i,j); /每次把小的值放到前面/
}
return 0;
}

int Bubblesort2(SqList L) /顺序表冒泡排序优化版*/
{
int i,j;
int f = 1;
for(i = 1;i < L -> length;i++)
{
f = 0;
for(j = L -> length;j > i;j–) /j从最后往前面走/
{
if(L -> data[j] > L -> data[j -1])
swap(L,i,j);
f = 1; /全部按顺序时自动中断/
}
}
}

int Selectsort(SqList *L)
{
int i,j,min;
for(i = 1;i < L -> length ; i++ )
{
min = i; /设置min初始值为i=1/
for(j = i + 1;j <= L -> length; j++)
{
if(L -> data[i] > L -> data[j])
min = j; /将元素值更小的元素下标交换给min/
}
if(min != i) /判断原本的第i个是否为最小值/
swap(L,i,min); /将值最小的元素传到最前面/
}

}

int Insertsort(SqList L) /直接插入排序,需要哨兵*/
{
int i,j;
for(i = 2;i <= L -> length;i++)
{
if(L -> data[i] < L -> data[i-1]) /后一个与前一个比较/
{
L -> data[0] = L -> data[i]; /设置哨兵为当前较小值/
for(j = i - 1;L -> data[j] > L -> data[0];j–)
{
L -> data[j+1] = L -> data[j]; /* 将[i]之前的元素后移一位*/
}
L -> data[j+1] = L -> data[0]; /把最小值哨兵放在第一位/
}
}
return 0;
}

int Shellsort(SqList *L)
{
int i,j;
int increment = L -> length;
do
{
increment = increment/3 + 1; /较优化的数据选择,增量序列/
for(i = increment + 1;i <= L -> length;i++)
{
if(L -> data[i] < L -> data[i - increment]) /隔increment个比较前后的大小/
L -> data[0] = L -> data[i]; /将后面的更小的元素赋给哨兵/
for(j = i-increment;j>0 && L->data[0]data[j];j-=increment)
L -> data[j+increment] = L -> data[j]; /值大的元素后移/
L->data[j + increment] = L->data[0]; /哨兵中的更小值放到前面/
}
}while(increment > 1);

}

int main()
{
SqList L;
char a;
L.data[11] = {0,5,4,23,4,56,4,5,4,3,4};
L.length = MAXSIZE;

printf("************冒泡排序初级版,请输入a**************\n");
printf("************冒泡排序正宗版,请输入b**************\n");
printf("************冒泡排序顺序表,请输入c**************\n");
printf("************简单的选择排序,请输入d**************\n");
printf("************直接插入排序法,请输入e**************\n");
printf("************实现希尔排序法,请输入f**************\n");
printf("请输入你想实现的功能:");
scanf("%c",&a);  getchar();

while(a != '0')
{
    switch(a)
    {
        case 'a' : Bubblesort(&L)  ; break;
        case 'b' : Bubblesort1(&L) ; break;
        case 'c' : Bubblesort2(&L) ; break;
        case 'd' : Selectsort(&L)  ; break;
        case 'e' : Insersort(&L)   ; break;
        case 'f' : Shellsort(&L)   ; break;
        default  : printf("输入有误") ; break;
    }
    printf("请输入你想继续实现的功能:");
    scanf("%c",&a); getchar();
}

return 0;