精华内容
下载资源
问答
  • c语言数组选择法排序

    2012-03-07 23:08:30
    使用c语言写的数组选择法排序的程序代码,有详细注释。
  • C语言 数组——选择排序法

    千次阅读 2020-04-06 17:18:47
    #include <stdio.h> int main() { int a[10],i,j,t; for(i=0;i<=9;i++){ scanf("%d",&a[i]); } for(i=0;i<=8;i++){ for(j=i+1;j<=9;j++){ if(a[i]>a[j]){ ... ...
    #include <stdio.h>
    int main()
    {
    	int a[10],i,j,t;
    	for(i=0;i<10;i++){
    		scanf("%d",&a[i]);
    	}
    	for(i=0;i<9;i++){
    		for(j=i+1;j<10;j++){
    		if(a[i]>a[j]){
    		t=a[i];
    		a[i]=a[j];
    		a[j]=t;
    		}
    	}
    }
        for(i=0;i<10;i++)
    	printf("%d ",a[i]);
    	printf("\n"); 
    	return 0;
    }
    
    
    
    展开全文
  • C语言数组排序法

    万次阅读 多人点赞 2011-07-13 20:27:16
    很多朋友是以谭浩强老师编的《c语言教程》作为学习...为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。 (1)
     

    很多朋友是以谭浩强老师编的《c语言教程》作为学习C语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉

    让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。

    (1)“冒泡法”

    冒泡法大家都较熟悉。其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a[i  ],则交换它们,一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理,即完成排序。下面列出其代码:

    void bubble(int *a,int n) /*定义两个参数:数组首地址与数组大小*/

    {

    int i,j,temp;

    for(i=0;i<n-1;i++)

    for(j=i+1;j<n;j++) /*注意循环的上下限*/

    if(a[i  ]>a[j]) {

    temp=a[i  ];

    a[i  ]=a[j];

    a[j]=temp;

    }

    }

    冒泡法原理简单,但其缺点是交换次数多,效率低。

    下面介绍一种源自冒泡法但更有效率的方法“选择法”。

     

    (2)“选择法”

    选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a[i ],这样就比冒泡法省下许多无用的交换,提高了效率。

    void choise(int *a,int n)

    {

    int i,j,k,temp;

    for(i=0;i<n-1;i++) {

    k=i; /*给记号赋值*/

    for(j=i+1;j<n;j++)

    if(a[k]>a[j ]) k=j; /*是k总是指向最小元素*/

    if(i!=k) { /*当k!=i是才交换,否则a[i ] 即为最小*/

    temp=a[i ];

    a[i ]=a[k];

    a[k]=temp;

    }

    }

    }

    选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。

     

    (3)“快速法”

    快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素(一般为a[(i +j)/2],即中间元素)作为参照,把比它小 的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析其代码:

    void quick(int *a,int i,int j)

    {

    int m,n,temp;

    int k;

    m=i;

    n=j;

    k=a[(i +j)/2]; /*选取的参照*/

    do {

    while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/

    while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/

    if(m<=n) { /*若找到且满足条件,则交换*/

    temp=a[m];

    a[m]=a[n];

    a[n]=temp;

    m++;

    n--;

    }

    }while(m<=n);

    if(m<j) quick(a,m,j); /*运用递归*/

    if(n>i) quick(a,i,n);

    }

     

    (4)“插入法”

    插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序,再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。

    void insert(int *a,int n)

    {

    int i,j,temp;

    for(i=1;i<n;i++) {

    temp=a[i ]; /*temp为要插入的元素*/

    j=i-1;

    while(j>=0&&temp<a[j]) { /*从a[i -1]开始找比a[i ]小的数,同时把数组元素向后移*/

    a[j+1]=a[j ];

    j--;

    }

    a[j+1]=temp; /*插入*/

    }

    }

     

    (5)“shell法”

    shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序,再缩小k值(一般取其一半),再排序,直到k=1时完成排序。下面让我们来分析其代码:

    void shell(int *a,int n)

    {

    int i,j,k,x;

    k=n/2; /*间距值*/

    while(k>=1) {

    for(i=k;i<n;i++) {

    x=a[i ];

    j=i-k;

    while(j>=0&&x<a[j]) {

    a[j+k]=a[j ];

    j-=k;

    }

    a[j+k]=x;

    }

    k/=2; /*缩小间距值*/

    }

    }

    上面我们已经对几种排序法作了介绍,现在让我们写个主函数检验一下。

    #include<stdio.h>

    /*别偷懒,下面的"..."代表函数体,自己加上去哦!*/

    void bubble(int *a,int n)

    {

    ...

    }

    void choise(int *a,int n)

    {

    ...

    }

    void quick(int *a,int i,int j)

    {

    ...

    }

    void insert(int *a,int n)

    {

    ...

    }

    void shell(int *a,int n)

    {

    ...

    }

    /*为了打印方便,我们写一个print吧。*/

    void print(int *a,int n)

    {

    int i;

    for(i=0;i<n;i++)

    printf("%5d",a[i ]);

    printf("\n");

    }

    main()

    { /*为了公平,我们给每个函数定义一个相同数组*/

    int a1[]={13,0,5,8,1,7,21,50,9,2};

    int a2[]={13,0,5,8,1,7,21,50,9,2};

    int a3[]={13,0,5,8,1,7,21,50,9,2};

    int a4[]={13,0,5,8,1,7,21,50,9,2};

    int a5[]={13,0,5,8,1,7,21,50,9,2};

    printf("the original list:");

    print(a1,10);

    printf("according to bubble:");

    bubble(a1,10);

    print(a1,10);

    printf("according to choise:");

    choise(a2,10);

    print(a2,10);

    printf("according to quick:");

    quick(a3,0,9);

    print(a3,10);

    printf("according to insert:");

    insert(a4,10);

    print(a4,10);

    printf("according to shell:");

    shell(a5,10);

    print(a5,10);

    }

     

     

    再补充个堆排序

    堆排序

    1、 堆排序定义
    n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
    (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

    若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
    【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

    2、大根堆和小根堆
    根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
    根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
    注意:
    ①堆中任一子树亦是堆。
    ②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

    3、堆排序特点
    堆排序(HeapSort)是一树形选择排序。
    堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。

    4、堆排序与直接插入排序的区别
    直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
    堆排序可通过树形结构保存部分比较结果,可减少比较次数。


    5、堆排序
    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

    (1)用大根堆排序的基本思想
    ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
    ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
    ③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
    ……
    直到无序区只有一个元素为止。

    (2)大根堆排序算法的基本操作:
    ① 初始化操作:将R[1..n]构造为初始堆;
    ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
    注意:
    ①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
    ②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

    (3)堆排序的算法:
    void HeapSort(SeqIAst R)
    { //对R[1..n]进行堆排序,不妨用R[0]做暂存单元
    int i;
    BuildHeap(R); //将R[1-n]建成初始堆
    for(i=n;i>1;i--){ //对当前无序区R[1..i ]进行堆排序,共做n-1趟。
    R[0]=R[1];R[1]=R[ i ];R[i ]=R[0]; //将堆顶和堆中最后一个记录交换
    Heapify(R,1,i-1); //将R[1.. i-1]重新调整为堆,仅有R[1]可能违反堆性质
    } //endfor
    } //HeapSort


    (4) BuildHeap和Heapify函数的实现
    因为构造初始堆必须使用到调整堆的操作,先讨论Heapify的实现。
    ① Heapify函数思想方法
    每趟排序开始前R[l..i]是以R[1]为根的堆,在R[1]与R[i ]交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆。因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可。
    "筛选法"调整堆
    R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆性质,以R[low]为根的树已是堆,无须调整;否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质,或者该结点已是叶子为止。上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来。因此,有人将此方法称为"筛选法"。
    具体的算法【参见教材】

    ②BuildHeap的实现
    要将初始文件R[l..n]调整为一个大根堆,就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
    显然只有一个结点的树是堆,而在完全二叉树中,所有序号 的结点都是叶子,因此以这些结点为根的子树均已是堆。这样,我们只需依次将以序号为 , -1,…,1的结点作为根的子树都调整为堆即可。
    具体算法【参见教材】。

    5、大根堆排序实例
    对于关键字序列(42,13,24,91,23,16,05,88),在建堆过程中完全二叉树及其存储结构的变化情况参见【动画演示】。

    6、 算法分析
    堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
    堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
    由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
    堆排序是就地排序,辅助空间为O(1),
    它是不稳定的排序方法。

    展开全文
  • 数组形式,不能运用除了main之外的函数的冒泡法,选择排序法,二分法,插入法,删除法,最好来段代码
  • 选择法排序是指每次选择索要排序数组中的最小值(这里是由小到大排序,如果是由大到小排序则需要选择最大值)的数组元素,将这些数组元素的值与前面没有进行排序数组元素值进行互换 代码实现需要注意的是:声明...

    1、选择法排序

    选择法排序是指每次选择索要排序的数组中的最小值(这里是由小到大排序,如果是由大到小排序则需要选择最大值)的数组元素,将这些数组元素的值与前面没有进行排序的数组元素值进行互换
    代码实现需要注意的是:声明一个数组和两个整形变量,数组用于存储输入的数字,而整形变量用于存储最小的数组元素的数值与该元素的位置,在我的代码中实现为a[] temp position。代码具体如下

    #include<stdio.h>
    int main()
    {
        int m,n,k;
        printf("please input the length of the array:");
        scanf("%d",&k);
        int a[k];
        int temp;
        int position;
        printf("please input the number of the array:\n");
        for(m=0;m<k;m++)
        {
            printf("a[%d]=",m+1);
            scanf("%d",&a[m]);
        }
        /*从小到大排序*/
        for(m=0;m<k-1;m++)
        {
            temp=a[m];          //设置当前的值为最小值
            position=m;         //记录当前的位置
            for(n=m+1;n<k;n++)
            {
                if(a[n]<temp)
                {
                    temp=a[n];  //如果找到比当前的还要小的数值,则更换最小的数值与位置
                    position=n;
                }
            }
            a[position]=a[m];
            a[m]=temp;
        }
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        return 0;
    }
    
    

    结果如下
    在这里插入图片描述

    2、冒泡法排序

    冒泡法排序就是值在排序时,每次比较数组中相邻的两个数组元素的值,将比较小的(从小到大排序算法,如果是从大到小排序算法就是将较大的数排在较小的数前面)排在比较大的前面
    在代码实现的过程中:声明一个数组与一个整型变量,数组用于存放数据元素,整型变量用于交换时作为中间变量。然后通过双层循环实现冒泡法。
    代码具体如下

    #include<stdio.h>
    int main()
    {
        int m,n,k;
        printf("please input the length if the array:");
        scanf("%d",&k);
        int a[k];
        int temp;
        for(m=0;m<k;m++)
        {
            printf("a[%d]=",m+1);
            scanf("%d",&a[m]);
        }
        /*从小到大排序*/
        for(m=0;m<k;m++)        //外层循环为k-1次
        {
            for(n=k-1;n>m;n--)  //内层循环下标为m~9
            {
                if(a[n]<a[n-1])
                {
                    temp=a[n-1];
                    a[n-1]=a[n];
                    a[n]=temp;
                }
            }
        }
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        return 0;
    }
    

    结果如下
    在这里插入图片描述

    3、交换法排序

    交换发排序就是将每一位数依次与其后面所有的数一一比较,如果发现符合条件就交换数据。首先用第一个数依次与其后的所有数据进行比较,如果存在比其小的数(这里采用的是从小到大排序,如果从大倒下排序反过来就行)就交换数据。然后用现在这个位上的数与后面的数比较,一直到最后一个数。然后向下进行,直至到最后一个数。结束
    代码实现:声明一个整数与整型数组,数组用于存放输入的数据,整型数据用于交换的充当中间变量
    代码具体如下

    #include<stdio.h>
    int main()
    {
        int m,n,k;
        printf("please input the length if the array:");
        scanf("%d",&k);
        int a[k];
        int temp;
        for(m=0;m<k;m++)
        {
            printf("a[%d]=",m+1);
            scanf("%d",&a[m]);
        }
        /*从小到大排序*/
        for(m=0;m<k-1;m++)
        {
            for(n=m+1;n<k;n++)
            {
                if(a[m]>a[n])
                {
                    temp=a[n];
                    a[n]=a[m];
                    a[m]=temp;
                }
            }
        }
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        return 0;
    }
    

    结果如图
    在这里插入图片描述
    为了方便分析程序的过程,对原始程序更改一下。把每一步具体每个数组位置的上元素打印出来,代码如下

    #include<stdio.h>
    int main()
    {
        int m,n,k;
        printf("please input the length if the array:");
        scanf("%d",&k);
        int a[k];
        int temp;
        int times=0;
        for(m=0;m<k;m++)
        {
            printf("a[%d]=",m+1);
            scanf("%d",&a[m]);
        }
        printf("The  original  array  is:");
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        printf("\n");
        /*从小到大排序*/
        for(m=0;m<k-1;m++)
        {
            for(n=m+1;n<k;n++)
            {
                if(a[m]>a[n])
                {
                    temp=a[n];
                    a[n]=a[m];
                    a[m]=temp;
                    
                }
                times++;
                printf("the %d times for exchange:",times);
                for(int i=0;i<k;i++)
                {
                    printf("%d\t",a[i]);
                }
                printf("\n");
            }
        }
        printf("\nthe last result:");
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        return 0;
    }
    

    图片如下
    在这里插入图片描述

    4、插入排序

    插入法排序基本思想是抽出一个数据,在前面的数据中寻找相应的位置插入然乎继续找下一个元素,直至结束

    数据 元素【0】 元素【1】 元素【2】 元素【3】 元素【4】
    起始值 9 6 15 4 2
    第一次 9
    第二次 6 9
    第三次 6 9 15
    第四次 4 6 9 15
    排序结果 2 4 6 9 15
    在第一次排序过程中将第一个数取出来,并放置在第一个位置然后取出第二个数,并将第二个数与第一个数进行比较,如果第二个数小于第一个数,则将第二个数排在第一个数之前,否则将第二个数排在第一个数之后;然后取出下一个数,先与排在后面的数字进行比较,如果当前数字较大则排在最后,如果当前数字比较小,还要与之前的数字进行比较,如果当前数字比前面的数字小,则将当前数字排在比它小的数字和比它大的数字之间,如果没有比当前数字小的数字,则将当数字排在最前方。依此类推,不断取出未进行排序的数字与排序好的数字进行比较,并插入到相应的位置,直到将一组数字按从小到大排序为止。 代码实现:需要声明一个整型数组,两个整型变量。数组用于存放输入的数据,两个整型变量分别用于存放交换数据时候的中间变量以及记录数据元素的位置 代码实现如下:
    #include<stdio.h>
    int main()
    {
        int m,n,k;
        printf("please input the length if the array:");
        scanf("%d",&k);
        int a[k];
        int temp;
        int position;
        for(m=0;m<k;m++)
        {
            printf("a[%d]=",m+1);
            scanf("%d",&a[m]);
        }
        /*从小到大排序*/
        for(m=1;m<k;m++)        //外层循环为k次
        {
            temp=a[m];          //temp为需要插入的元素
            position=m-1;       //position为需要插入位置前一个位置
            while((position>=0)&&(temp<a[position]))
            {
                a[position+1]=a[position];  //插入位置前一个位置元素后移
                position--;                 //位置继续减是往前移判断前面的元素是否也需要后移
                /*(这里是最难理解的,比较前面几种排序算法是特别难得,抓住一个点:上一个元素后移之后还需要继续向前面移动去判断)*/
            }
            a[position+1]=temp;             //position一直减到不满足插入条件,再往后加一位才是元素插入位置
        }
        for(m=0;m<k;m++)
        {
            printf("%d\t",a[m]);
        }
        return 0;
    }
    

    效果如图:
    在这里插入图片描述

    5、折半法排序

    折半法排序又称为快速排序,是选择一个中间值middle,然后把比中间值小的数据放在左边,比中间值大的放在右边(这里是从小到大排序。具体实现就是从两边找,找到一对后进行交换),然后两边分别递归使用这一过程。小代码实现:

    #include<stdio.h>
    void binarysort(int left,int right,int array[])
    {
        int m,n;
        int middle,temp;
        m=left;
        n=right;
        middle=array[(left+right)/2];           //求中间值
        do
        {
            while((array[m]<middle)&&(m<right)) //从左到右找小于中间值的数
            {
                m++;
            }
            while((array[n]>middle)&&(n>left))  //从右到左找大于中间值的数
            {
                n--;
            }
            if(m<=n)                            //找到不符合左边小于中间值,右边大于中间值的数对
            {
                temp=array[m];
                array[m]=array[n];
                array[n]=temp;
                m++;n--;
            }
        }while(m<=n);//如果两边的下标交错,就停止(完成一次)
        /*递归左半边*/
        if(left<n)
            binarysort(left,n,array);
        /*递归右半边*/
        if(right>m)
            binarysort(m,right,array);
    }
    int main()
    {
        int i,k;
        printf("please input the length of array:");
        scanf("%d",&k);
        int a[k];
        printf("please input the number of the array:\n");
        for(i=0;i<k;i++)
        {
            printf("a[%d]=",i+1);
            scanf("%d",&a[i]);
        }
        /*从小到大排序*/
        binarysort(0,k,a);
        for(i=0;i<k;i++)
        {
            printf("%d\t",a[i]);
        }
    }
    

    结果如下图
    在这里插入图片描述

    6、五种方法比较

    (1)选择法排序
    选择法排序在排序过程中共需进行n(n-1)/2次比较,互相交换n-1次。选择法排序简单、容易实现,适用于数量较小的排序。
    (2)冒泡法排序
    最好的情况是正序,因此只要比较一次即可最坏的情况是逆序,需要比较n^2次。冒泡法排序是稳定的排序方法,当待排序列有序时,效果比较好。
    (3)交换法排序
    交换法排序和冒泡法排序类似,正序时最快,逆序时最慢,排列有序数据时效果最好。
    (4)插入法排序
    此算法需要经过n-1次插入过程,如果数据恰好应该插入到序列的最后端,则不需要移动数据,可节省时间,因此若原始数据基本有序,此算法具有较快的运算速度。
    (5)折半法排序
    折半法排序对于较大的n时,是速度最快的排序算法;但当n很小时,此方法往往比其他排序算法还要慢。折半法排序是不稳定的,对应有相同关键字的记录,排序后的结果可能会颠倒次序。

    插入法、冒泡法、交换法排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序就能达到较快的速度在这种情况下,折半法排序反而会显得速度慢了。当n较小时,对稳定性不作要求时宜用选择法排序,对稳定性有要求时宜用插入法或冒泡法排序。

    展开全文
  • C语言数组排序算法详解——选择法、冒泡、交换、插入、折半C语言代码实现以及相应注释。可以参考本人另一篇博客关于C语言数组排序算法详解。
  • c语言数组排序小结(for beginner)  很多朋友是以谭浩强老师编的《c语言教程》作为学习c语言的入门教程的。书中涉及排序问题一般都以“冒泡”和“选择法”实现。为了扩大视野,增加学习编程的兴趣,我参阅了...
    c语言数组排序小结(for beginner)

      很多朋友是以谭浩强老师编的《c语言教程》作为学习c语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉。(高手们不要笑,这篇文章是写给出学者的,而且我自己也是只菜鸟,虽然内容陈旧,但值得初学者一看)。

      让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。

      (1)“冒泡法”

      冒泡法大家都较熟悉。其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a[i],则交换它们,一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理,即完成排序。下面列出其代码:
    void bubble(int *a,int n)
    {
    int i,j,temp;
    for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
    if(a[i]>a[j]) {
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    }
    }

      冒泡法原理简单,但其缺点是交换次数多,效率低。

      下面介绍一种源自冒泡法但更有效率的方法“选择法”。

      (2)“选择法”

      选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换,提高了效率。

    void choise(int *a,int n)
    {
    int i,j,k,temp;
    for(i=0;i<n-1;i++) {
    k=i;
    for(j=i+1;j<n;j++)
    if(a[k]>a[j]) k=j;
    if(i!=k) {
    temp=a[i];
    a[i]=a[k];
    a[k]=temp;
    }
    }
    }

      选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。

      (3)“快速法”

      快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素(一般为a[(i+j)/2],即中间元素)作为参照,把比它小的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析其代码:

    void quick(int *a,int i,int j)
    {
    int m,n,temp;
    int k;
    m=i;
    n=j;
    k=a[(i+j)/2];
    do {
    while(a[m]<k&&m<j) m++;
    while(a[
    n]>k&&n>i) n--;
    if(m<=n) {
    temp=a[m];
    a[m]=a[n];
    a[n]=temp;
    m++;
    n--;
    }
    }while(m<=n);
    if(m<j) quick(a,m,j);
    if(n>i) quick(a,i,n);
    }



    (4)“插入法”
      插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序,再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。

    void insert(int *a,int n)
    {
    int i,j,temp;
    for(i=1;i<n;i++) {
    temp=a[i];
    j=i-1;
    while(j>=0&&temp<a[j]) {
    a[j+1]=a[j];
    j--;
    }
    a[j+1]=temp;
    }
    }

      (5)“shell法”

      shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序,再缩小k值(一般取其一半),再排序,直到k=1时完成排序。下面让我们来分析其代码:

    void shell(int *a,int n)
    {
    int i,j,k,x;
    k=n/2;
    while(k>=1) {
    for(i=k;i<n;i++) {
    x=a[i];
    j=i-k;
    while(j>=0&&x<a[j]) {
    a[j+k]=a[j];
    j-=k;
    }
    a[j+k]=x;
    }
    k/=2;
    }
    }

     
    展开全文
  • 简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。 #pragma once #include <stdio.h> ...
  • C语言数组排序小结

    2012-05-29 11:22:47
    为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉。(高手们不要笑,这篇文章是写给出学者的,而且我自己也是只菜鸟,虽然内容陈旧,但值得初学者一看)。 让我们先定义...
  • 用冒泡选择法对10个整数排序C语言 数组

    万次阅读 多人点赞 2018-05-22 00:38:31
    1.区别: 两者最大的区别在于算法... 选择法是每趟选出一个最值确定其在结果序列中的位置,确定元素的位置是从前往后,而每趟最多进行一次交换,其余元素的相对位置不变。可进行降序排序或升序排序。2.冒泡:...
  • C语言数组

    2019-09-09 14:07:18
    数组的特点:构造类型之一,连续存放。 一维数组 1、定义:【存储类型】 数据类型 标识符 【下标】 2、初始化:不初始化 全部初始化 ...求fibonacci数组 数组排序(冒泡、选择) 进制转换 删除求质数 二维数组...
  • 选择排序法排列整形数组
  • 选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中最小的那个交换...
  • 3- C语言数组课件.ppt

    2020-02-28 09:38:18
    3.1 一维数组选择法对5个数如24530进行由小到大排序的过程 a[0] a[1] a[2] a[3] a[4] 排序前 2 4 5 3 0 第1轮比较 最小值位置下标 2 4 5 3 0 0 k= 0 4 2 0 2 3 3 5 4 a[0] a[k] 0 4 5 3 2 2 3 第2轮比较 4 5 3 2 ...
  • c语言选择排序法和冒泡排序法

    万次阅读 多人点赞 2015-04-20 19:11:48
    给定一个数组(或者输入一个数组),分别运用选择排序法和冒泡排序法将所要的结果输出。 程序分析:  选择排序 1>.对于选择排序,首先理解排序的思想。给定一个数组,这种思想首先假定数组的首元素为最大(最小)的...
  • c语言实现数组排序

    2016-12-21 14:45:00
    本文章只对选择排序和冒泡排序进行介绍 选择排序实际上是从0到length-1,选择某个元素与其他的元素...`从图可以看出排序出的数仿佛是从地下往上冒出一样,因此称之为冒泡排序法选择排序和冒泡排序算数复杂度都是n...
  • C语言--数组实现--各种...各种算法的相关分析如下:排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2)O(n2)稳定O(1)快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)选择排序O(n2)O(n2)稳定O(1)二叉树排序...
  • C语言——选择法排序_数组 问题描述 对于任意给定的含有十个数字的一维数组,如何进行排序? 编程思想: 让a[0]最小,分别与a[1]、a[2]…a[9]比较; 让a[1]最小,分别与a[2]…a[9]比较; … … #include <stdio.h...
  • 简单选择排序是指一种排序算法,在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。 一、基本思想 在要排序的一组数中,选出最小的一个数与...
  • 上面这个选择排序法编译运行时间是0.25秒gcc编译器 下面看看用指针怎么来进行操作 上面就是指针的操作方法 下面我们来看一下冒泡排序法,还是用两种方法来做 下面我们用指针来做测试 ...
  • c语言一维数组基本排序方法

    千次阅读 多人点赞 2019-07-11 21:06:22
    c语言数组排序 今天介绍排序中的两种基本方法:选择法和冒泡选择法选择第一个数字和后面的四个进行比较,如后面的小进行数字交换,否则不做运算。以此类推,到第四个数字和第五个数字比较结束。 代码...
  • 【问题描述】用选择法排序,让一个长度为n的整型数组内数据由大到小排列。n由键盘输入,排序后将数组元素依次输出。 【输入形式】输入分两行,第一行输入一个正整数n,第二行输入数组的n个数据,用空格隔开。 【输出...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 389
精华内容 155
关键字:

c语言数组选择排序法

c语言 订阅