啊哈磊_编程从这里起步

标题: C语言排序 [打印本页]
作者: 凡夫俗子    时间: 2012-8-10 08:44
标题: C语言排序
本帖最后由 =student= 于 2012-10-26 19:47 编辑

[ 本帖最后由 =student= 于 2012-8-10 21:43 编辑 ]\n\n
C语言主要排序有7种，分别是：选择排序， 快速排序，冒泡排序，堆排序，插入排序，归并排序，基数排序
平时用的比较多的是选择排序，代码如下：
  1. #include <stdio.h>
  2. int main()
  3. {
  4.         int a[10000],i,j,t,n;
  5.     printf("请输入排序数字的个数：");
  6.     scanf("%d",&n);//输入要排序数字的个数，自动从小到大排序
  7.     printf("请输入数据（数之间要有空格）：");
  8.         for(i=1;i<=n;i++)//循环输入要排序的数据，数与数之间要有空格
  9.     {
  10.                 scanf("%d",&a[i]);
  11.         }
  12.     for(i=1;i<=n-1;i++)
  13.     {
  14.                 for(j=i+1;j<=n;j++)
  15.         {
  16.                         if(a[i]>a[j])//如果前面的数大于后面的数，则交换
  17.             {
  18.                  t=a[i];
  19.                 a[i]=a[j];
  20.                 a[j]=t;
  21.             }
  22.         }
  23.     }
  24.     printf("从小至大排序：");
  25.     for(i=1;i<=n;i++)//循环输出
  26.     {
  27.                 printf("%d ",a[i]);
  28.     }
  29.         sleep(100000);
  30.         return 0;
  31. }
复制代码



有图有真相：

继续更新。。。

1.png (26.55 KB, 下载次数: 3)

1.png
作者: 凡夫俗子    时间: 2012-8-10 09:39
本帖最后由 =student= 于 2012-8-21 12:12 编辑

[ 本帖最后由 =student= 于 2012-8-21 12:12 编辑 ]\n\n[ 本帖最后由 =student= 于 2012-8-10 21:44 编辑 ]\n\n[ 本帖最后由 =student= 于 2012-8-10 21:42 编辑 ]\n\nc
语言排序之——基数排序（又称桶排序）
由于C语言下标数组限制，以下代码只能执行300000及以下的运算，若想更大可以定义多个数组并进行判断。
代码如下：

  1. #include <stdio.h>
  2. int main()
  3. {
  4.     int a[300001]={0},n,t,i,j;
  5.     printf("请输入要排序输的个数");
  6.     scanf("%d",&n);
  7.     printf("请输入数据（数之间要有空格）：");
  8.     for(i=1;i<=n;i++)
  9.     {
  10.         scanf("%d",&t);
  11.         a[t]++;//这个数据的下标增加
  12.     }
  13.     printf("从小至大排序:");
  14.     for(i=0;i<=300000;i++)
  15.     {
  16.                 if(a>0);
  17.         {
  18.                         for(j=1;j<=a;j++)
  19.                         {
  20.                                 printf("%d ",i);
  21.                         }                        
  22.                 }
  23.     }
  24.     sleep(100000);
  25.     return 0;
  26. }
复制代码



上图：
继续更新。。。


2.png (29.25 KB, 下载次数: 3)

2.png
作者: 凡夫俗子    时间: 2012-8-10 10:51
本帖最后由 =student= 于 2012-8-21 12:12 编辑

[ 本帖最后由 =student= 于 2012-8-10 21:43 编辑 ]\n\nC语言排序——冒泡排序
冒泡排序类似于选择排序，但选择排序效率更高。
原理：　设想被排序的数组a[1..N]垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

  1. #include <stdio.h>
  2. int main()
  3. {
  4.         int i,j,t,n;
  5.         int a[300000];
  6.     printf("请输入要排序输的个数:");
  7.     scanf("%d",&n);
  8.     printf("请输入数据（数之间要有空格）：");
  9.         for(i=0;i<n;i++);
  10.         scanf ("%d",&a[i]);
  11.         for(i=1;i<=n;i++)
  12.         {
  13.         for (j=0;j<n-j;j++)
  14.         {
  15.                         if (a[j]>a[j+1]) //交换
  16.                         {
  17.                                 t=a[j];
  18.                                 a[j]=a[j+1];
  19.                                 a[j+1]=t;
  20.                         }
  21.         }
  22.         }
  23.      printf("从小至大排序:");
  24.         for(i=0;i<n;i++)
  25.         {
  26.                 printf("%d ",a[i]);
  27.          }  
  28.     sleep(100000);
  29.     return 0;
  30. }
复制代码


上图：

继续更新。。。

搜狗截图_2012-08-10_10-44-43.png (59.83 KB, 下载次数: 7)

搜狗截图_2012-08-10_10-44-43.png
作者: 凡夫俗子    时间: 2012-8-10 11:08
有点小烧，37℃
作者: 凡夫俗子    时间: 2012-8-10 12:21
本帖最后由 =student= 于 2012-8-21 12:12 编辑

[ 本帖最后由 =student= 于 2012-8-10 21:46 编辑 ]\n\n[ 本帖最后由 =student= 于 2012-8-10 21:45 编辑 ]\n\nC语言排序——插入排序
原理：每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
代码如下：

  1. #include <stdio.h>
  2. int main()
  3. {
  4.    int   a[10000],i,j,k,t,n;
  5.    printf("请输入要排序输的个数:");
  6.    scanf("%d",&n);
  7.     printf("请输入数据（数之间要有空格）：");
  8.    for(i=0;i<n;i++)
  9.    {
  10.                 scanf("%d",&a[i]);
  11.    }
  12.    
  13.    for (j=1;j<n;j++)
  14.    {  
  15.       k = a[j];
  16.           i = j - 1;
  17.           while ((i >= 0) && (a > k))/* 开始插入排序的内层循环，注意循环条件以及终止条件 */
  18.        {     
  19.              a[i+1] = a;
  20.                  i--;
  21.           }
  22.           a[i+1] = k;
  23.       if(j==n-1)
  24.       {
  25.                  printf("从小至大排序:");
  26.                 for (t = 0;t<n;t++)
  27.                 {
  28.                         printf("%d ",a[t]);
  29.                 }
  30.                 printf("\n");
  31.       }
  32.    }
  33.    sleep(50000);
  34.    return 0;
  35. }
复制代码


图片：

继续更新ing

3.png (55.87 KB, 下载次数: 10)

3.png
作者: 凡夫俗子    时间: 2012-8-10 12:27
午饭ing，之后上课至5点，回来继续
作者: nan    时间: 2012-8-10 13:18
代码都有一些问题。是不是着急打太快了？{:soso_e112:}
作者: 凡夫俗子    时间: 2012-8-10 13:21
nan 发表于 2012-8-10 13:18:32
代码都有一些问题。是不是着急打太快了？

哪一个，我下午回家看看
来自：啊哈 [C语言论坛] Android客户端
作者: nan    时间: 2012-8-10 15:08
=student= 发表于 2012-8-10 10:51
C语言排序——冒泡排序
冒泡排序类似于选择排序，但选择排序效率更高。
原理：　设想被排序的数组a[1..N] ...

数组a后面都忘记写下标了
作者: nan    时间: 2012-8-10 15:23
个人的一点建议：涉及数组边界之类的循环条件，推荐用<=比较，个人觉得比较方便判断是否越界
作者: 凡夫俗子    时间: 2012-8-10 17:11
本帖最后由 =student= 于 2012-8-10 18:29 编辑
nan 发表于 2012-8-10 15:23:50
个人的一点建议：涉及数组边界之类的循环条件，推荐用<=比较，个人觉得比较方便判断是否越界

谢谢,由于起始值为0,所以需要使用<
来自：啊哈 [C语言论坛] Android客户端
作者: 凡夫俗子    时间: 2012-8-10 17:12
nan 发表于 2012-8-10 15:08:57

数组a后面都忘记写下标了

谢谢
来自：啊哈 [C语言论坛] Android客户端
作者: 凡夫俗子    时间: 2012-8-10 19:16
呃。。。正在研究归并排序
作者: 凡夫俗子    时间: 2012-8-10 19:25
休息ing。。。。。
作者: virfyf    时间: 2012-8-10 21:39
建议楼主贴代码时将附加选项这样设置.

[mw_shl_code=c,true]a[i][/mw_shl_code]

无标题.png (6.23 KB, 下载次数: 8)

无标题.png
作者: 凡夫俗子    时间: 2012-8-10 21:40
virfyf 发表于 2012-8-10 21:39
建议楼主贴代码时将附加选项这样设置.

非常感谢
作者: nan    时间: 2012-8-11 00:14
标题: 回复一楼
又仔细的看了下，我怎么感觉这是冒泡呢？选择排序不是有一个选出最小数再交换的过程吗？这个好像直接就交换了啊。
作者: 凡夫俗子    时间: 2012-8-11 08:06
nan 发表于 2012-8-11 00:14:37
又仔细的看了下，我怎么感觉这是冒泡呢？选择排序不是有一个选出最小数再交换的过程吗？这个好像直接就交换了啊。

选择排序是比较a【i】后面所有的数，确保它是最小的
来自：啊哈 [C语言论坛] Android客户端
作者: 凡夫俗子    时间: 2012-8-11 09:13
啊哈C论坛改版了呢
作者: 凡夫俗子    时间: 2012-8-11 12:01
发现个很严重的问题，快排我。。。也不会
作者: landrom    时间: 2012-8-12 10:31
来冒泡啦，我是日寸，顺便说一下。我还没看懂。先去看第三章教程先
作者: 凡夫俗子    时间: 2012-8-12 11:33
landrom 发表于 2012-8-12 10:31
来冒泡啦，我是日寸，顺便说一下。我还没看懂。先去看第三章教程先

呵呵，加在程序里用
作者: lin965639390    时间: 2012-8-12 12:22
高手啊，都看不懂是什么！
作者: 凡夫俗子    时间: 2012-8-12 12:27
lin965639390 发表于 2012-8-12 12:22
高手啊，都看不懂是什么！

慢慢学，加油
作者: 凡夫俗子    时间: 2012-8-12 13:06
哪位高手会快排的，麻烦贴一下，供大家学习学习
作者: 记忆Delete    时间: 2012-8-23 22:32
刚好对排序不熟，谢了。。。
作者: henk    时间: 2012-10-22 20:33
顶，感谢版主的分享~
作者: henk    时间: 2012-10-22 20:39
LZ，刚才试了下第一种排序，把代码完整复制下来，发现编译不了，截图如下，请问是什么问题呢
作者: jiejiezhu25    时间: 2012-10-26 11:14
非常不错！！！！！！！！！
作者: jiejiezhu25    时间: 2012-10-26 11:14

非常不错！！！！！！！！！
作者: 凡夫俗子    时间: 2012-10-26 19:49
henk 发表于 2012-10-22 20:39
LZ，刚才试了下第一种排序，把代码完整复制下来，发现编译不了，截图如下，请问是什么问题呢

谢谢指正错误，敲代码是粗心了点，现已改正（：
作者: henk    时间: 2012-11-16 20:35
[ 本帖最后由 henk 于 2012-11-16 20:46 编辑 ]\n\n

#include<stdio.h>
/*快速排序*/
int quick_sort(int *a, int n, int left, int right)
{
    int s, i, j;
    int temp;
    if(left < right)
       {
        s = a[left];
        i = left;
        j = right + 1;
        while(1)
           {
            while(i + 1 < n && a[++i] > s);
            while(j - 1 > -1 && a[--j] < s);
            if(i >= j)
           {
                break;
            }
            temp = a;
            a = a[j];
            a[j] = temp;
        }
        a[left] = a[j];
        a[j] = s;
        quick_sort(a, n, left, j - 1);
        quick_sort(a, n, j + 1, right);
    }
    return 0;
}
int main()
{
    int i,n;
    int arr[n];
    printf("请输入一个整数:");
    scanf("%d",&n);
    printf("请输入%d个整数:",n);
    for(i = 0; i < n; i++)
    {
        scanf("%d",&arr);      
    }
    for(i = 0; i < n; i++)
    {
        printf("arr[%d]=%d\n", i, arr);
    }
    quick_sort(arr, n, 0, (n-1));
    printf("排序后:\n");
    for(i = 0; i < n; i++) {
        printf("arr[%d]=%d\n", i, arr);
    }

    sleep(10000);   
    return 0;
}
作者: 凡夫俗子    时间: 2012-11-16 20:45
henk 发表于 2012-11-16 20:35
[ 本帖最后由 henk 于 2012-11-16 20:44 编辑 ]\n\n[ 本帖最后由 henk 于 2012-11-16 20:37 编辑 ]

#inc ...

??
作者: henk    时间: 2012-11-16 20:46
=student= 发表于 2012-11-16 20:45
??

刚才在修改，SORRY~现在好了
作者: rosynirvana    时间: 2013-5-30 23:00
1. 算法不依赖于语言，所以说某种语言有几种排序方法是不好的表达
另外如果把有文献讨论过的排序算法都算上，那么除了珠排序这种需要特殊计算机的排序算法，其他算法C都能很容易实现

2. 桶排序和基数排序是不同的两种算法，楼主给出的应该算是一种桶排序

3. 选择排序不是常用算法，因为太慢了
除非是在特别的计算机模型上（比如主存读取速度远远大于写入速度的硬件上）

4. 数组大小不是C语言的限制，而是特定环境下堆栈大小的限制，放在所有函数之外就不会发现这种问题。

5. 冒泡不一定比选择慢，对于一个长度为n的数组排序，冒泡的最佳情况是n-1次比较，而选择是(n+1)(n-2)次

6. 还有一种有名的排序算法没有提到，Shell sort(希尔排序)
作者: 超神级    时间: 2013-7-22 21:19
{:soso_e127:}



欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/) Powered by Discuz! X3.2