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

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;