十大排序

2021.11.09 默认分类 12 评

冒泡排序

/*本程序演示 冒泡排序 */

/*是否稳定？ 稳定！*/
#include<stdlib.h>
#include<stdio.h>
int main()
{
    int a[10];
    int n = sizeof(a)/sizeof(a[0]);
    printf("请输入十个数值:\n");
    for(int i = 0;i<n;i++)
    {
        printf("第%d个：",i);
        scanf("%d", &a[i]);
    }
    printf("排列之前的顺序为：\n");
    for (int length=0;length<n;length++)
    {
        printf("%3d",a[length]);
    }

     for (int j=0; j<n-1; j++)  //比较n-1轮  取两数相互排序依次递进 0-（n-1）,
    {
        for (int k=0; k<n-1-j; k++)  //每轮比较n-1-i次,  
        {
           
            if (a[k] > a[k+1]) //从小到大
            {
                int temp = a[k];
                a[k] = a[k+1];
                a[k+1] = temp;
            }
        }
     }

    printf("\n排序后的结果为\n");
    for (int len=0;len<n;len++)
    {
        printf("%3d",a[len]);
    }
    return 0;
}

选择排序

/*本程序演示 选择排序  */

/* 是否稳定？ */
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int a[10];
    int n = sizeof(a)/sizeof(a[0]);
    int num = n;
    int i=0;
    printf("请您输入排列的数：\n");
    while ( scanf("%d",&a[i]) && num >1)  //循环向数组中存入数
    {
        i++;
        num--;
    }
    printf("排列之前的顺序为：");
    for (int length=0;length<n;length++)
    {
        printf("%3d",a[length]);
    }

    for(int i = 0;i<n;i++)      // 取一数当最小 每轮进行比较 较小者置换；互换于前列！
    {
        int min = i;
        for(int j = i;j<n;j++)
        {
            if(a[j]<a[min])
            {
                min = j;
            }
        }
        int T = a[min];  // 比较置换过程！
        a[min] = a[i];
        a[i] = T;
    }

    printf("\n排序后的值为:\n");
    for (int len = 0; len < n; len++)
    {
        printf("%d",a[len]);
    }
    return 0;

}

快速排序

/*本程序演示 快速排序（冒泡排序的改进） */
#include<stdio.h>
#include<stdlib.h>
void display(int* a, int n) {
   printf("\n排序后的值为:\n");
        for (int len = 0; len < n; len++)
        {
            printf("%3d",a[len]);
        }
}
int getStandard(int a[], int i, int j) {
    // 基准数据
    int key = a[i];
    while (i < j) {
        // 因为默认基准是从左边开始，所以从右边开始比较
        // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
        while (i < j && a[j] >= key) {
            j--;
        }
        // 当找到比 a[i] 小的时，就把后面的值 a[j] 赋给它
        if (i < j) {
            a[i] = a[j];
        }
        // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
        while (i < j && a[i] <= key) {
            i++;
        }
        // 当找到比 a[j] 大的时，就把前面的值 a[i] 赋给它
        if (i < j) {
            a[j] = a[i];
        }
    }
    // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
    // 把基准数据赋给正确位置
    a[i] = key;
    return i;
}

void QuickSort(int a[], int low, int high) {
    // 开始默认基准为 low
    if (low < high) {
        // 分段位置下标
        int standard = getStandard(a, low, high);
        // 递归调用排序
        // 左边排序
        QuickSort(a, low, standard - 1);
        // 右边排序
        QuickSort(a, standard + 1, high);
    }
}

int main()
{
    int a[10];
    int n = sizeof(a)/sizeof(a[0]);
    int num = n;
    int i=0;
    printf("请您输入排列的十位数：\n");
    while ( scanf("%d",&a[i]) && num >1)  //循环向数组中存入数
    {
        i++;
        num--;
    }
    printf("排列之前的顺序为：");
    for (int length=0;length<n;length++)
    {
        printf("%3d",a[length]);
    }

    QuickSort(a, 0, n - 1);
    display(a, n);
}

希尔排序

/*本程序演示 希尔排序(缩小增量排序)  */
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int a[10];
    int n = sizeof(a)/sizeof(a[0]);
    int num = n;
    int i=0;
    printf("请您输入排列的数：\n");
    while ( scanf("%d",&a[i]) && num >1)  //循环向数组中存入数
    {
        i++;
        num--;
    }
    printf("排列之前的顺序为：");
    for (int length=0;length<n;length++)
    {
        printf("%3d",a[length]);
    }

    int temp;         // 假定一个区间ii; 将数组割分为k个区间ii；每个区间内排序;不断缩小区间ii--;
    int ii = n/2;    //增量为整数
    while(ii>0)
    {
        for(int i = ii;i<n;i++)
        {
            temp = a[i];
            int m = i-ii;
            while (m>=0 && temp<a[m])
            {
                a[m+ii] = a[m];
                m = m - ii;  //置换 1、
            }
            a[m+ii] = temp;  // 置换 2、
        }
        ii = ii/2;  //直至增量为零！
    }

    printf("\n排序后的值为:\n");
        for (int len = 0; len < n; len++)
        {
            printf("%3d",a[len]);
        }
        return 0;
}

插入排序

/*本程序演示 插入排序 （直接插入排序）*/

/*是否稳定？ 稳定！*/
#include<stdlib.h>
#include<stdio.h>

int main()
{
     int a[10];
    int n = sizeof(a)/sizeof(a[0]);
    int num = n;
    int i=0;
    printf("请您输入排列的数：\n");
    while ( scanf("%d",&a[i]) && num >1)  //循环向数组中存入数
    {
        i++;
        num--;
    }
    printf("排列之前的顺序为：");
    for (int length=0;length<n;length++)
    {
        printf("%3d",a[length]);
    }

    for(int i = 0;i<n-1;i++)     //取一个数在数组中检索 到相应位置 插入，其后的数相应后移
    {
        int dex = i;
        int m = a[dex+1];
        while (dex >= 0 && m < a[dex])
        {
            a[dex+1] = a[dex];  // 其后的数相应后移！
            dex--;  // 元素前移
        }
        a[dex+1] = m;  // 元素前移
    }

    printf("\n排序后的值为:\n");
    for (int len = 0; len < n; len++)
    {
        printf("%3d",a[len]);
    }
    return 0;

}