冒泡排序

前提条件:

-大多数情况下,为了简单起见只讨论从小到大的排序
-N是整数
-只讨论基于比较的排序(< > =有定义)
-只讨论内部排序,即加载到内存中的排序

相关概念

-稳定性:排序前相等的两个元素,排序后相对位置没有发生改变
-时间复杂度:时间复杂度是定量描述一个算法的运行的时间,一般与算法输入值的长度N有关,常用大O符号表述;

统一的入口

 void X_sort(int arr[] ,int N)
 ElenmentType 为数组类型  N 为数中元素的个数

示例图

冒泡排序.jpg

主函数

//冒泡排序
void Bubble_sort(int arr[] ,int N){
   //每趟排序都把最大的放最后一个,下次没必要比较最后一个
   for (int i = N-1; i >= 0; i--) {
       //判断是否已经有序,避免无用操作
       bool flag = 0;
       //比较相邻两个元素大小
       for (int j = 0; j < i; j++) {
           if (arr[j] > arr[j+1]) {
               //交换两个元素
               Swap(&arr[j], &arr[j+1]);
               //元素有交换,更改flag值
               flag = 1;
           }
       }
       if (flag == 0) {
         //这一趟没有交换任何元素,表明数组已为有序状态
           break;
       }
   }
}


交换函数

//交换元素
void Swap(int *a,int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

时间复杂度:

没有一种排序在任何情况下都是表现最好

最好情况:顺序 T = O(N)

最坏情况:逆序 T = O(N^2)

稳定性: 稳定

测试

int main(int argc, const char * argv[]) {
    //数组
    int arr[9] ={8,6,1,2,4,9,3,7,5};
   //冒泡排序函数
    Bubble_sort(arr, 9);
   //打印排序后结果
    for (int j= 0; j< 9; j++) {
        printf("%d",arr[j]);
    }
    return 0;
}

输出

Printing description of arr:
(int [9]) arr = ([0] = 1, [1] = 2, [2] = 3, [3] = 4, [4] = 5, [5] = 6, [6] = 7, [7] = 8, [8] = 9)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 项目需要,自己上学的时候接触过一些算法,我记得当时算法那门考了系里最高分,98分,想着没什么用呢,谁知道这两天就用...
    爱尚开发阅读 1,866评论 0 3
  • 拓扑排序 AOV网络(Activity On Vertex)拓扑序:如果在图中从V到W有一条有向路径,则V一定排在...
    Spicy_Crayfish阅读 917评论 0 0
  • 远方的诗 秋叶与风 借了酒放狂 阳光斜入窗 拿着笔 帮你计算时长 温柔把你关进笼子 安稳的写诗 写远方和狂妄
    雨安阳阅读 199评论 0 0
  • 这个年头,谁都缺钱,因此社会逐渐将利欲熏心看得理所当然。跟朋友谈梦想、聊未来,会被嘲笑被拒之门外;讲赚钱、说享乐,...
    JforJoker阅读 566评论 2 3
  • 注册简书,原因只想找一个可以随意发泄的地方。生活很奇怪,越是亲密的人,越要拿捏好什么该说,什么时候该闭嘴,分寸拿捏...
    Tina888888阅读 158评论 2 0