当前位置：首页 > 算法 > 正文内容

【排序】----冒泡排序

亿万年的星光5年前 (2021-01-28)算法2942

1.基本思想

两个数比较大小，较大的数下沉，较小的数冒起来。

2.过程

·每次比较相邻的两个数，如果第二个数小，就交换位置。（升序或降序）

·然后两两比较，一直到比较最后的数据。最终最小（大）数被交换到开始（结束）位置，这样第一个最小（大）数的位置就排好了。

·继续重复上述过程，依次将第2,3…n-1个最小数排好位置。

动图过程：

举例说明：【1 4 3 2】

第一趟排序：

第一次排序：1和4比较，1小于4，不交换位置。【1 4 3 2】

第二次排序：4和3比较，4大于3，交换位置。【1 3 4 2】

第三次排序：4和2比较，4大于2，交换位置。【1 3 2 4】

第二趟排序：

第一次排序：1和3比较，1小于3，不交换位置。【1 3 2 4】

第二次排序：3和2比较，3大于2，交换位置。【1 2 3 4】

第三次排序： 3和4比较，3小于4，不交换位置。【1 2 3 4】

第三趟排序：

第一次排序，1和2比较，1小于2，不交换位置。【1 2 3 4】

第二次排序，2和3比较，2小于3，不交换位置。【1 2 3 4】

第三次排序，3和4比较，3小于4，不交换位置。【1 2 3 4】

2.注意点

在冒泡排序中，两个数比较大小，只需要比较一次就行。

n个数比较大小（选出最大或者最小），比较n-1次就行。

3.参考代码

#include<iostream>
using namespace std;
int main()
{
     int arr[]={12,45,13,88,79,11,52}; //定义数组
     int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 
     int length = len-1; //排序总轮数() 
     for(int i=0;i<length;i++)
     {
         for(int j=0;j<length-i;j++)
         {
            if (arr[j]>arr[j+1])  //如果前一个数比后一个大 
            {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] =temp; 
            } 
        }
        /*
        for(int i=0;i<length;i++)
             cout<<arr[i]<<" "; 
         cout<<endl;
        */
     }
     //输出
     for(int i=0;i<length;i++)
         cout<<arr[i]<<" "; 
     return 0; 
}

如果需要手动读入数组，那么参考下面这个版本:

#include<iostream>
using namespace std;
int main()
{
     int n,a[100];
	 cin>>n;
	 for(int i=0;i<n;i++){
	 	cin>>arr[i];
	 } 
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n-1-i;j++)
         {
            if (arr[j]>arr[j+1])  //如果前一个数比后一个大 
            {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] =temp; 
            } 
        }
        /*
        for(int i=0;i<length;i++)
             cout<<arr[i]<<" "; 
         cout<<endl;
        */
     }
     //输出
     for(int i=0;i<length;i++)
         cout<<arr[i]<<" "; 
     return 0; 
}

4.问题及改进

由程序输出可以看出，在第5次的时候已经排序完了，后面的元素都没有交换过，也就说后面几次排序都是没有意义的。这样就可以改进一下排序算法，设置一个元素位置交换标志记录本次排序是否有位置发生变化，如果没有则认为已经排序完了，不需要再执行了。

#include<iostream>
using namespace std;
int main() {
    int arr[]= {12,45,13,88,79,11,52,66}; //定义数组
    int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
    int length = len-1; //排序总轮数
    bool flag = true; //标志位，记录每次排序是否有元素位置交换
    for(int i=0; i<length && flag!=false; i++) { //如果上次排序元素位置未改变过，
        flag = false; //每次排序前，标志位复位
        for(int j=0; j<length-i; j++) {
            if (arr[j]>arr[j+1]) { //如果前一个数比后一个大
                flag = true; //发生位置交换，改变标志位
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] =temp;
            }
        }
         /*
        for(int i=0;i<length;i++)
             cout<<arr[i]<<" "; 
         cout<<endl;
        */
    }
        //输出
     for(int i=0;i<length;i++)
         cout<<arr[i]<<" "; 
    return 0;
}