排序算法之 ____ 冒泡排序

写于: 2016年06月06日

自学算法 ing ...

感谢iOS路上不可替代的小伙伴JXT (......)

加油, 努努! (ps:夜深人静想点事情也方便.有点矫情了喔, 嘿^_)

冒泡排序

原理

俩俩比较 相邻记录的排序码, 若发生逆序, 则交换; 有两种方式进行冒泡, 一种是先把小元素的冒泡到前边去(常用), 另一种是把大的元素冒泡到后边.

实现步骤, 请前往下一篇:Take my word for it 看完这些 你会彻底理解排序算法看视频喔!

性能

时间复杂度为O(N^2), 空间复杂度为O(1). (ps:不懂的自行百度喔)
排序是稳定的, 排序比较次数与初始序列无关, 但交换次数与初始序列有关.

==废话不说, 看代码==

#include <stdio.h>
void swap(int *a, int *b);
int main () {
    int arr[10] = {15, 226, 34, 49, 6, 78, 523, 312, 8, 99};
    for (int i = 0; i < 10; i++) { //每一次由底至上地上升
        for (int j = 9; j> i; j--) {
            if (arr[j] < arr[j-1]) {
               swap(&arr[j], &arr[j-1]);
         }
      }
   }
   for (int i = 0; i < 10; i++) {
       printf("%d ",arr[i]);
   }
  return 0;
}
void swap(int *a, int *b) {
     int temp;  
     temp = *a;
     *a = *b;
     *b = temp;
}

结果:

优化

比如{2,1,3,4,5,6,7,8,9},除了第一次循环交换,后面都会排好的无序在交换. 即初始序列就是排序好的, 对于冒泡排序任然还要比较O(N^2)次, 但无交换次数. 可根据这个进行优化, 设置一个标记变量flag, 标记数列中的数是否在循环结束前就已经排好序. 当在一趟序列中没有发生交换, 则该序列已排序好, 但优化后排序的时间复杂度 没有发生量级的改变.

==呈上代码==

#include <stdio.h>
void swap(int *a, int *b);
int main() {
    int arr[10] = {2, 1, 3, 4, 5, 6, 7, 8 ,9, 10};
    int flag = 1; //设置标记变量
    for (int i = 0; i < 10 && flag; i++) {
        flag = 0; //只要flag在下一次外循环条件检测的时候值为0, 就说明已经排好序,不用继续循环
        for (int j = 9; j > i; j--) {
            if (arr[j] < arr[j-1]) {
               swap(&arr[j], &arr[j-1]);
               flag = 1; //如果有交换, 就将标记变量赋1
        }
     }
  }
  for (int i = 0; i < 10; i++) {
      printf("%d ",arr[i]);
  }
 return 0;
}
void swap(int *a, int *b);
int temp;
temp = *a;
*a = *b;
*b = temp;