網頁

2020年10月1日 星期四

C++排序教學1 - 泡沫排序法 Bubble Sort

前言

這個教學系列會討論各式排序演算法,並用C++來實現各式演算法,在文章最後也會寫出各式演算法的缺陷和優點,若在觀看過程有覺得可以改進的部分也歡迎在底下留言。

泡沫排序法簡述

泡沫排序法(Bubble Sort)是各式演算法中最簡單,也是幾乎最沒效率的一種,但是因概念簡單,適合初學排序演算法的人。

泡沫排序法的想法就比如想像在水中的泡泡,因為密度較低,便會慢慢向上浮出水面,同理,處裡在一排數字上,便是將密度小(數字小的)往前排序,並將密度大(數字大的)往後排序,以此類推,每次都將數字最小的移至前方,最後就能排序完成。

程式碼 (C++)

#include <stdio.h> void bubble_sort (int *param, int size) { bool not_sorted = true; //stop if already sorted for (int min = 0; min < size && not_sorted; min++) { not_sorted = false; for (int max = size; max > min; max--) { if (param[max - 1] > param[max]) //not what we want { int temp = param[max - 1]; param[max - 1] = param[max]; param[max] = temp; not_sorted = true; } } } } int main() { int array[10] = {1, 3, 5, 2, 7, 8, 0, 4, 6, 9}; bubble_sort(array, 10); for (int i = 0; i < 9; i++) printf("%d, ", array[i]); printf("%d", array[9]); }
輸出:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

優點

容易理解、不須額外使用記憶體

缺點

速度慢,正常情況下為O(n²),在大量數據下,相較其他演算法,處裡速度太慢。




👉【幫我們一個忙!】👈

👋如果您喜歡這篇文章,請在下方按5個Like!
 ❤您的支持是我們最大的動力!

您只要登入帳號(Facebook、Google),在下方按5個Like,我們就會收到來自LikeCoin基金會的贊助。
您只需要支持我們,完全不會花到錢!