冒泡排序

  1. —冒泡排序—
    1. 算法描述
    2. 代码实现
      1. 常规冒泡排序
      2. 改进版冒泡排序
    3. 算法分析
    4. 稳定性

—冒泡排序—

​ 重复地走访要排序的数列,依次比较两个元素。顺序错误则交换顺序,否则不改变原先顺序。

算法描述

具体算法描述如下:

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

冒泡排序

代码实现

常规冒泡排序

//  常规冒泡排序
void Bubble_Sort(int a[], int n)   // (数组,数组长度)
{  
    //外层循环(趟数) 最后一个元素已经有序 故 n-1
    for (int i = 0; i < n - 1; ++i)
    {    //内层循环,最后一个元素已经有序且每次向右移动进行比较 故 n-1-i
        for (int j = 0; j < n - 1 - i; ++j)
        {   // 升序
            if (a[j] > a[j + 1])     // 如果前个元素比后后面一个元素大
            {
                int temp = a[j];    // 交换元素
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

改进版冒泡排序

改进冒泡排序: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

耗时会比常规冒泡排序少一些.

// 改进版冒泡排序
void Bubble_sort(int a[],int n)
{
    int i = n - 1;          //初始时,最后位置保持不变
    while (i > 0) {
        int pos = 0;         //每趟开始时,无记录交换
        for (int j = 0; j < i; j++)
            if (a[j] > a[j + 1]) {
                pos = j;               //记录交换的位置
                int tmp = a[j]; 
                a[j] = a[j + 1]; 
                a[j + 1] = tmp;
            }
        i = pos;   //为下一趟排序作准备
    }

}

算法分析

  • 平均情况:T(n) = O(n2)

  • 最佳情况:T(n) = O(n)

当输入的数据已经是正序时

  • 最差情况:T(n) = O(n2)

当输入的数据是反序时

稳定性

  • 稳定

​ 若相邻元素相等,则不交换两元素位置,故稳定。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com

×

喜欢就点赞,疼爱就打赏