C语言实现八大排序算法（一）

雨点打透心脏的1/2处 2022-02-23 00:12 189阅读 0赞

本文主要介绍数据结构中常见的八大排序算法，冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序。

**注：下面的排序代码有些我没编译跑过，可能有问题，但思想肯定是正确的，我用python重新编写并验证了一遍，代码可参考这** [python实现十大排序算法（详解）][python]

## 排序相描述 ##

1.  **排序分类：若排序过程中，所有的文件都是放在内存中处理的，不涉及数据的内外存交换，则称该排序算法是内部排序算法**; 若排序过程中涉及内外存交换，则是**外部排序**。内部排序适合小文间，外部排序适用于不能一次性把所有记录放入内存的大文件。常见的分类算法还可以根据排序方式分为两大类：**比较排序**和**非比较排序**。
2.  **排序算法的稳定性：** 若排序对象中存在多个关键字相同的记录，经过排序后，相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的，若次序发生变化(哪怕只有两条记录之间)，则该排序方法是不稳定的。关于哪些算法是稳定的，哪些不稳定，下面会详细介绍。
3.  **时间复杂度**：一般情况下，算法中基本操作重复执行的次数是问题规模 n n n的某个函数，用 T ( n ) T(n) T(n)表示，若有某个辅助函数 f ( n ) f(n) f(n)，使得 T ( n ) / f ( n ) T(n)/f(n) T(n)/f(n)的极限值（当 n n n趋近于无穷大时）为不等于零的常数，则称 f ( n ) f(n) f(n)是 T ( n ) T(n) T(n)的同数量级函数。记作 T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))，称 O ( f ( n ) ) O(f(n)) O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
4.  **空间复杂度**：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，它是问题规模 n n n的函数，记做 S ( n ) = O ( f ( n ) ) S(n)=O(f(n)) S(n)=O(f(n))。比如直接插入排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2),空间复杂度是 O ( 1 ) O(1) O(1)。而一般的递归算法就要有 O ( n ) O(n) O(n)的空间复杂度了，因为每次递归都要存储返回信息，需要辅助空间的大小随着 n n n的增大线性增大。
5.  **就地排序**：若一个排序算法所需的辅助空间并不依赖于问题的规模n，即时间复杂度是 O ( 1 ) O(1) O(1),则称该排序算法为就地排序。非就地排序算法的时间复杂度一般为 O ( n ) O(n) O(n)。

注：**算法是否稳定并不能衡量一个算法的优劣**，排序算法主要包含2种操作：**比较和移动**，但并不是所有的排序都基于比较操作，比如基数排序。

**下图为排序算法体系结构图：**

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

**各大排序算法的时间复杂度、空间复杂度及稳定性见下表：**

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

## 直接插入排序（Insertion Sort） ##

### 基本思想 ###

将待排序的无序数列看成是一个仅含有**一个元素的有序数列和一个无序数列**，将无序数列中的元素逐次插入到有序数列中，从而获得最终的有序数列。

### 算法流程 ###

1.  初始时，  a \[ 0 \] a\[0\] a\[0\]自成一个有序区， 无序区为 a \[ 1 , . . . , n − 1 \] a\[1, ... , n-1\] a\[1,...,n−1\], 令 i = 1 i=1 i=1;
2.  将 a \[ i \] a\[i\] a\[i\]并入当前的有序区 a \[ 0 , . . . , i − 1 \] a\[0, ... , i-1\] a\[0,...,i−1\];
3.   i + + i++ i\+\+并重复步骤2，直到 i = n − 1 i=n-1 i=n−1, 排序完成。

**详细描述如下：**

1.  从第一个元素开始，该元素可以认为已经被排序
2.  取出下一个元素，在已经排序的元素序列中从后向前扫描
3.  如果该元素（已排序）大于新元素，将该元素移到下一位置
4.  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.  将新元素插入到该位置中
6.  重复步骤2

**复杂度分析：**  
第1个元素，需要进行 0 次比较;  
第2个元素，需要进行 1 次比较;  
第3个元素，需要进行 2 次比较;  
第n个元素，需要进行n-1次比较;

所以**插入排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，空间复杂度是 O ( 1 ) O(1) O(1)，稳定**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 2]

**动态实例**  
![20181108191925813.gif][]

### 算法实现 ###

//直接插入法一
    void InsertSort1(int a[], int n)
    {
        
        int i, j;
        for(i=1; i<n; i++)
            if(a[i] < a[i-1])   
            {
        
                int temp = a[i];                       //保存要比较的值
                for(j=i-1; j>=0 && a[j]>temp; j--)    //从后向前查找待插入位置
                    a[j+1] = a[j];                    //挪位
                a[j+1] = temp;                       //复制到插入位置
            }
    }
    
    //直接插入法二：用数据交换代替法一的数据后移(比较对象只考虑两个元素)
    void InsertSort2(int a[], int n)
    {
        
        for(int i=1; i<n; i++)
            for(int j=i-1; j>=0 && a[j]>a[j+1]; j--)
                Swap(a[j], a[j+1]);
    }
    void Swap(int a,int b){
        
        int temp;
        temp=a;
        a=b;
        b=temp;
    }

### 拓展（折半插入排序） ###

**仅适用于顺序存储的线性表**  
**直接插入排序**是边比较，边移动元素；  
**折半插入排序**是先折半查找到插入位置，再统一移动元素

void ZhebanInsertSort(int a[],int n){
        
        int i,j,low,high,mid;
        for(i=1;i<n;i++){
        
            temp=a[i];
            low=1,high=i;            //设置折半查找范围
            while(low<=high){
        
                mid=(low+high)/2;  
                if(a[mid]>temp) 
                    high=mid-1;        //查找左半部分
                else
                    low=mid+1;        //查找右半部分
            }
            for(j=i;j>=high+1;--j)
                a[j+1]=a[j];          //统一后移元素，空出插入位置
            a[high+1]=temp;           //插入
        }
    }

## 希尔排序（Shell Sort） ##

希尔排序是第一个突破 O ( n 2 ) O(n^2) O(n2)的排序算法，是**简单插入排序的优化，实质是分组的简单插入排序**。它与插入排序的不同之处在于，它**会优先比较距离较远的元素**(每次取相隔一定间隔gap的元素作为一组，在组内执行简单插入排序)。希尔排序又叫**缩小增量排序**（**不断减小间隔gap的数组，直到gap=1**）。

### 基本思想 ###

1.  希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
2.  随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。

### 算法流程 ###

1.  选择一个增量序列 t 1 ， t 2 ， … ， t k t\_1，t\_2，…，t\_k t1，t2，…，tk，其中 t i > t j ， t k = 1 t\_i>t\_j，t\_k=1 ti>tj，tk=1；
2.  按增量序列个数 k k k，对序列进行$k $趟排序；
3.  每趟排序，根据对应的增量 t i t\_i ti，将待排序列分割成若干长度为 m m m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

**时间复杂度为 O ( n 1 + e ) O(n^\{1+e\}) O(n1\+e)(其中0<e<1)，空间复杂度 O ( 1 ) O(1) O(1)，不稳定**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 3]

**动态实例**  
![20181108192122882.gif][]

### 算法实现 ###

//希尔排序法一
    void shellSort1(int a[],int n){
        
        int i,j,gap,temp;
        for(gap = n/2;gap>0;gap/=2){
        
            for(i=gap;i<n;i+=gap){
        
                temp = a[i];
                for(j = i-gap;j>=0&&a[j]>temp;j-=gap){
        
                    a[j+gap] = a[j];
                }
                a[j+gap] = temp;
            }
        }
    }
    //希尔排序法二，和上面的直接插入排序类似，用数据交换代替法一的数据后移(比较对象只考虑两个元素)
    void ShellSort2(int a[], int n)
    {
        
        int i, j, gap;
        //分组
        for(gap=n/2; gap>0; gap/=2)
            //直接插入排序
            for(i=gap; i<n; i++)
                for(j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap)
                    Swap(a[j], a[j+gap]);
    }

## 冒泡排序（Bubble Sort） ##

### 基本思想 ###

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下**对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒**。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。每一趟排序后的效果都是讲没有沉下去的元素给沉下去。

### 算法流程 （递增为例） ###

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
3.  针对所有的元素重复以上的步骤，除了最后一个
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

**复杂度分析**  
第一次排序的比较次数：$ n-1$ n个元素相邻两两比较，需要n-1次比较;  
第二次排序的比较次数：$ n-2$ 第一次排序后最后一个元素可以确定为最大值，不再需要参与第二次排序;  
第三次排序的比较次数：  n − 3 n-3 n−3 同理，最后两个数已经确定，不再需要参与排序;  
第 n-1 次排序的比较次数：  1 1 1 ;

**所以冒泡排序的时间复杂度是  O ( n 2 ) O(n^2) O(n2)。 空间复杂度是  O ( 1 ) O(1) O(1)，稳定** 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 4]

**动态实例**  
![20181108191123628.gif][]

### 算法实现 ###

//冒泡排序
    void BubbleSort(int a[], int n)
    {
        
        int i, j;
        for(i=0; i<n; i++){
        
            bool flag=false;              //表示本趟冒泡是否发生交换的标志
            for(j=1; j<n-i; j++){
                 //j的起始位置为1，终止位置为n-i  
                if(a[j]<a[j-1]){
        
                   Swap(a[j-1], a[j]);
                    flag=true;
                }
            }
            if(flag==false)             //未交换，说明已经有序，停止排序
                return;
        }          
    }

### 拓展 （冒泡排序的改进 ---- 鸡尾酒排序） ###

**鸡尾酒排序**与冒泡排序的不同处在于**排序时是以首尾双向在序列中进行排序**。

1.  先对数组从左到右进行升序的冒泡排序；
2.  再对数组进行从右到左的降序的冒泡排序；
3.  以此类推，持续的、依次的改变冒泡的方向，并不断缩小没有排序的数组范围；

**鸡尾酒排序的优点是能够在特定条件下（如集合中大部分元素有序），减少排序的回合数**。

实现鸡尾酒排序需要分别定义一个从最左边开始的index\_left和从最右边开始的index\_reight，当两个index相等的时候循环结束。

//鸡尾酒排序
    void CocktailSort(int a[], int n){
        
        int left = 0, right=n-1;
        while(left<right){
        
            for(int i=left;i<right-1;i++){
               //从前往后排
                if(a[i]>a[i+1]){
        
                    Swap(a[i],a[i+1]);
                }           
                right-=1;
                for(int j=right;j>left;j--){
             //从后往前排
                    if(a[j]<a[j-1]){
        
                        Swap(a[j],a[j-1]);
                    }
                }
                left+=1;
            }
        }    
    }

## 快速排序（Quick Sort） ##

**快速排序**是目前所有**内部排序**算法中**平均性能最优**的排序算法。

### 基本思想 ###

快速排序算法的基本思想为分治思想。

1.  先从数列中取出一个数作**轴值（基准数）pivot**；
2.  根据基准数将数列进行分区，小于基准数的放左边，大于基准数的放右边；
3.  重复分区操作，知道各区间只有一个数为止。

### 算法流程（递归+挖坑填数） ###

1.   i = L ， j = R i=L，j=R i=L，j=R，将基准数挖出形成第一个坑 a \[ i \] a\[i\] a\[i\]；
2.   j − − j-- j−−由后向前找出比它小的数，找到后挖出此数 a \[ j \] a\[j\] a\[j\]填到前一个坑 a \[ i \] a\[i\] a\[i\]中；
3.   i + + i++ i\+\+从前向后找出比它大的数，找到后也挖出此数填到前一个坑 a \[ j \] a\[j\] a\[j\]中；
4.  再重复2,3，直到 i = j i=j i=j，将基准数填到 a \[ i \] a\[i\] a\[i\]。

**复杂度分析：**  
**时间复杂度为 O ( n l o g 2 n ) O(nlog\_\{2\}^\{n\}) O(nlog2n)，空间复杂度为 O ( l o g 2 n ) O(log\_2^n) O(log2n)，不稳定**。

下面是一个我手写的详细分析实例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 5]

**动态实例**  
![20181108192522752.gif][]

### 算法实现 ###

//快速排序
    void QuickSort(int a[],int left,int right){
        
        if(left<right){
        
            int i=left,j=right；
            int base=a[left];             //基准
            while(i<j){
        
                while(i<j&&a[j]>=base)    //从右往左找小于base的元素
                    j--;
                if(i<j)
                    a[i++]=a[j];
                while(i<j&&a[i]<base)    //从左往右找大于base的值
                    i++;
                if(i<j)
                    a[j--]=a[i];
            }
            a[i]=base;                  //将基准base填入最后的坑中
            QuickSort(a,left,i-1);      //递归调用，分治
            QuickSort(a,i+1,right);
        }
    }

**注意**：如果基准不是选第一个数，可以用Swap()函数将基准调整至第一个位置，再执行上述程序。

**总结**：本文主要介绍了2大类排序算法：**插入排序**（直接插入、希尔排序）和**交换排序**（冒泡排序、快速排序）。在下一篇博文[C语言实现八大排序算法（二）][C]中，我将介绍剩下的4种排序（简单选择排序、堆排序、归并排序、基数排序），并对所有的排序算法做一个比较。

[python]: https://blog.csdn.net/bluesliuf/article/details/89979980
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center]: /images/20220223/0bb7785a58a145578b86ab8070a1a097.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220223/dbcd8360c92d41cbbd882f928edda2dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220223/9c391c265b5b46db945799ab43226637.png
[20181108191925813.gif]: /images/20220223/d276a1ba63174051bf22509ae42cca4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220223/955b5ca934194bee9e3e41576018da5b.png
[20181108192122882.gif]: /images/20220223/69602c9544604e7685c45535d8b6beb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220223/f81ec4eaeb4644dbb5618de45ba52d03.png
[20181108191123628.gif]: /images/20220223/09ea9098c72745a7b6348a97c7ccbc5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20220223/39a0b59b75e6409c8271670ac7e1e926.png
[20181108192522752.gif]: /images/20220223/d5ac4df3bc144f86bcfd6cebd7a01e0e.png
[C]: https://blog.csdn.net/bluesliuf/article/details/89055198