devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言---插入排序、希尔排序、冒泡排序、选择排序、快速排序简单介绍_插入法数组排序c语言

作者：你好赵伟 | 2024-05-17 16:14:10

赞

踩

插入法数组排序c语言

文章目录


本文主要介绍用C语言实现的一些排序方法，有插入排序、希尔排序、冒泡排序、选择排序和快速排序，文章中给出的例子都是按照升序排列的。

插入排序

若数组只有一个元素，自然不用排序，插入排序从数组的第二个元素开始，先将当前的元素存起来，然后将它和前面的元素依次比较，大于它的元素依次向后移动，直到找到小于或等于它的元素，将存放的这个元素赋值给经过比较找到的数组位置中，就完成了一次插入排序，每完成一次插入排序，前面的(n+1)个数就已经是顺序的了，其中n为当前完成插入排序的次数。让一个有n个元素的数组顺序排列，需要n-1次插入排序。
插入排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void InsertSort(int *a,int n)
{
    int i,j,temp;
    if(n==1)
    {
        printf("After InsertSort array : \n");
        print_array(a,n);
    }
    for(i=1;i<n;i++)
    {
        temp = a[i];   //保存当前值
        for(j=i-1;j>=0;j--)
        {
            if(a[j] > temp)
                a[j+1] = a[j];   //前面的值比当前值大，向后移动
            else
                break;      //找到了当前值该插入的位置
        }
        a[j+1] = temp;   //将当前值插入在找到的位置
        printf("After %d InsertSort array : ",i);
        print_array(a,n);
        if(i==n-1)
        {
            printf("After InsertSort array : \n");
            print_array(a,n);
        }    
    }
}

void main()
{
    int n,i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    InsertSort(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

运行结果如下图所示。
在这里插入图片描述

希尔排序

希尔排序是比较特殊的插入排序，上面提到的插入排序每次的步长为1，希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行插入排序，初始的步长是要排列元素数量的一半（取整），之后每次折半，最后一次排序是步长为1的插入排序。
希尔排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void ShellSort(int *a,int n)
{
    int i,j,k,temp,gap;
    if(n==1)  //数组只有一个元素
    {
        printf("After ShellSort array : \n");
        print_array(a,n);
    }
    gap = n/2;   //初始值为数组长度的一半取整
    while(gap > 0)  //退出循环的条件是 gap = 0
    {
        for(i=0;i<gap;i++)    //i为每组第一个元素的下标
        {
            for(j=gap+i;j<n;j+=gap)  //j的初始值为每组第二个元素的下标
            {
                temp = a[j];   //保存需要插入的值
                for(k=j-gap;k>=0;k-=gap)   //从j的前一个元素j-gap开始比
                {
                    if(a[k]>temp)
                        a[k+gap] = a[k];  //注意gap的值
                    else
                        break;
                }
                a[k+gap] = temp;  //插入到指定位置
            }
        }
        printf("After gap=%d ShellSort array : ",gap);
        print_array(a,n);
        gap = gap/2;   //gap的值在每次过后减半
    }
    printf("After ShellSort array : \n");
    print_array(a,n);
}

void main()
{
    int n,i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    ShellSort(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

运行结果如下图所示。
在这里插入图片描述

冒泡排序

冒泡排序相对比较简单，每趟冒泡排序从头开始，相邻两元素比大小，前面的元素比后面的元素大就交换，否则不交换继续往后比较，可以控制循环不用从头比较到尾，因为每经过一趟冒泡排序，所剩下元素中最大的数会被移动到数组末端，后面序列是有序的。
冒泡排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void BubbleSort(int *a,int n)
{
    int i,j,temp;
    if(n==1)  //数组只有一个元素
    {
        printf("After BubbleSort array : \n");
        print_array(a,n);
    }
    for(i=0;i<n-1;i++)  //外层循环执行次数比元素个数小1
    {
        for(j=0;j<n-i-1;j++)  //内层循环每次执行的次数跟i值有关
        {
            if(a[j]>a[j+1]) //相邻元素做比较，根据比较结果决定交换与否
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        printf("After %d BubbleSort array : ",i+1);
        print_array(a,n);
    }
    printf("After BubbleSort array : \n");
    print_array(a,n);
}

void main()
{
    int n,i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    BubbleSort(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

运行结果如下图所示。
在这里插入图片描述

选择排序

选择排序就是在每一趟排序中找到剩余元素中的最小值，然后将其与数组中第n个元素(第n趟排序就是第n个元素)进行交换(如果最小的是自己，不用交换)，为了优化，可以在一次循环中同时找到最大值和最小值分别交换，这样只需执行元素数量的一半即可完成最终排序。
选择排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void SelectSort(int *a,int n)
{
    int i,j,k,min;
    if(n==1)  //数组只有一个元素
    {
        printf("After SelectSort array : \n");
        print_array(a,n);
    }
    for(i=0;i<n-1;i++)  //外层循环执行次数比元素个数小1
    {
		k = i;  
        min = a[i];  //选定当前值为最小值
        for(j=i+1;j<n;j++)  //内层循环每次执行的次数跟i值有关
        {
            if(a[j]<min)   //找出最小值的下标
            {
                min = a[j];  //更新当前最小值
                k = j;  //记录下标
            }  
        }
        if(k != i)   //当前元素不是最小值，交换
        {
            a[k] = a[i];
            a[i] = min;
        }
        printf("After %d SelectSort array : ",i+1);
        print_array(a,n);
    }
    printf("After SelectSort array : \n");
    print_array(a,n);
}

void main()
{
    int n,i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    SelectSort(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

运行结果如下图所示。在这里插入图片描述
在一趟排序中同时找出最大值和最小值进行替换，这种情况下一定要注意，如果最大值出现在当前最小值将要存放的位置，如果你先交换了最小值，那么在交换最大值时就会出现问题，一定要在代码中进行判断，如果最大值出现在当前最小值将要存放的位置，那么在先交换了最小值后，在交换最大值时需要和交换最小值的那个位置进行交换。
同时找出最大值和最小值的选择排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void SelectSort(int *a,int n)
{
    int i,j,k,l,min,max;
    if(n==1)  //数组只有一个元素
    {
        printf("After SelectSort array : \n");
        print_array(a,n);
    }
    for(i=0;i<n/2;i++)  //外层循环执行次数是元素个数的一半
    {
		k = i;
        l = n-i-1;
        min = a[i];     //选定最小值
        max = a[n-i-1];  //选定最大值
        for(j=i;j<n-i;j++)  //内层循环每次执行的次数跟i值有关
        {
            if(a[j]<min)   //找出最小值的下标
            {
                min = a[j];  //更新当前最小值
                k = j;     //记录下标
            }
            else if(a[j]>max)
            {
                max = a[j];
                l = j; 
            }
        }
        if(k != i)  //最小值发生变化
        {
            a[k] = a[i];
            a[i] = min;
        }
        if(l != n-i-1 && l != i)    //最大值发生变化并且最大值不是和最小值交换位置  
        {
            a[l] = a[n-i-1];
            a[n-i-1] = max;
        }
        printf("After %d SelectSort array : ",i+1);
        print_array(a,n);
    }
    printf("After SelectSort array : \n");
    print_array(a,n);
}

void main()
{
    int n,i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    SelectSort(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

运行结果如下图所示。
在这里插入图片描述

快速排序

快速排序需要选择一个基准值key，一般选择最左边的，定义两个下标值，一个是最左边值的一个是最右边值的下标low和high，每次开始的时候，high先往左边移动，遇到比key值小的就停下，然后low开始往右边移动，遇到比key值大的就停下，此时，如果low<high，就交换low和high下标对应的值，然后依然是high先移动，low后移动，当low=high时，将这个位置的值和key值进行交换。交换完成后，key值左边的值都已经比它小，右边的值都比它大，然后在左右两边再选择基准值递归。注意，在移动时，先移动的是远离key值的那个下标值。
快速排序的完整代码如下。

#include <stdio.h>
#include <stdlib.h>

int n,count = 1;
void print_array(int *a,int n)
{
    int i;
    for (i=0; i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void QuickSort(int *a,int low,int high)
{
    int key,temp;
    int start,end;
    if(low>=high)   //涉及递归，根据low和high的关系决定是否执行下面的代码
        return;
    start = low;  //记录起始位置
    end = high;
    key = a[low]; //基准值设定
    while(low < high)
    {
        while(low < high && a[high] >= key)   //一定是大于等于
            high--;
        while(low < high && a[low] <= key)    //一定是小于等于
            low++;
        //low<high时交换low和high对应的值
        temp = a[high];    
        a[high] = a[low];
        a[low] = temp;
    }
    //退出循环即low=high,交换其与key的值
    temp = a[high];
    a[high] = key;
    a[start] = temp;
    printf("After %d QuickSort array : ",count);
    print_array(a,n);
    count++;
    QuickSort(a,start,low-1);  //一分为二进行递归
    QuickSort(a,low+1,end);
}

void main()
{
    int i;
    int *a;
    printf("Please input the number of the integer : ");
    scanf("%d",&n);
    a = (int*)malloc(n*sizeof(int));
    printf("Please input %d integer numbers : \n",n);
    for(i=0; i<n; i++)
        scanf("%d",&a[i]);
    printf("Original array : \n");
    print_array(a,n);
    QuickSort(a,0,n-1);
    printf("After QuickSort array : \n");
    print_array(a,n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

运行结果如下图所示。
在这里插入图片描述
以上就是用C语言实现插入排序、希尔排序、冒泡排序、选择排序和快速排序的所有内容了！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/584289
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号