插入排序

#include<stdio.h> 
insertsort(int a[], int n)                //插入排序
{
    int i, j, t;
    for (i = 1; i < n; i++)            //循环n-1次,执行n-1趟插入排序 
    {
        t = a[i];                 //将a[i]保存到临时变量t中 
        j = i - 1;
        while (j >= 0 && t < a[j])     //找到t的插入位置 t与a[j]之间的<符号改动可以升序降序
            a[j + 1] = a[j--];         //a[j]后移,再将j-1 
        a[j + 1] = t;             //将t插入到指定位置,第i-1趟完成(共n-1趟) 
    }
}
int main()
{
    int i, a[10] = { 4,3,2,1,5,6,7,9,8,10 };    //初始化序列 
    printf("原数组元素:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);                //显示原序列之中的元素 
    insertsort(a, 10);                  //插入排序 
    printf("\n插入排序后:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);              //输出排序后的结果 
    return 0;
}

选择排序

#include<stdio.h>
void selectslort(int k[], int n)     //选择排序
{
    int i, j, min, t;
    for (i = 0; i <= n - 2; i++)
    {
        min = i;
        for (j = i + 1; j <= n-1; j++)      //在后面 n-(i+1)=n-i-1 个元素中找到最小元素的下标(结束循环时j等于n嘛~)
            if (k[j] < k[min])              //k[j]与k[min]之间<符号改变有惊天大秘密哟!
                min = j;                   //用min记录最小元素下标
        if (min != i)                      //如果最小的元素不位于后n-i-1个元素档第1个
        {
            t = k[min];
            k[min] = k[i];                 //交换元素
            k[i] = t;
        }
    }
}
int main()
{
    int i, a[10] = { 4,3,2,1,5,6,7,9,8,10 };    //初始化序列 
    printf("原数组元素:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);                //显示原序列之中的元素 
    selectslort(a, 10);                  //执行选择排序 
    printf("\n选择排序后:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);              //输出排序后的结果 
    return 0;
}

冒泡排序

#include<stdio.h>
void bubblesort(int k[], int n)     //冒泡排序
{
    int i, j, t, flag = 1;
    for (i = 0; i < n - 1 && flag == 1; i++)  //共执行n-1趟排序
    {
        flag = 0;                           //每一趟执行一趟排序,flag置0
        for (j = 0; j < n - i - 1; j++)
        {
            if (k[j] > k[j + 1])           //数据交换
            {
                t = k[j + 1];
                k[j+1] = k[j];
                k[j] = t;
                flag = 1;                //发生元素交换flag置1
            }
        }
    }
}
int main()
{
    int i, a[10] = { 4,3,2,1,5,6,7,9,8,10 };    //初始化序列 
    printf("原数组元素:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);            //显示原序列之中的元素 
    bubblesort(a, 10);                  //执行选择排序 
    printf("\n冒泡排序后:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);            //输出排序后的结果 
    return 0;
}

希尔排序

#include<stdio.h>
void shellsort(int k[], int n)              //希尔排序 
{
    int i, j, flag, gap = n, tmp;
    while (gap > 1)
    {
        gap /= 2;                          //增量缩小,每次减半
        do {                               //子序列应用冒泡排序,可以使用其他排序
            flag = 0;
            for (i = 0; i <= n - gap - 1; i++)
            {
                j = i + gap;
                if (k[i] > k[j])
                {
                tmp = k[i];
                k[i] = k[j];
                k[j] = tmp;
                flag = 1;
                }
            }
        } while (flag != 0);
    }
}
int main()
{
    int i, a[10] = { 4,3,2,1,5,6,7,9,8,10 };    //初始化序列 
    printf("原数组元素:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);                //显示原序列之中的元素 
    shellsort(a, 10);                  //执行希尔排序 
    printf("\n希尔排序后:");
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);              //输出排序后的结果 
    return 0;
}

桶排序

桶排序的思想是若待排序的值在一个明显有限范围内(整形)时,可设计有限个有序通,待排序的值装入对应的桶(当然也可以装入若干个值),桶号就是待排序的值,顺序输出各个桶的值,将得到有序序列。

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int b[101],n,i,j,k;
    memset(b,0,sizeof(b));        //初始化 
    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>k;
        b[k]++;            //将等于k的值全部装入第k桶中 
    }

    for(i=0;i<=100;i++)
    {
        while(b[i]>0)        //相同的整数要重复输出 
        {
            cout<<i<<" ";     
            b[i]--;            //输出一个整数后,加一 
        }
    }


    return 0;
}

堆排序

#include <stdio.h>
#define N 100

int sift(int R[], int n, int i) 
{
    int j, k, t;
    for (t = R[i],k = i,j = 2*i; j <= n; ) 
    {
        if (R[j] > R[j/2])
        {
            R[j/2] = R[j];
            k = j;
        }
        if (j % 2 == 0) j++;
        else if (k == j/2) break;
        else {
            R[k] = t;
            j = 2*k;
        }
    }
    R[k] = t;
}

void heapsort(int R[], int n)
{
    int i, t;
    for (i = n/2; i >= 1; i--) sift(R,n,i);
    for (i = n; i >= 2; i--)
    {
        t = R[1];
        R[1] = R[i];
        R[i] = t;
        sift(R, i - 1, 1);
    }
}

int main()
{
    int R[N], n, i;
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
        scanf("%d",&R[i]);
    heapsort(R, n);
    for (int i = 1; i <= n; i++)
        printf("%d ",R[i]);
}

归并排序

#include <stdio.h>
#define N 100
int MERGE(int R[], int R1[], int l, int m, int h)
{
    int i,j,k;
    for(i=l,j=m+1,k=l;i<=m&&j<=h;k++)
    if(R[i]<R[j])
    {
        R1[k]=R[i];
        i++;
    } else {
        R1[k] = R[j];
        j++;
    }
    if(i>m)
        for(;j<=h;j++,k++) R1[k]=R[j];
    if(j>h)
        for(;i<=m;i++,k++) R1[k]=R[i];
}
int MERGEPASS(int R[], int R1[], int n, int len)
{
    int l,m,h,i;
    for(l=0,m=l+len-1;m<n-1;)
    {
        if(m+len<n) h=m+len;
        else h=n-1;
        MERGE(R,R1,l,m,h);
        l=h+1;m=l+len-1;
    }

    for(i = l; i < n; i++)
    R1[i] = R[i];
}

int MERGESORT(int R[], int n)
{
    int R1[N],len,i;
    for(len=1;len<n;)
    {
        MERGEPASS(R,R1,n,len);
        len*=2;
        MERGEPASS(R1,R,n,len);
        len*=2;
        } 
}
int main()
{ 
    int R[N]={25, 57, 48, 37, 12, 92, 86}, i;
    MERGESORT(R,7);
    for(i = 0; i < 7; i++)
    printf("%d ",R[i]);
}

最后修改:2021 年 12 月 06 日
如果觉得我的文章对你有用,请随意赞赏