c语言之排序

比眉伴天荒 2022-07-16 11:49 62阅读 0赞

冒泡排序是排序算法的一种，思路清晰，代码简洁，常被用在大学生计算机课程中。  
  
“冒泡”这个名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。  
  
这里以从小到大排序为例进行讲解。

## 基本思想及举例说明 ##

冒泡排序的基本思想就是不断比较相邻的两个数，让较大的元素不断地往后移。经过一轮比较，就选出最大的数；经过第2轮比较，就选出次大的数，以此类推。  
  
下面以对 3  2  4  1 进行冒泡排序说明。  
  
第一轮 排序过程  
3  2  4  1    （最初）  
2  3  4  2    （比较3和2，交换）  
2  3  4  1    （比较3和4，不交换）  
2  3  1  4    （比较4和1，交换）  
第一轮结束，最大的数4已经在最后面，因此第二轮排序只需要对前面三个数进行再比较。  
  
第二轮 排序过程  
2  3  1  4 （第一轮排序结果）  
2  3  1  4 （比较2和3，不交换）  
2  1  3  4 （比较3和1，交换  
第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。  
  
第三轮 排序过程  
2  1  3  4  （第二轮排序结果）  
1  2  3  4  （比较2和1，交换）  
至此，排序结束。

## 算法总结及实现 ##

对于具有N个元素的数组R\[n\]，进行最多N-1轮比较；  
  
第一轮，逐个比较（R\[1\], R\[2\]）,  （R\[2\], R\[3\]）,  （R\[3\], R\[4\]）,  …….  （R\[N-1\], R\[N\]） ;  最大的元素会被移动到R\[N\]上。  
  
第二轮，逐个比较（R\[1\], R\[2\]）,  （R\[2\], R\[3\]）,  （R\[3\], R\[4\]）,  …….  （R\[N-2\], R\[N-1\]）；第二大元素会被移动到R\[N-1\]上。  
  
。。。。  
以此类推，直到整个数组从小到大排序。

下面给出了冒泡排序的一般实现和优化实现。一般实现是教科书里常见的实现方法，无论数组是否排序好了，都会进行N-1轮比较； 而优化实现，在数组已经排序好的情况下，会提前退出比较，减小了算法的时间复杂度。

#include<stdio.h>
    #include<stdlib.h>
    
    #define N 8
    
    void bubble_sort(int a[],int n);
    
    
    //一般实现
    void bubble_sort(int a[],int n)//n为数组a的元素个数
    {
        //一定进行N-1轮比较
        for(int i=0; i<n-1; i++)
        {
            //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
            for(int j=0; j<n-1-i; j++)
            {
                if(a[j] > a[j+1])
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1]=temp;
                }
            }
        }
    }
    
    //优化实现
    void bubble_sort_better(int a[],int n)//n为数组a的元素个数
    {
        //最多进行N-1轮比较
        for(int i=0; i<n-1; i++)
        {
            bool isSorted = true;
            //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
            for(int j=0; j<n-1-i; j++)
            {
                if(a[j] > a[j+1])
                {
                    isSorted = false;
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1]=temp;
                }
            }
            if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
        }
    }
    
    
    int  main()
    {
        int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
    
        bubble_sort(num, N); //或者使用bubble_sort_better(num, N);
    
        for(int i=0; i<N; i++)
            printf("%d  ", num[i]);
    
        printf("\n");
    
    
        system("pause");
        return 0;
    }

选择排序是排序算法的一种，这里以从小到大排序为例进行讲解。

## 基本思想及举例说明 ##

选择排序（从小到大）的基本思想是，首先，选出最小的数，放在第一个位置；然后，选出第二小的数，放在第二个位置；以此类推，直到所有的数从小到大排序。  
  
在实现上，我们通常是先确定第i小的数所在的位置，然后，将其与第i个数进行交换。  
  
下面，以对 3  2  4  1 进行选择排序说明排序过程，使用min\_index 记录当前最小的数所在的位置。  
  
第1轮 排序过程 （寻找第1小的数所在的位置）  
3  2  4  1（最初， min\_index=1）  
3  2  4  1（3 > 2， 所以min\_index=2）  
3  2  4  1（2 < 4， 所以 min\_index=2）  
3  2  4  1（2 > 1， 所以 min\_index=4， 这时候确定了第1小的数在位置4）  
1  2  4  3 （第1轮结果，将3和1交换，也就是位置1和位置4交换）  
  
第2轮 排序过程 （寻找第2小的数所在的位置）  
1  2  4  3（第1轮结果， min\_index=2，只需要从位置2开始寻找）  
1  2  4  3（4 > 2， 所以min\_index=2）  
1  2  4  3（3 > 2， 所以 min\_index=2）  
1  2  4  3（第2轮结果，因为min\_index位置刚好在第2个位置，无需交换）  
  
第3轮 排序过程 （寻找第3小的数所在的位置）  
1  2  4  3（第2轮结果， min\_index=3，只需要从位置2开始寻找）  
1  2  4  3（4 > 3， 所以min\_index=4）  
1  2  3  4（第3轮结果，将3和4交换，也就是位置4和位置3交换）

至此，排序完毕。

## 总结及实现 ##

选择排序对大小为N的无序数组R\[N\]进行排序，进行N-1轮选择过程。第i轮选取第i小的数，并将其放在第i个位置上。当第N-1次完成时，第N小（也就是最大）的数自然在最后的位置上。  
  
下面给出选择排序的C语言实现。

#include<stdio.h>
    #include<stdlib.h>
    
    #define N 8
    
    void select_sort(int a[],int n);
    
    
    //选择排序实现
    void select_sort(int a[],int n)//n为数组a的元素个数
    {
        //进行N-1轮选择
        for(int i=0; i<n-1; i++)
        {
    
            int min_index = i; 
            //找出第i小的数所在的位置
            for(int j=i+1; j<n; j++)
            {
                if(a[j] < a[min_index])
                {
                    min_index = j;
                }
            }
    
            //将第i小的数，放在第i个位置；如果刚好，就不用交换
            if( i != min_index)
            {
                int temp = a[i];
                a[i] = a[min_index];
                a[min_index] = temp;
            }
        }
    }
    
    
    int  main()
    {
        int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
    
        select_sort(num, N);
    
        for(int i=0; i<N; i++)
            printf("%d  ", num[i]);
    
        printf("\n");
    
    
        system("pause");
        return 0;
    
    }