首页 > 编程语言 > 详细

经典排序:冒泡排序+选择排序 小结

时间:2018-01-14 00:24:15      阅读:97      评论:0      收藏:0      [点我收藏+]

标签:==   pid   targe   style   判断   tar   dex   put   i++   

经典排序:冒泡排序+选择排序

FJUTOJ 1842

冒泡排序

原理是取相邻两个数进行大小比较,判断是否交换。

以从小到大排序为例,冒泡排序就像气泡一样,最小的数慢慢浮上来,最大的数慢慢沉下去。那么完整从头到尾做一次之后最后一位就是原序列中最大的数字了。然后只需要对1~(n-1)个数字进行排序,完成后倒数第二个数字也为原序列的1~n-1元素中最大的值。如此重复,进行n-1次一定能完成排序。参考代码:

 1 #include <stdio.h>
 2 void BubbleSort(int *, int);
 3 int main()
 4 {
 5     int a[] = {9,5,3,6,7,2,5,4,3,9}, i;
 6     int s = sizeof(a) / sizeof(int);
 7     puts("Before sort:");
 8     for(i = 0; i < s; i++)
 9         printf("%d ",a[i]);
10     BubbleSort(a,s);
11     puts("\nAfter sort:");
12     for(i = 0; i < s; i++)
13         printf("%d ",a[i]);
14     return 0;
15 }
16 void BubbleSort(int *a, int s)
17 {
18     int i, j, tmp;
19     for(i = 0; i < s-1; i++)
20     {
21         for(j = 1; j < s-i; j++)
22         {
23             if(a[j-1] > a[j])
24             {
25                 tmp = a[j-1];
26                 a[j-1] = a[j];
27                 a[j] = tmp;
28             }
29         }
30     }
31 }

然后可以进行一个优化就是如果一整趟下来都没有一次交换,那么确定该序列已经满足单调,直接跳出循环可以省时。代码如下

 1 void BubbleSort(int *a, int s)
 2 {
 3     int i, j, tmp;
 4     char swap;
 5     for(i = 0; i < s-1; i++)
 6     {
 7         swap = 0;
 8         for(j = 1; j < s-i; j++)
 9         {
10             if(a[j-1] > a[j])
11             {
12                 swap = 1;
13                 tmp = a[j-1];
14                 a[j-1] = a[j];
15                 a[j] = tmp;
16             }
17         }
18         if(swap == 0) break;
19     }
20 }

 

选择排序

以从小到大排序为例。原理是在序列中挑一个最小的值,然后与序列中的第一个交换。那么,第一个就是整个序列中最小的数字。再对从第二个数字开始的序列做这个操作,得到剩余序列中最小的数字所在位置,与原序列第二个数交换,以此类推做n-1完成排序。参考代码:

void SelectSort(int *a, int s)
{
    int i, j, tmp, min_num_index;
    for(i = 0; i < s-1; i++)
    {
        min_num_index = i;
        for(j = i+1; j < s; j++)
        {
            if(a[j] < a[min_num_index])
                min_num_index = j;
        }
        if(min_num_index != i)
        {
            tmp = a[i];
            a[i] = a[min_num_index];
            a[min_num_index] = tmp;
        }
    }
}

 

以上代码和文字均手打,有误还请指正!

经典排序:冒泡排序+选择排序 小结

标签:==   pid   targe   style   判断   tar   dex   put   i++   

原文:https://www.cnblogs.com/sandychn/p/8280817.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号