C++笔记：结合他人博文总结数组的几种常用排序法(如有误或补充，请读者留言指出，持续学习更新)

墨蓝 2021-10-30 00:36 265阅读 0赞

### 文章目录 ###

*  插入排序法（稳定）
 *   *  简介
     *  分类
     *   *  直接插入排序（完全无序的序列用插入排序法排序）
         *  直接插入排序（将一个元素插入有序序列）
         *  二分查找法
         *   *  递归方式优化
             *  非递归方式优化
     *  适用场景
 *  希尔排序法（插入排序的改良版：该方法实质上是一种分组插入方法）（不稳定）
 *   *  简介
     *  实例代码
     *  适用场景
 *  冒泡排序法（稳定）
 *   *  简介
     *  实例代码
     *  适用场景
 *  快速排序法(对冒泡排序的一种改进)（不稳定）
 *   *  简介
     *  实例代码
     *  使用场景
 *  选择排序法（冒泡排序法的改进）（不稳定）
 *   *  简介
     *   *  简单选择排序
         *   *  实例代码
     *  树形选择排序（暂不讨论）
     *   *  堆排序（暂不讨论）
     *  使用场景
 *  归并排序法（稳定）
 *   *  简介
     *  分类
     *   *  递归法
         *  循环法
     *  使用场景

简介部分摘自百度百科  
动图部分摘自简书博客https://www.jianshu.com/p/f127bcc3d90e（写的非常好）

**术语说明：**

*  **稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；**
 *  **不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；**
 *  **内排序：所有排序操作都在内存中完成；**
 *  **外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；**
 *  **时间复杂度： 一个算法执行所耗费的时间。**
 *  **空间复杂度：运行完一个程序所需内存的大小。**

# 插入排序法（稳定） #

## 简介 ##

（一）概念：插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。  
（二）算法描述：

*  把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
 *  从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
 *  重复上述过程直到最后一个元素被插入有序子数组中。

（三）动图演示：  
![在这里插入图片描述][20190820144733163.gif]

## 分类 ##

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。

### 直接插入排序（完全无序的序列用插入排序法排序） ###

#include<iostream>
    #include<windows.h>
    using namespace std;
    void insertSort(int a[],  int length)
    { 
     int tmp;//临时变量
     for (int i=1;i<length;i++)//遍历a[1]~a[9]
     { 
      for (int j=i-1;j>=0&&a[j+1]<a[j];j--)//不符合升序的序列，才进入内层循环进行替换
      { 
       tmp=a[j];
       a[j]=a[j+1];
       a[j+1]=tmp;
      }
     } 
    }
    int main(){ 
     SetConsoleOutputCP(65001);
     int a[] = { 3,6,12,43,12,34,12,13,21,10};
     insertSort(a, 10);
     for (int i = 0; i < 10; i++)
     { 
      cout << a[i] << " ";
     }
     cout << endl;
     system("pause");
     return 0;
    }

输出：  
![在这里插入图片描述][20190820153049180.PNG]  
解释：关注insertSort()函数体，外层for循环从1开始，表示默认a\[0\]有序，然后从a\[1\]~a\[9\]依次插入排序。

当i=1时：进入外层for循环，j的取值范围为0,但由于内层循环条件a\[j+1\]<a\[j\]不符合，无法进入。

当i=2时：进入外层for循环，j的取值范围为0~1，但由于内层循环条件a\[j+1\]<a\[j\]不符合，无法进入。

当i=3时：同上，目前，即a\[3\]~a\[0\]仍是升序的序列，不进行任何操作

当i=4时：符合内层循环条件a\[j+1\]<a\[j\]（不符合升序排列），即前一个元素a\[3\]>后一个元素a\[4\]，进入内层循环，交换a\[3\]与a\[4\]，此时a\[0\]~a\[4\]都符合升序排列，此时排列为3,6,12,12,43,34,12,13,21,10，退出内层循环

当i=5时：符合内层循环条件a\[j+1\]<a\[j\]（不符合升序排列）,交换a\[5\]与a\[4\]，此时  
排序为3,6,12,12,34,43,12,13,21,10。

当i=6时：  
。。。。。。

当i=7时：  
。。。。。。

总结：该程序运行过程就是，假设第一个元素有序，第二个元素与第一个元素比较排序，此时元素一与元素二组成一个有序序列，接着元素三插入该有序序列，由于此时该有序序列已经是一个升序的序列，所以元素三只会比较排序到元素二，再次以元素一和元素二和元素三组成一个有序序列，再插入第四个元素，此时第四个元素也只会比较到元素3，后面的情况以此类推

### 直接插入排序（将一个元素插入有序序列） ###

参考：https://blog.csdn.net/qq\_15029743/article/details/79526902

#include <iostream>
    using namespace std;
    int main()
    { 
     int a[11] = {  1, 2, 13, 17, 28, 40, 56, 78, 89, 100 };//已经排序好的数组
     int num, i, j;
     cout << "now the array is:" << endl;
     for (i = 0; i<10; i++)
     { 
      cout << a[i] << " ";
     }
     cout << endl << "insert the array is:" << endl;
     cin >> num;
     if (num>a[9])
     { 
      a[10] = num;
     }
     else
     { 
      for (i = 0; i<10; i++)//将已经排好序的元素遍历出比num变量值第一个大的个元素，从该元素下标开始进行下标移动，赋值操作
      { 
       if (a[i]>num)//外循环从已排好序的数组第一个元素到最后一个元素判断如果大于输入的num，则进入内循环
       { 
        for (j = 9; j >= i; j--)//内循环负责将比num大的元素逐一后移一个单位
        { 
         a[j + 1] = a[j];
        }
        a[i] = num;
        break;
       }
      }
     }
     cout << "now the array is:" << endl;
     for (i = 0; i<11; i++)
     { 
      cout << a[i] << " ";
     }
     cout << endl;
     system("pause");
     return 0;
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]解释：  
此处在if (a\[i\]>num)中，根据我输入的31，确定a\[5\]=40>31,进入第二层for循环，第二层for循环变量j的取值范围为\[9,5\],a\[5\]赋值为插入元素num变量，原a\[5\]元素后移一个下标存储为a\[6\]，即将较小的插入元素插入到比较元素的左边，第二层for循环的作用即是将原数组a下标为9-5的逐一后移一个下标（此处需要注意，必须是原数组的最后一个元素开始逐个向后移动，即a\[9\]->a\[10\]，a\[8\]->a\[9\]…而不能从a\[5\]->a\[6\],a\[6\]->a\[7\]…原因就在于a\[6\]原来的值被a\[5\]覆盖了。）。然后此时在外层for循环内，内层for循环外，a\[5\]的值就可被num变量覆盖了，然后重新打印输出排序的数组。

### 二分查找法 ###

参考：  
https://baike.baidu.com/item/二分查找/10628618?fr=aladdin  
https://blog.csdn.net/luoweifu/article/details/16656737  
算法要求：

*  必须采用顺序存储结构（在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。）。
 *  必须按关键字大小有序排列。

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。确切来说，该算法有前提要求数组中元素按关键字有序排列。它主要是用来快速查找的。优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。  
（1）递归

#include<iostream>
    #include <windows.h>
    using namespace std;
    int a[100]={ 1,2,3,5,12,13,15,15,29,29};//数组中的数（由小到大）,此处数组有重复，重复的元素返回第一此出现的元素下标
    int k;//要找的数字
    int found(int x,int y)
    { 
        int m=x+(y-x)/2;//此处m=4，向零取整
        if(x>y)//查找完毕没有找到答案，返回-1,下标输入错误
            return -1;
        else
        { 
            if(a[m]==k)//首先判断中间元素a[4]是否与要查找的数组元素相等
                return m;//找到!返回位置.
            else if(a[m]>k)
                return found(x,m-1);//找左边
             else
                return found(m+1,y);//找右边
        }
    }
    int main()
        { 
      SetConsoleOutputCP(65001);
      cout<<"请输入要查找对应下标的数组元素："<<endl;
            cin>>k;//输入要找的数字c语言把cin换为scanf即可
            cout<<found(0,9);//从数组a[0]到a[9]c语言把cout换为printf即可
            return 0;
        }

输出：  
![在这里插入图片描述][20190819152636617.PNG]  
解释：第一次调用函数found(0-9)，m=4（中间下标），第一次函数递归（found函数第二次调用）found(5,9)，m=7（中间下标）,根据程序算法首先判断中间下标与输入的num变量是否相等，所以此处相等，直接输出下标7。函数结束，返回主函数。  
然后我们再测试一下输入一个29，然后运行结果：  
![在这里插入图片描述][20190819153006939.PNG]  
这里有细心的读者就会发现，自定义的数组a有重复元素，而对于本算法来说对于重复数组元素确定其下标是随机的，即重复数组元素在数组中定义的顺序，如上我分别测试了两次，第一次输出重复元素最右边的下标7，第二次输出重复元素最左边下标8。既然遇到了这个问题，那么我们就开始想怎么制定一个标准，是统一输出第一个出现重复元素的下标，还是统一输出最后一个出现重复元素的下标。接着看优化代码

#### 递归方式优化 ####

此处递归的优化暂时没编写测试成功，如有例子请读者留言网址，不胜感激！

（2）非递归（循环）

/* 非递归的二分查找 arrat：数组 ， n:数组最大下标值; target:查找的数据； 返回target所在数组的下标 */
    #include<iostream>
    #include <windows.h>
    using namespace std;
    int found(int array[], int n, int target) { 
     int low = 0, high = n, middle = 0;
     while(low < high) { 
      middle = (low + high)/2;//middle=4，向零取整
      if(target == array[middle]) { //先比较中间元素
       return middle;
      } else if(target < array[middle]) { //判断目标元素与中间元素值的大小，缩小1/2范围
       high = middle;
      } else if(target > array[middle]) { //判断目标元素与中间元素值的大小，缩小1/2范围
       low = middle + 1;
      }
     }
     return -1;
    }
    int main(){ 
     int a[100]={ 1,2,3,5,12,13,15,15,29,29};
     int n=9;
     int k;
     SetConsoleOutputCP(65001);
     cout<<"请输入要查找对应下标的数组元素："<<endl;
        cin>>k;//输入要找的数字c语言把cin换为scanf即可
     cout<<found(a,n,k);
     return 0;
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]  
解释：输入15，调用found()函数，接着计算中间下标值middle=4(向零取整)，求得a\[4\]=12，15>12,执行第二个else if子句，此时low=5,high=9,数组下标区间缩小为\[5,9\]，再次while循环判断low<high,第二次进入while循环，此时middle=(5+9)/2=7，a\[7\]=15，直接第一条if语句判断成功,返回下标7，再继续测试输入29，运行结果为：  
![在这里插入图片描述][20190819171759290.PNG]  
这里直接从第二次while循环开始解释，第一次while循环判断结果和输入15的情况一致，第二次while循环，middle=7,a\[7\]=15,target=29,根据判断，执行第二个else if子句，此时low=8,high=9，数组下标区间缩小为\[8,9\]，再次while循环判断low<high，第三次进入while循环，此时middle=(8+9)/2=8(向零取整)，直接第一个If语句判断出a\[8\]=29=target=29，退出found函数，返回主函数输出结果。此处仍是重复元素的查找问题，与递归方式一样的输出结果，所以仍需优化代码。

#### 非递归方式优化 ####

参考：  
https://blog.csdn.net/weixin\_42124234/article/details/99817661

/* flag=0,获取最左目标,flag=1，获取最右侧目标 */
    #include<iostream>
    #include <windows.h>
    using namespace std;
    int found(int arr[], int n, int target,int flag){ 
     int low=0;
     int high=n;
     if(flag==0){ 
      while(low < high){ 
      int mid = (low + high)/2;//4,7,6,5
      if(arr[mid] >= target){ 
       high = mid;//[5,7],[5,6]
      }
      else{ 
       low = mid + 1; //[5,9],[6,6]
      }
     }
     if(arr[high] == target){ 
      return high;
     }
     }else if(flag==1){ 
      while(low < high){ 
      int mid = (low + high)/2+1;
      if(arr[mid] <= target){ 
       low = mid;
      }
      else{ 
       high = mid - 1;
      }
     }
     if(arr[high] == target){ 
      return high;
     }
     }else{ 
      cout<<"flag参数设置错误！"<<endl;
     }
     return -1;
    }
    int main(){ 
     int a[100]={ 1,2,3,5,12,13,15,15,29,29};//middle依次为a[4]=12,a[7]=15(第二个),a[8]=29(第一个)
     int n=9;
     int k;
     int flag;
     SetConsoleOutputCP(65001);
     cout<<"请输入要查找对应下标的数组元素："<<endl;
        cin>>k;//输入要找的数字c语言把cin换为scanf即可
     cout<<"设置数组重复元素查找模式参数flag(0:获取最左目标(默认)；1：获取最右侧目标):"<<endl;
     cin>>flag;
     cout<<"下标："<<found(a,n,k,flag);
     return 0;
    }

运行结果：  
![在这里插入图片描述][20190820093336847.PNG]  
![在这里插入图片描述][20190820093352629.PNG]

总结：使用递归方法解决问题的特点是：问题描述清楚，代码量比非递归函数少。缺点就是递归程序的运行效率低，无论是从时间角度还是空间角度都比非递归程序差。所以能用循环的尽量不用递归。

评价排序算法优劣的标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应；另一个是执行算法所需要的附加存储单元的的多少。

## 适用场景 ##

在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。

# 希尔排序法（插入排序的改良版：该方法实质上是一种分组插入方法）（不稳定） #

## 简介 ##

（一）希尔排序(Shell’s Sort)是插入排序的一种又称“增量递减排序算法”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

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

我们都知道插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，Shell排序是一个不稳定的算法。

https://blog.csdn.net/weixin\_37818081/article/details/79202115具体实现原理可以参考这篇博客，插图讲的通俗易懂，我看百度百科也是迷迷糊糊的。  
（二）算法描述：

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

（三）动图演示：

![在这里插入图片描述][20190820163023369.gif]  
希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）  
下面是一些常见的增量序列：

*  **第一种增量是最初Donald Shell提出的增量，即折半降低直到1**。据研究，使用希尔增量，其时间复杂度还是O(n2)。
 *  第二种增量Hibbard：\{1, 3, …, 2k-1\}。该增量序列的时间复杂度大约是O(n1.5)。
 *  第三种增量Sedgewick增量：(1, 5, 19, 41, 109,…)，其生成序列或者是94^i - 92^i + 1或者是4^i - 3\*2^i + 1。

首先，**选择增量第一种增量方式 gap = 10/2** ，缩小增量继续以 gap = gap/2 的方式。原数组排列为![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]  
1、初始增量为 gap = 10/2 = 5，整个数组分成了 5 组：【50，84】，【70，83】，【60，88】，【80，87】，【61，99】，然后将相对较小的元素调到前面  
此时原数组排序变为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 3]

2、缩小增量 gap = 5/2 = 2，整个数组分成了 2 组：【50，60，61，83，87】，【70，80，84，88，99】，对这分开的 2 组分别进行插入排序(本博文提到的第一种排序法)，，此时整个数组的有序性是很明显的。由于蓝和灰两组序列都是按升序排序的，所以无变化：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 4]

3、再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组：【50，70，60，80，61，84，83，88，87，99】对这一组进行插入排序。完成操作

## 实例代码 ##

/* 希尔排序：升序 */
    #include<iostream>
    #include<windows.h>
    using namespace std;
    void print(int a[], int n)
    {   
        for(int j= 0; j<n; j++)
     {   
               cout<<a[j] <<" ";  
            }  
        cout<<endl;  
    }
    void shellSort(int array[], int n)  //a -- 待排序的数组, n -- 数组的长度
    {   
     int temp;
     for (int gap = n / 2; gap > 0; gap /= 2) { // gap为步长，每次减为原来的一半。控制几次分组，这里是3次分组，为5，2，1
      for (int i = gap; i < n; i++) { // 共gap个组，对每一组都执行直接插入排序.分5组时，该循环执行5次，
       for (int j = i; j >= gap; j -= gap) { 
        if (array[j - gap] > array[j]) { 
         temp = array[j - gap];
         array[j - gap] = array[j];
         array[j] = temp;
        }
       }
      }
     }
    }  
    int main()
    {  
     SetConsoleOutputCP(65001);
        int a[10] = { 84,83,88,87,61,50,70,60,80,99};  
        cout<<"初始序列：";  
        print(a,10);  
        shellSort(a,10);  
        cout<<"排序结果：";  
        print(a,10);  
        system("pause"); 
    }

输出：  
第一次分组：增量变量gap=5,  
![在这里插入图片描述][20190820195211228.PNG]  
解释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 7]

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

## 适用场景 ##

Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀–快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

# 冒泡排序法（稳定） #

## 简介 ##

（一）概念：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。  
（二）算法描述：

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *  针对所有的元素重复以上的步骤，除了最后一个；
 *  重复步骤1~3，直到排序完成。

（三）动图演示：  
![在这里插入图片描述][20190821080751629.gif]

## 实例代码 ##

#include <iostream>
    #include <windows.h>
    using namespace std;
    template<typename T>
    //整数或浮点数皆可使用
    void bubble_sort(T arr[], int len)
    { 
        int i, j;  T temp;
        for (i = 0; i < len - 1; i++)//len个数，排序len-1次，又因为下标从0开始，故用"<" 
            for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            { 
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
    }
    int main()
    { 
     //SetConsoleOutputCP(65001);
     printf("整数排序：\n");
        int arr[] = {  61, 17, 29, 22, 34};
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
        cout << endl;
     printf("浮点数排序：\n");
        float arrf[] = {  17.5, 19.1, 0.6, 1.9, 10.5};
        len = (int) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
            cout << arrf[i] << ' ';
     
        return 0;
    }

输出：  
![在这里插入图片描述][20190821084434721.PNG]  
解释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 9]

## 适用场景 ##

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

# 快速排序法(对冒泡排序的一种改进)（不稳定） #

## 简介 ##

（一）概念：

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序是不稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

（二）算法描述：

*  先从数列中取出一个数作为基准数。
 *  分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 *  再对左右区间重复第二步，直到各区间只有一个数。

（三）动图演示：  
![在这里插入图片描述][2019082111413186.gif]  
步骤：  
1、先将数组中的第一个元素作为基准数，在程序中声明一个变量保存起来，此时在a\[0\]上挖了个坑(可随意覆盖)，然后再将数组的初始下标和结束下标赋值给变量i和j  
2、进入分区过程，从j开始从后向前移动下标，直到遇到比基准数小的或相等的(假设j1)，然后将这个下标元素赋值a\[0\]，此时a\[j1\]为一个坑，再从i开始从前往后移动，直到遇到比基准数大的或相等的(假设i1)，然后将a\[i1\]赋值给a\[j1\]，此时a\[i1\]为一个坑，  
3、再重复上面的步骤，先从后向前找，再从前向后找。最后将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

## 实例代码 ##

参考博文：https://blog.csdn.net/morewindows/article/details/6684558，作者用白话等非专业术语将快速排序法的两个步骤（挖坑填数+分治法）讲的通俗易懂

//快速排序法
    #include <iostream>
    #include <windows.h>
    using namespace std;
    void Print(int a[],int n)
    {   
        for(int j= 0; j<n; j++)
     {   
               cout<<a[j] <<" ";  
            }  
        cout<<endl;  
    }
    int Exchange(int arr[], int low, int high){ //2、填坑法
     int pivot = arr[low];     //基准
     while (low < high){ 
      while (low < high && arr[high] >= pivot) { //从右向左扫描 ,选择比基准值小的，赋值左边，否则进入循环，下标左移 
      --high;
      } 
      arr[low]=arr[high];             //交换比基准小的记录到左端
      while (low < high && arr[low] <= pivot) { //从左向右扫描 ，选择比基准值大的，赋值右边，否则进入循环，下标右移 
      ++low;
      } 
      arr[high] = arr[low];           //交换比基准大的记录到右端
     }
     //扫描完成，基准到位
     arr[low] = pivot;
     //返回的是基准的位置
     return low;
    }
    void QuickSort(int arr[], int low, int high){ //1、分治法
      if (low >= high){ //递归跳出条件 
       return;
      }
      int pivot = Exchange(arr, low, high);        //将数组分为两部分 
      QuickSort(arr, low, pivot-1);                   //递归排序左子数组
      QuickSort(arr, pivot+1, high);                  //递归排序右子数组
    }
    int main(){ 
     int array[] = { 57, 68, 59, 52, 72, 28, 96, 33, 24,12}; 
     int n=sizeof(array)/sizeof(array[0]);
     QuickSort(array,0,n-1);
     Print(array,n);
     return 0;
    }

解释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 10]

## 使用场景 ##

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。

# 选择排序法（冒泡排序法的改进）（不稳定） #

## 简介 ##

（一）概念：选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。  
（二）算法描述：

*  初始状态：无序区为r\[0\]~r\[n-1\]的n个元素，有序区为空。
 *  第一趟排序：从无序区r\[0\]~r\[n-1\]中筛选出值最小的元素r\[k\]，将它与无序区的第一个元素r\[0\]交换，使r\[0\] ~r\[0\]和r\[1\] ~r\[n-1\]分别变成为元素个数增加1个的新有序区和元素个数减少1个的新无序区。
    
    。。。
 *  第i趟排序：第i趟排序开始时，当前有序区和无序区分别为r\[0\] ~r\[i-2\]和r\[i-1\] ~r\[n-1\]。该趟排序从当前无序区中选出关键字最小的元素r\[k\]，将它与无序区的第一个元素交换，使r\[0\] ~r\[i-1\]和r\[i\] ~r\[n-1\]分别变为元素个数增加1的新有序区和记录个数减少1个的新无序区。

n个元素需要经过n-1趟筛选选出最小元素，并进行交换。实际上，就是每次从无序区中筛选出最小的元素，并与无序区中的第一个元素交换。

（三）动图演示：  
![在这里插入图片描述][20190822162812895.gif]

### 简单选择排序 ###

#### 实例代码 ####

#include <iostream>
    using namespace std;
    void print(int a[], int n )
    {   
     for(int j= 0; j<n; j++)
          {   
      cout<<a[j] <<" ";  
     }  
     cout<<endl;  
    }  
    void select_sort(int*a,int n)
    { 
        register int i,j,min,temp;//i,j为循环控制变量，min存放最小值下标，temp为数组元素交换的中间变量，寄存器变量:直接CPU读写，使用时不需要访问内存
        for(i=0;i<n-1;i++)
        { 
            min=i;//查找最小值
            for(j=i+1;j<n;j++)
                if(a[min]>a[j])
       { 
                    min=j;
       }
            if(min!=i)//若从j循环遍历没有比a[i]更小的了，即min=i，不变，则不执行交换。 
            { 
                temp=a[min];
                a[min]=a[i];
                a[i]=temp;
                print(a,15); 
            }
        }
    }
    int main(){   
     int a[15] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};  
     select_sort(a,15);  
     print(a,15);  
     return 0;
    }

解释：  
在函数select\_sort中  
原数组→\[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\]

当i=0时，j的取值为\[1,14\]，假设0是第一次排序的最小值下标，j从\[1,14\]遍历元素与a\[0\]判断，判断到a\[9\]=2<a\[0\]=3,最小值下标min=9，后面循环到j=14没有比a\[9\]更小的了，min不变,然后a\[9\]与a\[0\]互换。  
→\[2 44 38 5 47 15 36 26 27 3 46 4 19 50 48\]

当i=1时，j的取值为\[2,14\]，假设1是第二次排序的最小下标，j从\[2,14\]遍历元素与a\[1\]判断比较，判断到a\[2\]=38<a\[1\]=44，最小值下标min=2，判断到a\[3\]=5<a\[min\]=38，最小值下标min=3，接着判断到a\[9\]=3<a\[3\]=5，最小值下标min=9，后面循环到j=14没有比a\[9\]更小的了,min不变，然后a\[9\]与a\[1\]互换。  
→\[2 3 38 5 47 15 36 26 27 44 46 4 19 50 48\]

当i=2时，j的取值为\[3,14\]，假设2是第三次排序的最小下标，j从\[3,14\]遍历元素与a\[2\]判断比较，判断到a\[3\]=5<a\[2\]=38，最小值下标min=3，接着再判断到a\[11\]=4<a\[3\]=5，最小值下标min修改为11，后面循环到j=14没有比a\[11\]更小的了，min=11不变，然后a\[11\]与a\[2\]互换。  
→\[2 3 4 5 47 15 36 26 27 44 46 38 19 50 48\]

当i=3时，j的取值为\[4,14\]，假设3是第四次排序的最小下标，j从\[4,14\]遍历元素和a\[3\]判断比较，发现没有比a\[3\]更小的了，数组排序不变，所以直接i=4。  
→\[2 3 4 5 47 15 36 26 27 44 46 38 19 50 48\]

当i=4时，j的取值为\[5,14\]，假设4是第五次排序的最小下标，j从\[5,14\]遍历元素和a\[4\]判断比较，判断到a\[5\]=15<a\[4\]=47，最小值下标min=5，后面循环到j=14没有比a\[5\]更小的了，min不变，然后a\[5\]与a\[4\]互换。  
→\[2 3 4 5 15 47 36 26 27 44 46 38 19 50 48\]

当i=5时，j的取值为\[6,14\]，假设5是第六次排序的最小下标，j从\[6,14\]开始遍历元素和a\[5\]比较，判断到a\[6\]=36<a\[5\]=47，最小值下标变为6,接着再判断到a\[7\]=26<a\[6\]=36，最小下标min修改为7，再判断到a\[12\]=19<a\[7\]=26，最小值下标min变为12，接着a\[12\]与a\[5\]互换。  
→\[2 3 4 5 15 19 36 26 27 44 46 38 47 50 48\]

当i=6时，j的取值为\[7,14\]，假设6是第七次排序的最小下标，j从\[7,14\]开始遍历元素和a\[6\]判断比较，a\[7\]=26<a\[6\]=36,min=7，此时a\[min\]=26，此后循环到j=14没有比a\[7\]更小的了，min不变，然后a\[7\]与a\[6\]互换。  
→\[2 3 4 5 15 19 26 36 27 44 46 38 47 50 48\]

当i=7时，最小值下标min初始化为7，j从\[8,14\]遍历比较元素判断比较，判断到a\[8\]=27<a\[7\]=36，最小值下标min变为8，此时a\[min\]=27，此后j循环到14没有比a\[8\]更小的了，a\[7\]与a\[8\]互换。  
→\[2 3 4 5 15 19 26 27 36 44 46 38 47 50 48\]

当i=8时，最小值下标min初始化为8，j从\[9,14\]判断没有比a\[min\]=36更小的了，数组排序不变。  
→\[2 3 4 5 15 19 26 27 36 44 46 38 47 50 48\]

当i=9时，最小值下标min初始化为9，j从\[10,14\]遍历比较元素判断比较，判断到a\[11\]=38<a\[9\]=44，最小值下标min=11，此后没有比a\[11\]还小的了，min不变，然后a\[11\]与a\[9\]互换。  
→\[2 3 4 5 15 19 26 27 36 38 46 44 47 50 48\]

当i=10时，最小值下标min初始化为10，j从\[11,14\]遍历比较元素判断比较，判断到a\[11\]=44<a\[10\]=46，最小值下标min=11，此后没有比a\[11\]更小的了,min不变，然后a\[11\]与a\[10\]互换。  
→\[2 3 4 5 15 19 26 27 36 38 44 46 47 50 48\]

当i=11时，数组排序不变。

当i=12时，数组排序不变。

当i=13时，j只能取14，a\[14\]=48<a\[13\]=50，min=14,然后a\[14\]与a\[13\]互换。  
→\[2 3 4 5 15 19 26 27 36 38 44 46 47 48 50\]

**精简版选择排序**

#include <stdio.h>
    void SelectSort(int a[],int n); 
    const int N=6;
    int main(void)
    { 
     int a[N],i;//定义有N个元素的数组a
     printf("请输入%d个整数（数与数之间用空格隔开）：\n",N);
     for(i=0;i<N;i++)
     { 
      scanf("%d",&a[i]);
     } 
     SelectSort(a,N);
     printf("排序后的结果为：\n");
     for(i=0;i<N;i++)
     { 
      printf("%-2d",a[i]);
     }
     printf("\n");
     return 0;
    } 
    void SelectSort(int a[],int n)
    { 
     for(int i=0;i<=n-1;i++)//依次确定需要交换的位置a[0],a[1]....a[4] 
     { 
      for(int j=i+1;j<n;j++)//每个位置需要比较的数，a[0]与a[1],a[2],a[3],a[4],a[5]比较 
      { 
       if(a[i]>a[j])
       { 
        int t;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
       }
      }
     }
    }

## 树形选择排序（暂不讨论） ##

### 堆排序（暂不讨论） ###

## 使用场景 ##

选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n^2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。

# 归并排序法（稳定） #

## 简介 ##

（一）概念：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序比较占用内存，但却是一种效率高且稳定的算法。即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。

（二）算法描述：  
**两种方法：**  
递归法（Top-down）

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 *  重复步骤3直到某一指针到达序列尾
 *  将另一序列剩下的所有元素直接复制到合并序列尾

迭代法（Bottom-up）

原理如下（假设序列共有n个元素）：  
将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素  
若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素  
重复步骤2，直到所有元素排序完毕，即序列数为1

（三）动图演示：  
![在这里插入图片描述][20190823091628314.gif]  
假设有数组【3，44，38，5，47，15，36，26，27，2，46，4，19，50，48】

*  第一次归并后：【3，44】，【38，5】，【47，15】，【36，26】，【27，2】，【46，4】，【19，50】，【48】
 *  第二次归并后：【3，5，38，44】，【15，26，36，47】，【2，4，27，46】，【19，48，50】
 *  第三次归并后：【3，5，15，26，36，38，44，47】，【2，4，19，27，46，48，50】
 *  第四次归并后：【2，3，4，5，15，19，26，27，36，38，44，46，47，48，50】

## 分类 ##

### 递归法 ###

### 循环法 ###

## 使用场景 ##

归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

[20190820144733163.gif]: /images/20211029/4630939ad21e46028c3fd7656002473e.png
[20190820153049180.PNG]: /images/20211029/5949597fac58468286ed12e2977949ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]: /images/20211029/46e60850574d4b5bbf1fbf3a5a09c8b5.png
[20190819152636617.PNG]: /images/20211029/b8365cfc89e045bdb64e5fad977cad1a.png
[20190819153006939.PNG]: /images/20211029/bd9abb6966364eefb162407cb6c78ba9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]: /images/20211029/9ae071e85f5342ec8b7e6cfd5df82ebe.png
[20190819171759290.PNG]: /images/20211029/342711dc550f4636979a33a1169216cf.png
[20190820093336847.PNG]: /images/20211029/70258ed307114a5e87bcc9a860b509fe.png
[20190820093352629.PNG]: /images/20211029/6a620107dc234cbe8b8b9dcb9b91fb2c.png
[20190820163023369.gif]: /images/20211029/257eb3e060da44b3aad6d4287656f1f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]: /images/20211029/4ea3323ebbb949dfadc73860d4ed8c7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 3]: /images/20211029/ed42170547a54e0ead6bf66e99de38e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 4]: /images/20211029/13cfcaab98394dd18f1b967b34d987e7.png
[20190820195211228.PNG]: /images/20211029/c0b7fded7c994803839a29043dbc59c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 5]: /images/20211029/85cd76b015e443f48b27a4e95dfe5d9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 6]: /images/20211029/64a313c9068c4e0fb7aab2330bf56cf0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 7]: /images/20211029/9e6acca46c9847219fb13e097c980694.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 8]: /images/20211029/405b46b2eb0c4bdc86bfccf39ef2cdda.png
[20190821080751629.gif]: /images/20211029/c1303ece72354c60b3ca1fbb19d6f285.png
[20190821084434721.PNG]: /images/20211029/28974281e4a649e4b03f9fc8f9e4f006.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 9]: /images/20211029/3b0f9879efe846d5b5cda5132e0e918a.png
[2019082111413186.gif]: /images/20211029/d96b9ea3a6864657a181081636e79d41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 10]: /images/20211029/1aabbf04c44c4b199783e90a4375a831.png
[20190822162812895.gif]: /images/20211029/1da4db0e4ede49d291103738fdef6e07.png
[20190823091628314.gif]: /images/20211029/150c0d8cb6ce4b269013652dc2b4d744.png