【Day21】[演算法]-排序Sort & 气泡排序法Bubble Sort

排序（Sorting）

排序（Sorting）在电脑领域中是非常普遍且重要工作，即是将一群不规格的资料按照某个规格来重新排列，让排序过的资料容易阅读、利於统计整理、和减少搜寻时间，假若资料只有10笔左右，还能以人工的方式排序，但若资料多到万笔以上就会相当困难，因此，排序演算法就变得相当重要。

气泡排序法(Bubble Sort)

气泡排序法(Bubble Sort)又称交换排序法，原理是从第一笔资料开始，逐一比较相邻两笔资料，如果两笔大小顺序有误则做交换，反之则不动，接者再进行下一笔资料比较，所有资料比较完第1回合後，可以确保最後一笔资料是正确的位置。

下面利用40 30 60 50 20由小到大排序。

n=5
第1回合比较了4次，n-1次
第2回合比较了3次，n-2次
第3回合比较了2次，n-3次
第4回合比较了1次，n-4次
总共比较了4回合，n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均时间复杂度为: O(n²)

JavaScript

let data = [8,6,1,10,5,3,9,2,7,4]

function BubbleSort(array){
  let len = array.length
  while (len > 1) {
    len--
    for (let i = 0; i < len; i++) {
      // 如果前面的元素比後面的元素要大，则交换元素位置
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
      }
    }
  }
  return array
}
console.log(BubbleSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Bubble Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def BubbleSort(data):
    n = len(data)
    while n > 1:
        n-=1
        for i in range(n):        
            if data[i] > data[i+1]:  
                data[i], data[i+1] = data[i+1], data[i]
    return data

print(BubbleSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]