寫于: 2016年06月06日

自學(xué)算法 ing ...

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

加油, 努努! (ps:夜深人靜想點(diǎn)事情也方便.有點(diǎn)矯情了喔, 嘿^_)

冒泡排序

原理

倆倆比較 相鄰記錄的排序碼, 若發(fā)生逆序, 則交換; 有兩種方式進(jìn)行冒泡, 一種是先把小元素的冒泡到前邊去(常用), 另一種是把大的元素冒泡到后邊.

實(shí)現(xiàn)步驟, 請(qǐng)前往下一篇:Take my word for it 看完這些 你會(huì)徹底理解排序算法看視頻喔!

性能

時(shí)間復(fù)雜度為O(N^2), 空間復(fù)雜度為O(1). (ps:不懂的自行百度喔)
排序是穩(wěn)定的, 排序比較次數(shù)與初始序列無關(guān), 但交換次數(shù)與初始序列有關(guān).

==廢話不說, 看代碼==

#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;
}

結(jié)果:

優(yōu)化

比如{2,1,3,4,5,6,7,8,9},除了第一次循環(huán)交換,后面都會(huì)排好的無序在交換. 即初始序列就是排序好的, 對(duì)于冒泡排序任然還要比較O(N^2)次, 但無交換次數(shù). 可根據(jù)這個(gè)進(jìn)行優(yōu)化, 設(shè)置一個(gè)標(biāo)記變量flag, 標(biāo)記數(shù)列中的數(shù)是否在循環(huán)結(jié)束前就已經(jīng)排好序. 當(dāng)在一趟序列中沒有發(fā)生交換, 則該序列已排序好, 但優(yōu)化后排序的時(shí)間復(fù)雜度 沒有發(fā)生量級(jí)的改變.

==呈上代碼==

#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; //設(shè)置標(biāo)記變量
    for (int i = 0; i < 10 && flag; i++) {
        flag = 0; //只要flag在下一次外循環(huán)條件檢測的時(shí)候值為0, 就說明已經(jīng)排好序,不用繼續(xù)循環(huán)
        for (int j = 9; j > i; j--) {
            if (arr[j] < arr[j-1]) {
               swap(&arr[j], &arr[j-1]);
               flag = 1; //如果有交換, 就將標(biāo)記變量賦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;