排序算法（Python实现）
最近找实习，把之前用Java实现过排序算法，重新实现一下，当作复习。之前Java版实现的文章
冒泡排序
def bubbleSort(arr):
if arr is None or len(arr) == 0:
return []
l = len(arr)
for i in range(l - 1):
for j in range(l - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
选择排序
def selectSort(arr):
if arr is None or len(arr) == 0:
return []
l = len(arr)
for i in range(l - 1):
minIndex = i
for j in range(i + 1, l):
if arr[j] < arr[minIndex]:
minIndex = j
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
插入排序
def insertSort(arr):
if arr is None or len(arr) == 0:
return []
l = len(arr)
for i in range(1, l):
current = arr[i]
preIndex = i - 1
while preIndex >= 0 and arr[preIndex] > arr[i]:
arr[preIndex + 1] = arr[preIndex] # 后移
preIndex -= 1
arr[preIndex + 1] = current
return arr
希尔排序
def shellSort(arr):
if arr is None or len(arr) == 0:
return []
l = len(arr)
h = 1
while h < l/3:
h = 3*h + 1
while h>0:
for i in range(h, l):
for j in range(i, h-1, -1):
if arr[j] < arr[j-h]:
arr[j], arr[j-h] = arr[j-h], arr[j]
h = int(h/3)
return arr
快速排序
def quickSort(arr, left, right):
if left >= right:
return
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex, right)
return arr
def partition(arr, left, right):
pivot = arr[right]
i = left
for j in range(left, right):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[right] = arr[right], arr[i]
return i
归并排序
归并排序，其实就是不断二分，然后二分排序好的子集进行合并
# 归并排序
def merge(arr, left, right):
result = [] # 借助辅助空间
mid = (left + right) >> 1
leftIndex, rightIndex = left, mid + 1
print("left: %s, right: %s, %s" % (left, right, arr[left: right+1]))
while leftIndex <= mid and rightIndex <= right:
# 用辅助空间
if arr[leftIndex] < arr[rightIndex]:
result.append(arr[leftIndex])
leftIndex += 1
else:
result.append(arr[rightIndex])
rightIndex += 1
while leftIndex <= mid:
result.append(arr[leftIndex])
leftIndex += 1
while rightIndex <= right:
result.append(arr[rightIndex])
rightIndex += 1
for i in range(left, right+1):
arr[i] = result[i-left]
print("After sort, left: %s, right: %s, %s" % (left, right, arr[left: right + 1]))
def sort(arr, left, right):
if left >= right:
return
mid = (left + right) // 2
sort(arr, left, mid)
sort(arr, mid + 1, right)
merge(arr, left, right)
def mergeSort(arr, left, right):
sort(arr, left, right)
return arr
if __name__ == '__main__':
mergeSort([3, 44, 38, 5, 47, 15, 26, 2, 46, 19, 50, 48], 0, 11)
结果展示
left: 0, right: 1, [3, 44]
After sort, left: 0, right: 1, [3, 44]
left: 0, right: 2, [3, 44, 38]
After sort, left: 0, right: 2, [3, 38, 44]
left: 3, right: 4, [5, 47]
After sort, left: 3, right: 4, [5, 47]
left: 3, right: 5, [5, 47, 15]
After sort, left: 3, right: 5, [5, 15, 47]
left: 0, right: 5, [3, 38, 44, 5, 15, 47]
After sort, left: 0, right: 5, [3, 5, 15, 38, 44, 47]
left: 6, right: 7, [26, 2]
After sort, left: 6, right: 7, [2, 26]
left: 6, right: 8, [2, 26, 46]
After sort, left: 6, right: 8, [2, 26, 46]
left: 9, right: 10, [19, 50]
After sort, left: 9, right: 10, [19, 50]
left: 9, right: 11, [19, 50, 48]
After sort, left: 9, right: 11, [19, 48, 50]
left: 6, right: 11, [2, 26, 46, 19, 48, 50]
After sort, left: 6, right: 11, [2, 19, 26, 46, 48, 50]
left: 0, right: 11, [3, 5, 15, 38, 44, 47, 2, 19, 26, 46, 48, 50]
After sort, left: 0, right: 11, [2, 3, 5, 15, 19, 26, 38, 44, 46, 47, 48, 50]
