算法工程师之排序算法Python

一个合格的算法工程师应该具有熟练写各种排序算法的本领

1&＃xff0c;快速排序&＃xff08;n*logn&＃xff09;

分治法&＃xff0c;主要是它的划分过程&＃xff0c;即选取一个值将list中不大于该数的放在该数左边&＃xff0c;不小于该数的放在该数右边&＃xff0c;然后分别对左右两个区间递归划分。

def sortmy(arr, low, high):if low &＃61; key:high -&＃61; 1arr[low] &＃61; arr[high]while low sortmy(arr, 0, len(arr) - 1)
print(arr)

2, 冒泡排序&＃xff08;n^2&＃xff09;

每次循环将最大的值放在数组最后

def sortmy(arr, n):while n:for i in range(n-1):if arr[i] > arr[i&＃43;1]:arr[i], arr[i&＃43;1] &＃61; arr[i&＃43;1], arr[i]n -&＃61; 1arr &＃61; list(map(int, input().split()))
sortmy(arr, len(arr))
print(arr)

3&＃xff0c;堆排序&＃xff08;n*logn&＃xff09;

先构建大根堆&＃xff08;没有排好序&＃xff09;&＃xff0c;然后将堆顶位置的值&＃xff08;即最大值&＃xff09;与最后一个值交换&＃xff0c;然后再将更新后的大根堆进行重新构建&＃xff0c;最后会得到一个排好序的数组。具体参考堆的构建及堆排序&＃xff08;C&＃43;&＃43;&＃xff09;

def sortmy(arr, n):for i in range(int(n / 2 - 1), -1, -1):heapAdjust(arr, i, n - 1)while n - 1:arr[0], arr[n - 1] &＃61; arr[n - 1], arr[0]n -&＃61; 1heapAdjust(arr, 0, n - 1)def heapAdjust(arr, low, high):"""构建大根堆:param arr::param low::param high::return:"""rc &＃61; arr[low] # 头节点i &＃61; low * 2 &＃43; 1 # 左孩子while i <&＃61; high:if i arr[i]: # 头节点大于孩子节点就不操作breakarr[low] &＃61; arr[i] # 否则将较大的孩子节点赋值给头节点low &＃61; i # 开始将这个较大节点作为新头节点继续遍历i &＃61; 2 * i &＃43; 1arr[low] &＃61; rc # 循环执行完毕需要将一开始的头节点赋值给循环中的新头节点arr &＃61; list(map(int, input().split()))
sortmy(arr, len(arr))
print(arr)

4、归并排序

分而治之&＃xff0c;核心是将两个有序数组组合成一个有序数组&＃xff0c;即下面的归并过程代码

import copy
import randomdef merge(arr, start, mid, end):"""归并过程:param arr::param start::param end::return:"""res &＃61; copy.deepcopy(arr)Mid &＃61; midfor idx in range(start, end &＃43; 1):if start > Mid: # 左分支已遍历完arr[idx] &＃61; res[mid &＃43; 1]mid &＃43;&＃61; 1elif mid &＃61;&＃61; end: # 右分支已遍历完arr[idx] &＃61; res[start]start &＃43;&＃61; 1elif res[start] <&＃61; res[mid &＃43; 1]: # 左分支的值小于右分支arr[idx] &＃61; res[start]start &＃43;&＃61; 1else:arr[idx] &＃61; res[mid &＃43; 1] # 左分支的值大于右分支mid &＃43;&＃61; 1def merge_sort(arr, start, end):"""归并排序递归函数:param arr: :param start: :param end: :return: """if end &＃61;&＃61; start:returnmid &＃61; int((start &＃43; end) / 2)merge_sort(arr, start, mid)merge_sort(arr, mid &＃43; 1, end)merge(arr, start, mid, end)a &＃61; random.sample(range(100), 100)
print(a)
merge_sort(a, 0, len(a) - 1)
print(a)


5、选择排序

挺垃圾的一种排序方法&＃xff0c;还不如冒泡

import randomdef select_sort(arr, n):"""选择排序:param arr::return:"""for i in range(n):minIdx &＃61; ifor j in range(i, n):if arr[j] print(a)
select_sort(a, len(a))
print(a)


6、插入排序

时间复杂度也挺高&＃xff0c;但是代码实现起来设计巧妙如下&＃xff0c;循环遍历数组&＃xff0c;将未排序的数一个个插入到前面已排好序的数组中&＃xff0c;未申请额外空间

import randomdef insert_sort(arr, n):"""插入排序:param arr::param n::return:"""for i in range(1, n):for j in range(i - 1, -1, -1):if arr[j&＃43;1] print(a)
insert_sort(a, len(a))
print(a)


7、希尔排序

插入排序的改进版&＃xff0c;设计的非常巧妙&＃xff0c;也可以说插入排序是特殊情况的希尔排序&＃xff0c;即gap设为1时&＃xff0c;两者就是一样的。只不过shell由小及大&＃xff0c;通过设置不同的增量&＃xff08;这里的增量是[n/2, n/2/2, ..., 1]&＃xff0c;也可以设为其他&＃xff09;来实现最终的排序。

import randomdef shell_sort(arr, n):"""希尔排序:param arr::param n::return:"""gap &＃61; int(n / 2)while gap:for i in range(gap, n):for j in range(i - gap, -1, -gap):if arr[j] > arr[j &＃43; gap]:arr[j], arr[j &＃43; gap] &＃61; arr[j &＃43; gap], arr[j]gap &＃61; int(gap / 2)a &＃61; random.sample(range(100), 100)
print(a)
shell_sort(a, len(a))
print(a)