对冒泡、直接插入、快速排序、归并四种排序方式的总结，及对二分法查找的注意事项的一些说明

每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
通知：目前比赛栏的权限已经完全开放，支持老师、个人随时抽题创建比赛，需达到P2等级
比赛名称建议包含学校/组织名称，具有辨识度。不友好名称可能会被屏蔽，请大家知晓！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
比赛创建功能已经完全开放，需要达到P2等级，写博客要达到P2等级
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

行之

用户名：jark

访问量：109

签　名：

等　　级
排　　名	2280
经　　验	880
参赛次数	0
文章发表	4
年　　龄	0
在职情况
学　　校	成都信息工程大学
专　　业

　　自我简介：

TA的其他文章

2017题-10.猜价模拟-题解(C++描述)
浏览：16

对冒泡、直接插入、快速排序、归并四种排序方式的总结，及对二分法查找的注意事项的一些说明
浏览：56

2024题-17.链表删除练习-题解(C++描述)
浏览：2

你可能喜欢

题解1007：C语言程序设计教程（第三版）课后习题5.5 （Java描述）
浏览：756

题解1007：C语言程序设计教程（第三版）课后习题5.5 （C语言描述）
浏览：481

题解1088：A+B for Input-Output Practice (IV) （C语言描述）
浏览：324

题解1030：C语言程序设计教程（第三版）课后习题8.4 （C语言描述）
浏览：425

题解1431：分糖果（C语言描述）
浏览：693

对冒泡、直接插入、快速排序、归并四种排序方式的总结，及对二分法查找的注意事项的一些说明

　　作者: 行之　　　　发表时间：2019-11-19 22:49:31 浏览：56　|　评论：0　

以下所有程序的运行环境均为Code::Block，代码在不同编译器下运行，结果可能会有有所不同
如，以下定义变量的位置并非全在程序开头，在VC上，可能会报错。改正方法：将程序里定义变量的语句放在程序的开头即可。
************************************************************************************************************************************************************************************************
话不多说，直接进入正题：
一）：直接插入排序（插入排序有多种类型，这次讲平时应用最多的）
代码实现如下：（以正序输出为例，倒序输出，仅需对代码进行适当修改即可）
```cpp
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
 
int a[100055];
 
int main()
{
    int n,i;
    cin>>n;
 
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
 
    int head;
    head = 2;
    while(head<=n)
    {
        i = head;
        while(i>=2&&a[i]<a[i-1])
        {
            if(a[i]<a[i-1])//判断是否进行交换
            {
                swap(a[i] ,a[i-1]);//调用swap函数
                i--;
            }
        }
        head++;//起索引作用，是循环的范围加1
    }
 
    for(i=1;i<=n;i++)
    {
        cout<<a[i];
    }
    return 0;
}
```
上述代码的运行结果为：![](/image_editor_upload/20191119100854_56599.png)
上述代码实际上就是，**每次while循环依次比较a[2]与a[1]  ;  a[3]与a[2] 、a[2]与a[1] ; a[4]与a[3]、a[3]与a[2]、a[2]与a[1] ; ………大小，直到遍历完数组所有的元素，也就完成了排序。首先，我们来理一下上述代码的思想，上述代码实际上就是，每次while循环依次比较a[2]与a[1]  ;  a[3]与a[2] 、a[2]与a[1] ; a[4]与a[3]、a[3]与a[2]、a[2]与a[1] ; ………大小，直到遍历完数组所有的元素，也就完成了排序。**
我们可以把上述代码总结成一种模型，即，**上述代码可以对任意一组数据的任意一段连续数据进行排序（仅需改变上述代码的初始化条件以及循环结束条件即可实现）**，而这一思想的典型应用就是 “**滚动的榜单**”问题。
当然，上述代码也可以用for循环实现，但个人认为，用while循环，更能体现其思想本质，尤其是通过变量head，体现比较范围的变换。且在实际应用时，个人感觉，用while循环实现更加方便。

**二）：冒泡排序**
代码如下（以正序输出为例）
```cpp
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
 
int a[55];
 
int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
 
    int head = 1;
    while(head<=n)
    {
        for(i=head+1;i<=n;i++)
        {
            if(a[i]<a[head])
            {
                swap(a[i] ,a[head]);
            }
        }
        head++;
    }
 
    for(i=1;i<=n;i++)
    {
        cout<<a[i];
    }
    return 0;
}
```
上述代码的运行结果为：
![](/image_editor_upload/20191119102218_13546.png)
上述代码的思想是：**首先，用数组的第一个元素与剩下的元素比较，并将最小的元素调到第一位；然后，用数组的第二个元素与剩下的元素比较，并将最小的元素调到第二位；以此类推，当head等于n时，就完成了排序。**
上述算法，对于不搞竞赛的同学来说，应该是最常用的排序方法了。
上述代码同样可以用for循环实现。

**三）：快速排序**
具体代码如下（以升序形式输出）
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
 
void quicksort(int l ,int r);
 
int a[100055];
 
int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
 
    quicksort(1 ,n);
 
    for(i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
 
    cout<<endl;
    return 0;
}
 
void quicksort(int l  ,int r)
{
    int i,j,m,mid;
    i = l;
    j = r;<br>　　 mid = (l+r)/2;
    m = a[mid];//将数组分成两部分
    while(i<=j)
    {
/***********************************************/
//注意，这里while里面的判断条件为什么不带上 “=” ？
/*是为了防止当出现数组中出现一段相等的数字是，该循环变为死循环。如下面举出的例子。*/
        while(a[i]<m)
            i++;
        while(a[j]>m)
            j--;
/***********************************************/
        if(i<=j)
        {
            swap(a[i] ,a[j]);
            i++;
            j--;
        }
    }
    if(j-l>=1)//停止调用函数本身的判断条件
        quicksort(l ,j);//通过调用函数自身，对分开的两部分，分别
                        //进行排序                    
//同时，由于i,j经过while循环，均越过了中值mid,故，新范围是（l,j)
//下面的（i，r）同理。
    if(r-i>=1)//停止调用函数本身的判断条件
        quicksort(i ,r);
//通过调用函数自身，对分开的两部分，分别进行排序
}
```
上述代码运行结果为：
![](/image_editor_upload/20191119102715_46037.png)

但当将while循环中的判断条件带上等号是，就会出现漏洞，可能使程序变为死循环，如：
![](/image_editor_upload/20191119103035_41408.png)
上述代码实际上体现了二分的思想：**首先随机在数组中选一个数，将一个数组分成随机分成两部分（这里我就用区间的中间位置对应的值，实际上，可以用rand函数随机生成一个位置，这样其实更加合理），分别在左，右取大于或等于、小于或等于a[mid]的数，进行交换，直到i,j越过mid值时，一次循环结束。这样不断地进行循环，最终即可以实现排序。**
快速排序的精髓就在于灵活应用二分的思想，这也正是其运行效率高的原因之一。

**四）：归并排序**
代码如下：（以升序为例）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 100055
void mergesort(int l, int r);
int a[N];
int larray[N],rarray[N],rn,ln,lposition,rposition;
//larray[N],rarray[N]用于存储拆分得到的两个数组;
//ln ,rn 用于记录被分成的左右数组分别包含的元素的个数
//lposition ,rposition 用于记录数组的下表所在的位置
int main()
{
 　　int n,i;
 　　cin>>n;
 　　for(i=1;i<=n;i++)
   　　  cin>>a[i];
 　　mergesort(1,n);
 　　for(i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
       cout<<endl;
       return 0;
}
void mergesort(int l,int r)
{
 　　int i;
　　 int mid=(l+r)/2;
        //将数组分为两部分

if(l<mid)
　　　　mergesort(l,mid);//反复调用函数本身，实现排序
　　 if(mid+1<r)
　　　　mergesort(mid+1,r);//反复调用函数本身，实现排序
 
　　 ln=rn=0;
 　　for(i=l;i<=mid;i++)
　　       larray[++ln]=a[i];
　　 for(i=mid+1;i<=r;i++)
  　　     rarray[++rn]=a[i];
 
　　 lposition=rposition=1;
         for(i=l;i<=r;i++)
        {
//******************************************************************************/
/*这部分用于解决数组中最后一个元素归属问题（因为对于数组的追后一个元素，已经没有其他元素来和他进行大小比较了，那么，也就不能利用下面的语句，通过比较两个数组大小为其中的元素分配位置。这时，*/
/*必须单独设计语句，为最后的一个元素分配位置，也就有了下面的这两个语句)*/
            if(lposition>ln)
            　　a[i]=rarray[rposition++];
/*lposition>ln的意思是，当前数组下标的位置已经超出了数组的有效长度，下同。*/
  　　   else if(rposition>rn)
          　　  a[i]=larray[lposition++];
//*****************************************************************************/
  　　　else if(larray[lposition]<=rarray[rposition])
/*这两句是为数组中的元素分配位置，分配原则是数值小的先分配位置，下同。*/
            　　 a[i]=larray[lposition++];
 　　　 else
   　　　　　a[i]=rarray[rposition++];
　　　 }
}
```
上述代码运行结果为：
![](/image_editor_upload/20191119103643_92232.png)
上述代码的核心思想是：**先将数组利用二分思想多次进行二等分，然后在从得到的各个小份数组出发，两两遵循在合并的同时按从小到大排序，最终，即可实现排序。**
由于图片超限，无法展示，具体图片如下：（下图摘自百度百科 ，链接：https://baike.baidu.com/pic/归并排序/1639015/0/c8177f3e6709c93d673b9ed49d3df8dcd00054c3
fr=lemma&ct=single#aid=0&pic=c8177f3e6709c93d673b9ed49d3df8dcd00054c3）

归并排序在上述几种排序方式中应该是最复杂的排序方式了，但其高效的运行效率，以及其包含的重要思想使得作为一个合格的程序员，或者是搞算法竞赛的同学必须掌握。
到目前为止，个人感觉，对上述归并排序算法的思想的应用最到位的当属经典的  “ **逆序数的对数**”  问题。

**五）二分法查找**
除了介绍上述四种常用的排序方法外，我还想补充一下关于二分法查找的一下东西。（将一个数加入到一组数里面后，找出其在这组数里的位置）
先看代码实现：（以正序输入为例）
```cpp
#include<iostream>
using namespace std;
const int maxint = 1000000000;
int main()
{
    int a[100055];
    int n,m;
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[0] = -maxint;
    a[n+1] = maxint;
/*这个语句的作用就是为了防止因输入的数大于已知数据的最大值而造成程序不稳定*/
    int l,r,mid,mark;
    l = 0,r=n+1;
    while(l<=r)
    {
        mid = (l+r)/2;
        if(a[mid]>=m)
        {
            mark = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    cout<<mark<<endl;
    return 0;
}
```
以上代码运行结果为：
![](/image_editor_upload/20191119104158_73103.png)

若没有上述语句，会：
![](/image_editor_upload/20191119104326_81338.png)
结果是乱码！！！

所以，**我们在设计二分法的时候，一定要考虑当输入的值大于已知的最大值这种情况，**当然，解决这个问题的方法不止上面一种，就不一一罗列了。
 
希望以上内容能对各位有所帮助！！！
************************************************************************************************************************************************************************************************************************* 
再强调一次，以上代码均为     通过各种途径学习+自己的理解      所得，如若侵权，请告知，核实之后，必立即删除！！！
同时本人为大一菜鸟，上面的样例均为自主设置的，如若有误，还请告知，必立即改正。
本人写此文章主要目的是对知识点整理，但限于个人水平，如上述表述内容有些许错误，或不到位的地方，请各位大佬告知，在下必立刻更改！！！
欢迎大佬们评论，留言。
最后，码字不易，要是感觉还行的话，求求大佬们点个赞吧。

0.0分

2 人评分