冒泡排序法和选择排序法

拼搏现实的明天。 2022-06-01 05:30 238阅读 0赞

语言中，常用的算法有：冒泡排序、快速排序、插入排序、选择排序、希尔排序、堆排序以及归并排序等等。那么从这篇开始，我将分别总结下这几种排序法。  
  
先交代一下，我们将要排序的数组定义为arr\[N\],即数组arr\[\]包含N个元素。  
  
\#\# 冒泡排序法（Bubblesort） \#\#  
  
所谓排序法，就是对一组无序的序列进行有序的排序（从大到小或者从小到大），那么什么叫冒泡排序法，冒泡排序法又是怎么实现数组的有序排列呢。  
  
冒泡排序法的具体实现方法是这样的，从数组的第一个元素\`arr\[0\]\`开始，**两两比较\*\*(\`arr\[n\],arr\[n+1\]\`)，如果前面的数大于后面的数（\`arr\[n\] > arr\[n+1\]\`）,那么交换两个元素的位置，把大的数往后移动。这样依次经过一轮比较以后，最大的数将会被交换到最后的位置（arr\[n-1\]）。  
  
先一起再来看看冒泡排序法是怎么排序的。  
    
  数组排序前    7    23    12    4    33    21    2    17    13    9            
  第一轮排序    7    12    4    23    21    2    17    13    9    33      
  第二轮排序    7    4    12    21    2    17    13    9    23      
  第三轮排序    4    7    12    2    17    13    9    21                   
  第四轮排序    4    7    2    12    13    9    17      
  第五轮排序    4    2    7    12    9    13          
  第六轮排序    2    4    7    9    12          
  第七轮排序    2    4    7    9      
  第八轮排序    2    4    7     
  第九轮排序    2    4        
  
可以看到，每一轮的排序，在这一轮中参与比较的元素中最大的数将会浮到最后。而冒泡排序的名字也是从这里来的 。  
  
C语言实现Bubblesort：**

#include <stdio.h>
    
    
    void bubble_sort(int a[], int m)
    {
        int i,j;
        int tmp;
        int flag = 0;  //设定标志，如果第一次循环比较时没有发生交换，则说明数组是升序排序，不用排序，提前结束循环。
        
        for(i = 0; i < m - 1; i++)       //外层循环控制循环次数
        {
            flag = 0;
            
            for(j = 0; j < m-1-i; j++)   //内层循环控制每次循环里比较的次数。
            {
                if(a[j] > a[j+1])
                {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    flag = 1;
                }
            }
           
            if(0 == flag)
            {
                printf("No Sort, i(%d) !!!\n", i);
                break;
            }
        }
    }
    
    
    int main()
    {
        int i = 0;
        int a[10] = {7, 23, 12, 4, 33, 21, 2, 17, 13, 9};
        
        for(i = 0; i < 10; i++)
        {
            printf("%d, ", a[i]);
        }
        printf("\n");
        
        bubble_sort(a, 10);
        
        for(i = 0; i < 10; i++)
        {
            printf("%d, ", a[i]);
        }
        printf("\n");
        
        return 0;
    }

**\#\# 选择排序法（Selectionsort） \#\#  
  
所谓的选择是什么意思呢，选择就是于万千花丛中择其一，在选择排序法中说的就是，每一次循环过程中，通过比较选择出你需要的\*\*最值\*\*。  
  
选择排序法的过程是，通\*\*过比较，选择出每一轮中最值元素，然后把他和这一轮中最最前面的元素交换\*\*，所以这个算法关键是要记录每次比较的结果，即每次比较后最值位置（下标）。  
  
先来看看选择排序的过程：  
  
数组排序前    7    23    12    4    33    21    2    17    13    9        
第一轮循环    2    23    12    4    33    21    7    17    13    9            
第二轮循环          4      12    23    33    21    7    17    13    9      
第三轮循环                  7      23    33    21    12    17    13    9      
第四轮循环                           9      33    21    12    17    13    23           
第五轮循环                                   12    21    33    17    13    23      
第六轮循环                                           13    33    17    21    23     
第七轮循环                                                   17    33    21    23      
第八轮循环                                                           21    33    22     
第九轮循环                                                                    22    33  
  
通过这个过程，我们可以看到，每轮循环过程中，都会找出这个最值元素，下一轮排序时就不用再考虑这个元素了。  
  
C语言实现（Selectionsort）**

![复制代码][copycode.gif]

1     void selectionsort(int a[],int m)
     2     {
     3         int i,j;
     4         int k;
     5         int tmp;
     6 
     7         for(i = 0; i < m-1; i++)//控制循环次数，n个数需要n-1次循环
     8         {
     9             k = i;
    10             for(j = i+1; j < m ; j++)
    11             {
    12                 if(a[j] < a[k])
    13                     k = j;
    14             }
    15             //i不等于k是就证明a[i]不是最小的，
    16             //i等于k时证明a[i]就是本轮比较过程中最小的值
    17             if(i != k)
    18             {
    19                 tmp = a[i];
    20                 a[i] = a[k];
    21                 a[k] = tmp;
    22             }
    23         }
    24     }

![复制代码][copycode.gif]

**\#\# 总结 \#\#  
冒泡排序法是两两依次比较，并做交换，交换的次数多。  
选择排序法是每次循环找出最值，循环结束后将最值调整到合适位置，交换的次数少。**

**本文转自：**

**https://www.cnblogs.com/banana201/p/4928733.html**

[copycode.gif]: /images/20220601/915808b9aa384374840f9de1bba4245a.png