認識排序
在電腦科學與數學中，一個排序演算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種演算法。最常用到的排序方式是數值順序以及字典順序。有效的排序演算法在一些演算法（例如搜尋演算法與合併演算法）中是重要的，如此這些演算法才能得到正確解答。排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序演算法的輸出必須遵守下列兩個原則：
- 輸出結果為遞增序列（遞增是針對所需的排序順序而言）
- 輸出結果是原輸入的一種排列、或是重組
雖然排序演算法是一個簡單的問題，但是從電腦科學發展以來，在此問題上已經有大量的研究。舉例而言，氣泡排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新演算法仍在不斷的被發明。
氣泡排序
氣泡排序法(Bubble Sort)是最容易理解和實作的一種排序演算法，也翻譯作冒泡排序法。由於它很容易學習，所以也是許多演算法課程中第一個學習的排序演算法。
由於他的演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動，就像有許多氣泡慢慢從底部浮出，因此成為氣泡排序法。他的運作流程如下：
- 比較相鄰的兩個元素，若前面的元素較大就進行交換。
- 重複進行1的動作直到最後面，最後一個元素將會是最大值。
- 重複進行1,2的動作，每次比較到上一輪的最後一個元素。
- 重複進行以上動作直到沒有元素需要比較。
實作上直接使用迭代法迴圈就可以很容易的完成。另外可以使用額外的旗標(Flag)來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到O(n)。
//JS
<script>
var swap = function(data, i, j){
var tmp = data[i];
data[i] = data[j];
data[j] = tmp;
};
var bubbleSort = function(data){
var flag = true;
for(var i = 0; i < data.length - 1 && flag; i++){
flag = false;
for(var j = 0; j < data.length - i - 1; j++){
if(<pre>data[j+1]<pre> < <pre>data[j]<pre> ) {
swap(data, j+1, j);
flag = true;
}
}
}
};
</script>
//JS
//Python
#選擇排序法
def showdata(data):
for i in range(8):
print('%3d' %data[i],end='')
print()
def select (data):
for i in range(7):
for j in range(i+1,8):
if data[i]>data[j]: #比較第i及第j個元素
data[i],data[j]=data[j],data[i]
print()
data=[16,25,39,27,12,8,45,63]
print('原始資料為:')
for i in range(8):
print('%3d' %data[i], end='')
print('\n----------------------------------------')
select(data)
print("排序後資料")
for i in range(8):
print('%3d' %data[i],end='')
print('')
//Python
選擇排序法
選擇排序法 (Selection Sort)
時間複雜度為 O(n²) 的演算法，代表著執行步驟會跟著輸入 n 成次方比例的增加。最基礎的排序法之一：選擇排序法(Selection Sort) 是 O(n²) 複雜度的代表。
基本來說，選擇排序只需要重複執行兩個步驟，分別是：
找最小值
- 從「未排序好的數字」中找到最小值
丟到左邊
- 把最小值丟到「未排序好的數字」的最左邊，把它標示成已排序好
假設有一個 [41, 33, 17, 80, 61, 5, 55] 的陣列，我們用圖的例子來一步一步理解選擇排序是如何進行，在下面的圖中，我們把尚未排序好的數字用紅色標示，這輪找到的最小值以橘色標示，排序好的以藍色標示。
//python
#選擇排序法
def showdata(data):
for i in range(8):
print('%3d' %data[i],end='')
print()
def select (data):
for i in range(7):
for j in range(i+1,8):
if data[i]>data[j]: #比較第i及第j個元素
data[i],data[j]=data[j],data[i]
print()
data=[16,25,39,27,12,8,45,63]
print('原始資料為:')
for i in range(8):
print('%3d' %data[i], end='')
print('\n----------------------------------------')
select(data)
print("排序後資料")
for i in range(8):
print('%3d' %data[i],end='')
print('')
//python
出處:按此連結
插入排序法
同樣擁有 O(n²) 時間複雜度，插入排序法 Insertion Sort 則是另外一個非常常見的排序法。簡單來說，插入排序法就是你玩撲克牌時用到的排序法。
讀一個數字
- 從「未排序過的數字」中讀取一個數
插入合適位置
- 把這個讀取的數往前插入一個位置
<pre>//python
//插入排序:
SIZE=8
def showdata(data):
for i in range(SIZE):
print('%3d' %data[i], end='')
print()
def insert(data):
for i in range(1,SIZE):
tmp=data[i]
no=i-1
while no >= 0 and
tmp < data[no]:
data[no+1]=data[no]
no-=1
data[no+1]=tmp
def main():
data=[16,25,39,27,12,8,45,63]
print('原始陣列:')
showdata(data)
insert(data)
print('排序後:')
showdata(data)
main()
//python
</pre>
謝耳排序法
![若有n筆資料要進行排序時，先求出初始間隔值 Gap = 3. 依照間隔值將資料分割成數個區塊。 4. 再利用插入排序法針對數個區塊內的資料進行排序. 5. 最後，再縮小間隔值範圍，重複步驟3與步驟4，直到間隔值Gap=1， 排序即可完成。 [n Div 2]代表n除以2之後，取下限.](https://brian.oneofpeace.org/wp-content/uploads/2019/07/6-12謝耳排序.jpg)
#謝耳排序
SIZE = 8
def showdata(data):
for i in range(SIZE):
print('%3d' %data[i],end='')
print()
def shell(data,size):
k=1
jmp=size//2
while jmp != 0:
for i in range(jmp, size):
tmp=data[i]
j=i-jmp
while tmp<data[j] and j>=0:
data[j+jmp] = data[j]
j = j-jmp
data[jmp+j]=tmp
print('第 %d 次排序過程:' %k,end='')
k+=1
showdata (data)
print('----------------')
jmp=jmp//2
def main():
data=[16,25,39,27,12,8,45,63]
print('原始陣列:')
showdata (data)
print('---------------')
shell(data,SIZE)
main()
