侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

冒泡排序

kaixindeken
2021-04-19 / 0 评论 / 0 点赞 / 102 阅读 / 1,339 字

我们在选择排序算法的时候,通常会根据以下几个维度来考虑:

  • 时间复杂度
  • 空间复杂度(对内存空间的消耗)
  • 算法的稳定性(如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变)

实现原理

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

光看定义有点抽象,我们用图来演示,假设待排序数字是 4、5、6、3、2、1,第一次排序的流程是这样的:

1.png

看这个图的时候要结合定义一起看,否则也比较懵逼,当然如果你去 VisuAlgo 上看动态图的话就更形象了:https://visualgo.net/zh/sorting ,经过 n 次冒泡,最终完成排序(所谓冒泡,以升序来看,就是每次把待排序序列中的最大值插到已排序序列的最前面,这个过程就像冒泡一样):

1.png

示例代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h.h>
//从头向尾遍历
//相邻两数进行比较
//将最大数(相对)沉入尾部(相对)
void BubbleSort1(int *arr,int sz){
    int i = 0;
    int j = 0;
    assert(arr);
    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]>arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
//从尾向头遍历
//相邻两数进行比较
//将最小数(相对)冒泡到头部(相对)
void BubbleSort2(int *arr,int sz){
    int i = 0;
    int j = 0;
    assert(arr);
    for(i=0;i<sz-1;i++){
        for(j=sz;j>i;j--){
            if(arr[j]>arr[j-1]){
                int tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }
    }
}

void TestBubbleSort(void (*BubbleSort)(int *arr,int sz)){
    int arr[]={1,3,5,7,9,2,4,6,8,0};
    int i = 0;
    int sz = sizeof(arr)/sizeof(arr[0]);
    BubbleSort(arr,sz);
    for(i=0; i<sz; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

int main(){
    TestBubbleSort(BubbleSort1);
    TestBubbleSort(BubbleSort2);
    system("pause");
    return 0;
}

性能分析

最后我们来看下冒泡排序的性能和稳定性:

  • 时间复杂度: O(n2)
  • 空间复杂度:只涉及相邻元素的交换,是原地排序算法
  • 算法稳定性:元素相等不会交换,是稳定的排序算法
  • 时间复杂度是 O(n2),看起来性能并不是很好,所以我们在实践中基本不会选用冒泡算法。
0

评论区