十大排序算法第一弹：冒泡排序

自从上一篇简书发布到现在，差不多也有两个月了。小编原本五一假期打算整理下有关排序的一些算法，没成想放假第一天就因为骑着的电动车出了故障导致人摔飞了出去，在家养了几天的伤这事也就给搁置了。最近忙于工作累了就睡便也彻底忘了这事。难得赋闲，利用周末的时间，小编便整理了十大排序算法中的“冒泡排序”，与小伙伴们分享一下。

一、算法思想

冒泡排序的英语名是Bubble Sort，是一种最基础的交换排序。可以从大到小，也可以从小到大。
交换排序顾名思义就是通过元素的两两比较，判断是否符合要求，如过不符合就交换位置来达到排序的目的。冒泡排序名字的由来就是因为在交换过程中，类似水冒泡，小（大）的元素经过不断的交换由水底慢慢的浮到水的顶端【根据自身大小，一点一点向着数组的一侧移动】。
冒泡排序的思想就是利用的比较交换，利用循环将第 i 小或者大的元素归位，归位操作利用的是对 n 个元素中相邻的两个进行比较，如果顺序正确就不交换，如果顺序错误就进行位置的交换。通过重复的循环访问数组，直到没有可以交换的元素，那么整个排序就已经完成了。

二、实例演示

我们通过一个示例来理解一下基本的冒泡排序，假设当前我们有一个数组 a，内部元素为 3，4，1，5，2，即初始状态，如下图所示。我们的目的就是通过 n 趟比较来实现由底向上从大到小的的顺序。

待排序数组

1、第一遍排序

进行第一遍排序，如下图所示，橙色圆形白色字体代表当前比较的元素，绿色代表已经归位的元素，橙色代表未排元素。
（1）比较第一个和第二个元素，3<4，交换
（2）比较第二个和第三个元素，3>1，不交换
（3）比较第三个和第四个元素，1<5，交换
（4）比较第四个和第五个元素，1<2，交换
最后，我们可以看到 1 已经位于最顶部。第一遍需要尽心四次比较才能把五个数比较完。

第一遍排序

2、第二遍排序

第二遍排序的初始状态是第一遍排序的最终状态，即4，3，5，2，1【待排序列有4个数为4、3、5、2，绿色代表不参与下一轮排序】。
（1）比较第一个和第二个元素，4>3，不交换
（2）比较第二个和第三个元素，3<5，交换
（3）比较第三个和第四个元素，3>2，不交换
第二遍排序，会让2归位，并且这一遍只用进行三次比较就可以了。

第二遍排序

3、第三遍排序

第三遍排序的初始状态是第二遍排序的最终状态，即4，5，3，2，1【待排序列有3个数为4、5、3，绿色代表不参与下一轮排序】。
（1）比较第一个和第二个元素，4<5，交换
（2）比较第二个和第三个元素，4>3，不交换
第三遍排序，会让 3 归位，并且这一遍只用进行两次比较就可以了。

第三遍排序

然而我们可以看到这一次五个数已经全部完成了归位，但是当我们采用普通的冒泡排序的时候，算法仍然会继续向下进行【下面会贴上常规的冒泡排序代码】

4、第四遍排序

第四遍排序的初始状态是第三遍排序的最终状态，即5，4，3，2，1。比较第一个和第二个元素，5>4，不交换。
第四遍排序，会让 4 归位，并且这一遍只用进行一次比较就可以了。

第四遍排序

第四遍排序结束后，由于待排序序列中仅剩 1 个元素，无法再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列。

冒泡排序结果序列

三、代码实现

通过观察上述例子，我们可以发现整个冒泡的过程，外部循环只需要执行4次（n个待排序数外层循环n-1次），执行第i次【i>=0】外部循环的时候，内部循环需要执行n-1-i次（看上述例子进行比对）。
整个算法流程其实就是上面实例所分析的过程。可以看出，我们在进行每一次大循环的时候，还要进行一个小循环来遍历相邻元素并交换。所以我们的代码中首先要有两层循环。
1、外层循环：即主循环，需要辅助我们找到当前第 i 小的元素来让它归位。所以我们会一直遍历 n-1 次，这样可以保证前 n-1 个元素都在正确的位置上，那么最后一个也可以落在正确的位置上了。
2、内层循环：即副循环，需要辅助我们进行相邻元素之间的比较和换位，把大的或者小的浮到水面上。所以我们会一直遍历 n-1-i 次这样可以保证没有归位的尽量归位，而归位的就不用再比较了。
代码如下所示：

#include<iostream>
using namespace std;
void BubbleSort1(int arr[], int n);//从大到小的冒泡排序
void BubbleSort2(int arr[], int n);//从小到大的冒泡排序
void printArray(int arr[], int n);//输出结果 
int main()
{
    int n;//待排序数的个数
    int m;//用于做排序选择 
    int *p;
    cout<<"输入待排序数的个数:";
    cin>>n;
    p=new int[n];
    cout<<"请输入待排序的数字："<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<"选1进行由大到小的冒泡排序，选2进行由小到大的冒泡排序：";
    cin>>m;
    if(m==1)
        BubbleSort1(p,n);
    else if(m==2)
        BubbleSort2(p,n);
    else
        cout<<"选择出错！"<<endl;
    
    return 0;
}
void BubbleSort1(int arr[], int n)
{ 
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
        for(int j = 0; j < n-1-i; j++)
        {
            // 比较相邻的元素，如果前面的数小于后面的数，就交换
            if(arr[j] < arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
    }
}

//从小到大的冒泡排序
void BubbleSort2(int arr[], int n)
{
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i大的数放在第i个位置上
        for(int j = 0; j < n-1-i; j++)
        {
            // 比较相邻的元素，如果前面的数大于后面的数，就交换
            if(arr[j] > arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
    }
}
 
void printArray(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

常规代码运行截图：

常规代码运行截图

四、代码优化

1、优化一：设置标志位

经过了上述的讨论和编码，常规的冒泡排序已经被我们实现了。那么接下来我们要讨论的就是刚刚分析时候提出的问题。
首先针对第一个问题，当我们进行完第三遍的时候，实际上整个排序都已经完成了，但是常规版还是会继续排序。
可能在上面这个示例下，可能看不出来效果，但是当数组是【5，4，3，1，2】的时候的时候就非常明显了，实际上在第一次循环的时候整个数组就已经完成排序，但是常规版的算法仍然会继续后面的流程，这就是多余的了。

多余排序

所以我们可以在交换的地方加一个标记flag，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。
代码如下：

#include<iostream>
using namespace std;
void BubbleSort1(int arr[], int n);//从大到小的冒泡排序
void BubbleSort2(int arr[], int n);//从小到大的冒泡排序
void printArray(int arr[], int n);//输出结果 
int main()
{
    int n;//待排序数的个数
    int m;//用于做排序选择 
    int *p;
    cout<<"输入待排序数的个数:";
    cin>>n;
    p=new int[n];
    cout<<"请输入待排序的数字："<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<"选1进行由大到小的冒泡排序，选2进行由小到大的冒泡排序：";
    cin>>m;
    if(m==1)
        BubbleSort1(p,n);
    else if(m==2)
        BubbleSort2(p,n);
    else
        cout<<"选择出错！"<<endl;
    
    return 0;
}
void BubbleSort1(int arr[], int n)
{ 
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int flag = 0;
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        flag = 0;
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
        for(int j = 0; j < n-1-i; j++)
        {
            // 比较相邻的元素，如果前面的数小于后面的数，就交换
            if(arr[j] < arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = 1;//加入标记
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
        if (flag == 0)//如果没有交换过元素，则已经有序，提前结束
        {
            return;
        }
    }
}

//从小到大的冒泡排序
void BubbleSort2(int arr[], int n)
{
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int flag = 0;
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        flag = 0;
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i大的数放在第i个位置上
        for(int j = 0; j < n-1-i; j++)
        {
            // 比较相邻的元素，如果前面的数大于后面的数，就交换
            if(arr[j] > arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = 1;//加入标记
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
        if (flag == 0)//如果没有交换过元素，则已经有序
        {
            return;
        }
    }
}
 
void printArray(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

优化一运行截图

2、优化二：设置结束边界

除了上面这个问题，在冒泡排序中还有一个问题存在，就是第 i 趟排的第 i 小或者大的元素已经在第 i 位上了，甚至可能第 i-1 位也已经归位了，那么在内层循环的时候，有这种情况出现就会导致多余的比较出现。
例如：【6，4，7，5，1，3，2】，当我们进行第一次排序的时候，结果为【6，7，5，4，3，2，1】。实际上后面有很多次交换比较都是多余的，因为没有产生交换操作。看下图小伙伴就知道了【有很多次的交换是没必要的】：

优化一算法存在问题

可以看出，第三趟的多次比较实际上可以没有，因为中间几个位置在第二趟就没有过交换。
针对上述的问题，我们可以想到，利用一个标志位pos，记录一下当前第 i 趟所交换的最后一个位置的下标，在进行第 i+1 趟的时候，只需要内循环到这个下标的位置就可以了，因为后面位置上的元素在上一趟中没有换位，这一次也不可能会换位置了。基于这个原因，我们可以进一步优化我们的代码。
代码如下：

#include<iostream>
using namespace std;
void BubbleSort1(int arr[], int n);//从大到小的冒泡排序
void BubbleSort2(int arr[], int n);//从小到大的冒泡排序
void printArray(int arr[], int n);//输出结果 
int main()
{
    int n;//待排序数的个数
    int m;//用于做排序选择 
    int *p;
    cout<<"输入待排序数的个数:";
    cin>>n;
    p=new int[n];
    cout<<"请输入待排序的数字："<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<"选1进行由大到小的冒泡排序，选2进行由小到大的冒泡排序：";
    cin>>m;
    if(m==1)
        BubbleSort1(p,n);
    else if(m==2)
        BubbleSort2(p,n);
    else
        cout<<"选择出错！"<<endl;
    
    return 0;
}
void BubbleSort1(int arr[], int n)
{ 
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int flag = 0;
    int pos = 0;//用来记录最后一次交换的位置
    int k = n - 1;
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        pos=0; 
        flag = 0;
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
        for(int j = 0; j < k; j++)
        {
            // 比较相邻的元素，如果前面的数小于后面的数，就交换
            if(arr[j] < arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = 1;//加入标记
                pos = j;//交换元素，记录最后一次交换的位置
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
        if (flag == 0)//如果没有交换过元素，则已经有序
        {
            return;
        }
        k = pos;//下一次比较到记录位置即可
    }
}

//从小到大的冒泡排序
void BubbleSort2(int arr[], int n)
{
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int flag = 0;
    int pos = 0;//用来记录最后一次交换的位置
    int k = n - 1;
    // 要遍历的次数
    for(int i = 0; i < n-1; i++)
    {
        flag = 0;
        pos=0;
        printf("--第%d遍交换:\n",i+1);
        //依次的比较相邻两个数的大小，遍历一次后，把数组中第i大的数放在第i个位置上
        for(int j = 0; j < k; j++)
        {
            // 比较相邻的元素，如果前面的数大于后面的数，就交换
            if(arr[j] > arr[j+1])
            {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = 1;//加入标记
                pos = j;//交换元素，记录最后一次交换的位置
            }
            printf("----第%d遍的第%d次交换:",i+1,j+1);
            printArray(arr,n);
        }
        printf("----第%d遍最终结果:",i+1);
        printArray(arr,n);
        if (flag == 0)//如果没有交换过元素，则已经有序
        {
            return;
        }
        k = pos;//下一次比较到记录位置即可
    }
}
 
void printArray(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

优化二

可以清楚的看到，部分内循环多余的比较已经被去掉了，算法得到了进一步的优化。

3、优化三：优化一 + 优化二 + 双向冒泡排序

双向冒泡排序，又叫鸡尾酒排序（Cocktail Sort）。
它的过程是：先从左往右比较一次，再从右往左比较一次，然后又从左往右比较一次，以此类推。
它是为了优化前面的大部分元素都已经排好序的数组的排序。我们来看个简单例子【5，1，3，2，4】，了解所谓的双向冒泡排序【没有结合前面两种优化，这里依然是从大到小排序】

待排序序列

（一）第一趟正向扫描
（1）比较第一个和第二个元素，5>1，不交换
（2）比较第二个和第三个元素，1<3，交换
（3）比较第三个和第四个元素，1<2，交换
（4）比较第四个和第五个元素，1<4，交换
最后，我们可以看到 1 已经位于数组最右侧。第一趟正向扫描需要尽心四次比较才能把五个数比较完。

第一趟正向扫描

（二）第一趟反向扫描
（1）比较第四个和第三个元素，4>2，交换
（2）比较第三个和第二个元素，4>3，交换
（3）比较第二个和第一个元素，4<5，不交换
第一趟反向扫描，会让5归位，并且这一趟只用进行三次比较就可以了。

第一趟反向扫描

（三）第二趟正向扫描
（1）比较第二个和第三个元素，4>3，不交换
（2）比较第三个和第四个元素，3>2，不交换
第一趟正向扫描，会让2归位，并且这一趟只用进行两次比较就可以了。

第二趟正向扫描

（四）第二趟反向扫描
比较第三个和第二个元素，3<4，不交换
第二趟反向扫描，会让4归位，并且这一趟只用进行一次比较就可以了。

第二趟反向扫描

由于待排序序列中仅剩 1 个元素，无论再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列。

最后排序结果

代码如下：

#include<iostream>
using namespace std;
void BubbleSort1(int arr[], int n);//从大到小的冒泡排序
void BubbleSort2(int arr[], int n);//从小到大的冒泡排序
void printArray(int arr[], int n);//输出结果 
int main()
{
    int n;//待排序数的个数
    int m;//用于做排序选择 
    int *p;
    cout<<"输入待排序数的个数:";
    cin>>n;
    p=new int[n];
    cout<<"请输入待排序的数字："<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<"选1进行由大到小的冒泡排序，选2进行由小到大的冒泡排序：";
    cin>>m;
    if(m==1)
        BubbleSort1(p,n);
    else if(m==2)
        BubbleSort2(p,n);
    else
        cout<<"选择出错！"<<endl;
    
    return 0;
}
void BubbleSort1(int arr[], int n)
{ 
    int left = 0;
    int right = n- 1;
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int j=1; 
    while (left < right) 
    { 
        printf("----第%d趟正向扫描:\n",j);
        for (int i = left,k=1; i < right; i++,k++) { // 保证 a[right] 是最小的
            if (arr[i] < arr[i+1]) {
                temp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = temp;
            }
            printf("--第%d趟正向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        printf("----第%d反趟向扫描:\n",j);
        right--;
        for (int i = right,k=1; i > left; i--,k++) { // 保证 a[left] 是最大的
            if (arr[i] > arr[i-1]) {
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
            }
            printf("--第%d趟反向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        left++;
        j++;
    }
    //printf("----第%d遍最终结果:",i+1);
    printArray(arr,n);
}

//从小到大的冒泡排序
void BubbleSort2(int arr[], int n)
{
    
    int left = 0;
    int right = n- 1;
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int j=1; 
    while (left < right) 
    { 
        printf("---第%d趟正向扫描:\n",j);
        for (int i = left,k=1; i < right; i++,k++) { // 保证 a[right] 是最大的
            if (arr[i] > arr[i+1]) {
                temp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = temp;
            }
            printf("------第%d趟正向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        printf("---第%d反趟向扫描:\n",j);
        right--;
        for (int i = right,k=1; i > left; i--,k++) { // 保证 a[left] 是最小的
            if (arr[i] < arr[i-1]) {
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
            }
            printf("------第%d趟反向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        left++;
        j++;
    }
    //printf("----第%d遍最终结果:",i+1);
    printArray(arr,n);
}
 
void printArray(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

运行截图：

未改良双向冒泡

接下来，我们只需要将设置标志位和记录最后一次交换位置的优化思路应用在双向冒泡上，就形成了最终的优化版本。这里小编不再做具体阐述，代码如下：

#include<iostream>
using namespace std;
void BubbleSort1(int arr[], int n);//从大到小的冒泡排序
void BubbleSort2(int arr[], int n);//从小到大的冒泡排序
void printArray(int arr[], int n);//输出结果 
int main()
{
    int n;//待排序数的个数
    int m;//用于做排序选择 
    int *p;
    cout<<"输入待排序数的个数:";
    cin>>n;
    p=new int[n];
    cout<<"请输入待排序的数字："<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<"选1进行由大到小的冒泡排序，选2进行由小到大的冒泡排序：";
    cin>>m;
    if(m==1)
        BubbleSort1(p,n);
    else if(m==2)
        BubbleSort2(p,n);
    else
        cout<<"选择出错！"<<endl;
    
    return 0;
}
void BubbleSort1(int arr[], int n)
{ 
    int left = 0;
    int right = n- 1;
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int j=1; 
    int pos=0;// 记录最后一次交换的位置
    int flag=0; // 标志位
    while (left < right) 
    { 
        printf("----第%d趟正向扫描:\n",j);
        for (int i = left,k=1; i < right; i++,k++) { // 保证 a[right] 是最小的
            if (arr[i] < arr[i+1]) {
                temp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = temp;
                flag=1;
                pos=i;
            }
            printf("--第%d趟正向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        right = pos;  // 将最后一次交换的位置作为右边界
        if (flag==0) { // 上一轮没有交换，提前结束
            break;
        }
        flag=0;
        printf("----第%d反趟向扫描:\n",j);
        for (int i = right,k=1; i > left; i--,k++) { // 保证 a[left] 是最大的
            if (arr[i] > arr[i-1]) {
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
                flag=1;
                pos=i;
            }
            printf("--第%d趟反向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        left = pos;  // 将最后一次交换的位置作为右边界
        if (flag==0) { // 上一轮没有交换，提前结束
            break;
        }
        flag=0;
        j++;
    }
    //printf("----第%d遍最终结果:",i+1);
    printArray(arr,n);
}

//从小到大的冒泡排序
void BubbleSort2(int arr[], int n)
{
    
    int left = 0;
    int right = n- 1;
    int temp = 0; // 开辟一个临时空间, 存放交换的中间值
    int j=1; 
    int pos=0;// 记录最后一次交换的位置
    int flag=0; // 标志位
    while (left < right) 
    { 
        printf("---第%d趟正向扫描:\n",j);
        for (int i = left,k=1; i < right; i++,k++) { // 保证 a[right] 是最大的
            if (arr[i] > arr[i+1]) {
                temp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = temp;
                flag=1;
                pos=i;
            }
            printf("------第%d趟正向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        right = pos;  // 将最后一次交换的位置作为右边界
        if (flag==0) { // 上一轮没有交换，提前结束
            break;
        }
        flag=0;
        printf("---第%d反趟向扫描:\n",j);
        for (int i = right,k=1; i > left; i--,k++) { // 保证 a[left] 是最小的
            if (arr[i] < arr[i-1]) {
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
                flag=1;
                pos=i;
            }
            printf("------第%d趟反向扫描第%d次交换:\n",j,k);
            printArray(arr,n);
        }
        left = pos;  // 将最后一次交换的位置作为右边界
        if (flag==0) { // 上一轮没有交换，提前结束
            break;
        }
        flag=0;
        j++;
    }
    //printf("----第%d遍最终结果:",i+1);
    printArray(arr,n);
}
 
void printArray(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

五、算法时间复杂度分析

1、最优情况

冒泡法排序的最好情况是数据元素集合已经全部排好序，这时循环n-1次每次没有交换动作而退出。
（1）对于常规冒泡排序算法来说：
虽然不进行交换动作，但依然要进行内部的循环【看上述代码】。
举个例子来说，一个数列【5，4， 3， 2， 1 】进行冒泡降序排列。
第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，不交换位置；比较4和3，3比4小，不交换位置……，最后比较1和2，1比2小，不交换位置。这时候共进行了4次比较。
第二次大循环从第一个数（5）开始到倒数第二个数（2）结束。进行3次比较交换运算。
……
所以总的比较次数为 4 + 3 + 2 + 1 = 10次。
对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数。
而O(N²)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n² - n) / 2 = (100000000 - 10000) / 2，相对10⁸来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N²。用O(N²)就表示了其数量级（忽略前面系数0.5）。
所以对于常规的冒泡排序算法，最优情况下，冒泡排序的时间复杂度为O(n²)。
（2）对于优化冒泡排序算法来说：
当然，也有很多人说冒泡排序的最优的时间复杂度为：O(n)；其实这是在代码中使用一个标志位来判断是否已经排序好的。
小伙伴们可以看看上述优化一或者优化二等的代码，就可以发现对于一个已经全部排好序的序列【5，4， 3， 2， 1 】进行降序的冒泡排序，只需要执行4次比较就结束。如下图：

添加标记位

因此对于这种添加标记位的冒泡排序，其最优情况时间复杂度就是O(n)。

2、最坏情况

最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。
举个例子来说，一个数列【5，4， 3， 2， 1 】进行冒泡升序排列。
第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成【4 ，5， 3， 2， 1】；比较5和3，3比5小，交换位置变成【4 ，3， 5， 2， 1】……最后比较5和1，1比5小，交换位置变成【4 ，3 ，2， 1， 5】。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。
第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。
……
所以总的比较次数为 4 + 3 + 2 + 1 = 10次。
对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数。
除此之外，还要进行交换移动次数 3n(n-1)/2次。
通过计算，最终得到的时间复杂度也是O(n²)。

3、综上所述

最优的时间复杂度为： O(n)【优化算法得到】；
最差的时间复杂度为：O( n² )；
平均的时间复杂度为：O( n²)；

六、算法空间复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存空间；有关空间复杂度，小编就不做分析了，大致如下：
1、最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
2、最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
3、平均的空间复杂度为：O(1)；

七、写在最后

接下来，小编将利用空闲的时间。整理其他九大排序算法。小编水平有限，有误的请指正。

最后编辑于：2021.05.16 06:17:30

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,271评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,275评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,151评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,550评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,553评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,559评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,924评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,580评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,826评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,578评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,661评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,363评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,940评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,926评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,156评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,872评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,391评论 2赞 342