Python實現氣泡排序，選擇排序，插入排序，快速排序和堆排序

摘要： 氣泡排序 時間複雜度：O(n²) 空間複雜度：O(1) 健壯性：健壯 難易程度：簡單 def bubbleSort(li): for i in range(len(li) - 1): for j in range(len(...

氣泡排序

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 健壯性：健壯
• 難易程度：簡單

def bubbleSort(li):
for i in range(len(li) - 1):
for j in range(len(li) - i - 1):
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]

li = [345, 456, 68.435, 1, 6, 4, 568, ]
bubbleSort(li)
print(li)

選擇排序

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 健壯性：健壯
• 難易程度：簡單

def selectSort(li):
for i in range(len(li) - 1):
min = I# 選擇一個小的來比較
for j in range(i + 1, len(li)):
if li[min] > li[j]:
li[min], li[j] = li[j], li[min]

li = [345, 456, 68.435, 1, 6, 4, 568, ]
selectSort(li)
print(li)

插入排序

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 健壯性：健壯
• 難易程度：較複雜

def insertSort(li):
for i in range(len(li) - 1):
temp = li[i]
j = i - 1
while j >= 0 and li[j] > temp:
li[j + 1] = li[j]
j = j - 1
li[j + 1] = temp


li = [345, 456, 68.435, 1, 6, 4, 568, ]
insertSort(li)
print(li)

快速排序

• 時間複雜度：O(nlogn)
• 空間複雜度：O(nlogn)
• 健壯性：不穩定
• 難易程度：複雜

def partition(li, left, right):
temp = li[left]

while left < right:
while li[right] > temp:
right -= 1
li[left] = li[right]

while li[left] < temp:
left += 1
li[right] = li[left]

li[left] = temp

return left

def quickSort(li, left, right):
if left < right:
mid = partition(li, left, right)
quickSort(li, left, mid - 1)
quickSort(li, mid + 1, right)


li = [345, 456, 68.435, 1, 6, 4, 568, ]
partition(li, 0, (len(li) - 1))
quickSort(li, 0, (len(li) - 1))
print(li)

堆排序

• 時間複雜度：O(nlog₂n)
• 空間複雜度：O(1)
• 健壯性：不穩定
• 難易程度： 困難

def heap_sort(array):
def heap_adjust(parent):
child = 2 * parent + 1# left child
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child += 1# right child
if heap[parent] >= heap[child]:
break
heap[parent], heap[child] = \
heap[child], heap[parent]
parent, child = child, 2 * child + 1

heap, array = array.copy(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
array.insert(0, heap.pop())
heap_adjust(0)
return array