冒泡排序是什麼
是一種簡單的比較排序法，原理是將元素反覆與相鄰元素比較，逐步將最大元素排到數列尾端，直到所有元素排好。
舉例
一個數列[75,93,33,81,75]用冒泡排序。
回合 1. [75,93,33,81,75]
[75,33,93,81,75]
[75,33,81,93,75]
[75,33,81,75,93]
回合2. Pass 2 [75,33,81,75,93]
[33,75,81,75,93]
[33,75,75,81,93]
時間複雜度
第一輪會做n-1次比較，
第二輪會做n-2次比較，依此類推
共需比較次數(n-1)+(n-2)+...+1=
(((n-1)+1)*(n-1))/2=(n*(n-1))/2
，所以時間複雜度為O(n^2)
沒有留言:
張貼留言
寫下幸福點子吧！