郝斌数据结构7排序之冒泡选择

Myth丶恋晨 2022-03-02 15:10 233阅读 0赞

一. 冒泡排序  
比较相邻的元素。如果第一个比第二个大，就交换他们两个  
对每一对相邻元素作同样的工作。第一次后，最后的元素是最大的数  
针对所有的元素重复以上的步骤，除了最后一个  
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190320192243632.png]  
二. 选择排序  
首先通过n-1 次比较，从n个数中找出最小的，将它与第1个数交换。第一次结束，最小的数放在第1个  
再通过n-2次比较，从剩余的n-1个数中找出最小的，将它与第二个数交换。  
第二次结束，次小的数放在第2个  
重复上述过程

区别在于：  
冒泡算法，每次比较如果发现较小的元素在后面，就交换两个相邻的元素  
而选择排序算法的改进在于：  
先并不急于调换位置，先从a\[0\]开始逐个检查，看哪个数最小就记下该数所在的位置P。等一次 扫描完毕，再把a\[P\]和a\[0\]对调，这时a\[0\]到a\[9\]中最小的数据就换到了最前面。  
所以，选择排序每扫描一次数组，只需要一次真正的交换，而冒泡可能需要很多次。但是他俩比 较的次数是一样的。  
一句话总结：选择是通过下标改动来排，冒泡则直接交换。  
程序如下:

#include<stdio.h>
    int main(int argc, const char *argv[])
    { 
    int i,j,k = 0;
    int a[10] = { 1,3,5,7,9,2,4,6,8,0};
    for(i = 0;i < sizeof(a)/sizeof(a[0]) -1;i++)
    { 
            k = i;
            for(j = i + 1;j < sizeof(a)/sizeof(a[0]);j++)
            { 
                   if(a[j] < a[k])
                   { 
                          k = j; //k是最小值的下标
                   }
            }
            if(i != k)
            { //例如第一次循环，a[0]如果不是最小的，就把a[0]换成最小的
                   a[i] ^= a[k];
                   a[k] ^= a[i];
                   a[i] ^= a[k];
            }
    }
    for(i = 0;i < sizeof(a)/sizeof(a[0]);i++)
    { 
            printf("a[%d] = %d\n",i,a[i]);
    }
    return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/c367e16b982446cc9f983b715ed219f0.png
[20190320192243632.png]: /images/20220302/037592ea494b496cb8f44954fff0a225.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]: /images/20220302/1a0eaae548f8437e9ec87b0e5d9d78f5.png