一、冒泡排序
核心思想： 通过相邻元素的比较实现排序
def bubble_sort(a, length):'''冒泡排序'''for i in range(length-1):for j in range(0, length-1-i):if a[j] > a[j+1]:a[j], a[j+1] = a[j+1], a[j]a = [5, 2, 3, 1, 6, 8, 7, 4]bubble_sort(a, len(a))
二、选择排序
核心思想：每次选出最小的元素(记录索引)实现排序
def selection_sort(a, length):'''选择排序'''for i in range(length-1):idx = ifor j in range(i+1, length)if a[idx] > a[j]:idx = ja[i], a[idx] = a[idx], a[i]a = [5, 2, 3, 1, 6, 8, 7, 4]selection_sort(a, len(a))
三、快速排序
核心思想： 选择序列中一个数(一般都选择序列的第一个元素)，一次循环实现将比这个元素小的元素放到这个元素左边，将比这个元素大的放到元素右边
def quict_sort(a, start_index, end_index):'''快速排序核心函数Args:a = [] 待排序数组start_index = 数组开始索引值end_index = 数组结束索引值Return:a = [] 完成排序数组'''#if条件是递归结束条件if start_index >= end_index:returnboundary_index = quick_boundary(a, start_index, end_index)quict_sort(a, start_index, boundary_index - 1)quict_sort(a, boundary_index + 1, end_index)return adef quick_boundary(a, start_index, end_index):'''快速排序获取拆分边界索引值辅助函数Args:a = [] 待排序数组的拆分start_index = 拆分数组开始索引值end_index = 拆分数组结束索引值Return:boundary_index = Int 边界索引值'''boundary_index = start_indexstandard = a[boundary_index]left_index, right_index = start_index, end_indexwhile left_index < right_index:while left_index < right_index and standard <= a[right_index]:right_index -= 1a[left_index] = a[right_index]while left_index < right_index and standard >= a[left_index]:left_index += 1a[right_index] = a[left_index]a[left_index] = standardboundary_index = left_indexprint(boundary_index)print(a)return boundary_indexa = [49, 38, 65, 97, 76, 13, 27, 49]quict_sort(a, 0, len(a) - 1)
四、归并排序
核心思想：先递归分解数组，合并数组完成递归排序
def merge_array(a, start_index, mid_index, end_index):'''合并两个有序数组成一个有序数组Args:a = [] 待排序数组start_index = 数组开始索引值mid_index = 数组中间索引值，区分开两个有序数组end_index = 数组结束索引值Return:a = [] 合并的有序数组'''i, j = start_index, mid_index + 1m, n = mid_index, end_indextemp_list = []while i <= m and j <= n:if a[i] <= a[j]:temp_list.append(a[i])i += 1else:temp_list.append(a[j])j += 1while j <= n:temp_list.append(a[j])j += 1while i <= m:temp_list.append(a[i])i += 1for index in range(len(temp_list)):a[start_index + index] = temp_list[index]def merge_sort(a, start_index, end_index):'''归并排序核心函数Args:a = [] 待排序数组start_index = 数组开始索引值end_index = 数组结束索引值Return:a = [] 完成排序数组'''if start_index < end_index:mid_index = (start_index + end_index)/2merge_sort(a, start_index, mid_index)merge_sort(a, mid_index + 1, end_index)merge_array(a, start_index, mid_index, end_index)a = [3, 4, 1, 2, 9, 6, 5, 7, 12, 11, 10]merge_sort(a, 0, len(a) - 1)
五、堆排序
核心思想：堆排序是在不断自下向上调整堆结构，通过数组索引关联父节点和左右子节点
def adjustheap(a, i, n):'''调整堆'''j = 2*i + 1while j < n:if j+1 < n and a[j] < a[j+1]:j += 1if a[j] < a[i]:breaka[i], a[j] = a[j], a[i]i = jj = 2*i + 1def makeheap(a, n):'''建堆'''for i in range(int(n/2)-1, -1, -1):adjustheap(a, i, n)def heapsort(a, n):'''堆排序'''makeheap(a, n)for i in range(n-1, -1, -1):a[i], a[0] = a[0], a[i]adjustheap(a, 0, i)a = [5, 2, 3, 1, 6, 8, 7, 4]heapsort(a, len(a))
供参考！
