数据结构（C语言）直接插入排序、冒泡法排序、选择排序_用c语言实现顺序表l的直接插入排序,并输出每一趟结果的代码

7-1 直接插入排序

给定一个整数序列，请按非递减序输出采用直接插入排序的各趟排序后的结果。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。

输出格式:

对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。

输入样例:

4
8 7 2 1

输出样例:

7 8 2 1
2 7 8 1
1 2 7 8

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include <stdio.h>
#include <stdlib.h>
 
#define MAXSIZE 20
typedef struct
{
    int key;
} RedType;
 
typedef struct
{
    int r[MAXSIZE+1];
    int length;
} SqList;
 
 
int InsertSort(SqList* L)
{
    int i, j;
    for(i = 2; i <= L->length; i++)
    {
        if(L->r[i] < L->r[i-1])
        {
            L->r[0] = L->r[i];
            L->r[i] = L->r[i-1];
            for(j = i-2; L->r[0] < L->r[j]; j--)
            {
                L->r[j+1] = L->r[j];
            }
            L->r[j+1] = L->r[0];
        }
        for(int k = 1; k <= L->length; k++)
        {
            if(k == L->length)
                printf("%d", L->r[k]);
            else
                printf("%d ", L->r[k]);
        }
        printf("\n");
    }
    return 1;
}
 
 
int main()
{
    SqList L;
 
    int n;
    while(scanf("%d", &n) != -1)
    {
        L.length = n;
 
        for(int i = 1; i <= L.length; i++)
        {
            scanf("%d", &L.r[i]);
        }
        L.r[0] = -1;
 
 
 
        InsertSort(&L);
 
    }
 
    return 0;
}

 

7-2 冒泡法排序

将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。

本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。

输入格式：

输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。

输出格式：

在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。

输入样例：

6 2
2 3 5 1 6 4

输出样例：

2 1 3 4 5 6

代码长度限制

16 KB

时间限制

400 ms

内存限制 

64 MB

#include <stdio.h>
#include <stdlib.h>
 
#define MAXSIZE 200
typedef struct
{
    int key;
} RedType;
 
typedef struct
{
    int r[MAXSIZE+1];
    int length;
} SqList;
 
 
void BubbleSort(SqList *L, int k)
{
    int m = L->length-1;
    int flag = 1, j;
    while((m>0) && flag == 1)
    {
        flag = 0;
        for(j = 1; j <= m; j++)
        {
            if(L->r[j] > L->r[j+1])
            {
                flag = 1;
                int t = L->r[j];
                L->r[j] = L->r[j+1];
                L->r[j+1] = t;
            }
        }
        k--;
        if(k == 0)
        {
            for(int i = 1; i <= L->length; i++)
            {
                if(i == L->length)
                    printf("%d", L->r[i]);
                else
                    printf("%d ", L->r[i]);
            }
        }
        m--;
    }
}
 
int main()
{
    SqList L;
 
    int n, k;
    scanf("%d %d", &n, &k);
 
    L.length = n;
 
    for(int i = 1; i <= L.length; i++)
    {
        scanf("%d", &L.r[i]);
    }
 
    BubbleSort(&L, k);
 
    return 0;
}

 

7-3 选择排序

本题要求从键盘读入n个整数，对这些数做选择排序。输出选择排序每一步的结果和最终结果。

输入格式:

输入的第一行是一个正整数n，表示 在第二行中会有n个整数。

输出格式:

输出选择排序每一步的结果和最终结果。

输入样例:

在这里给出一组输入。例如：

5
3 7 2 9 1

输出样例:

在这里给出相应的输出。例如：

step 1: 1 7 2 9 3 
step 2: 1 2 7 9 3 
step 3: 1 2 3 9 7 
step 4: 1 2 3 7 9 
sorted array: 1 2 3 7 9 

注意：

输出的冒号 : 是英文输入法下的符号，冒号后有一个空格。每个整数后有一个空格。

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

 

#include <stdio.h>
#include <stdlib.h>
 
#define MAXSIZE 20
typedef struct
{
    int key;
} RedType;
 
typedef struct
{
    int r[MAXSIZE+1];
    int length;
} SqList;
 
 
void SelectSort(SqList *L)
{
    int i, j, k, t;
    for(i = 1; i <= L->length; i++)
    {
        k = i;
        for(j = i+1; j <= L->length; j++)
        {
            if(L->r[j] < L->r[k])
                k = j;
 
        }
        if(k != i)
        {
            t = L->r[i];
            L->r[i] = L->r[k];
            L->r[k] = t;
        }
        if(i != L->length)
            printf("step %d: ", i);
        else
            printf("sorted array: ");
        for(int s = 1; s <= L->length; s++)
        {
            printf("%d ", L->r[s]);
        }
        printf("\n");
    }
}
 
 
 
int main()
{
    SqList L;
 
    int n;
    scanf("%d", &n);
 
    L.length = n;
 
    for(int i = 1; i <= L.length; i++)
    {
        scanf("%d", &L.r[i]);
    }
 
    SelectSort(&L);
 
    return 0;
}