排序算法
一般排序算法最常考的:快速排序和归并排序。这两个算法体现了分治算法的核心观点,而且还有很多出题的可能。
1. 常见的排序算法
排序算法很多,除了能写出常见排序算法的代码,还需要了解各种排序的时空复杂度、稳定性、使用场景、区别等。
1.1 选择排序
1.1.1 思想
对于给定的一组序列,第一轮比较选择最小(或最大)的值,然后将该值与索引第一个进行交换;接着对不包括第一个确定的值进行第二次比较,选择第二个记录与索引第二个位置进行交换,重复到只剩最后一个记录位置。
案例:幼儿园排队,老师先让站成一队,带第一个小朋友依此跟其他小朋友逐个比较,选出个子最矮的,然后依此进行
1.1.2 实现
def selection_sort(gList): """选择排序 :param gList: 给定的一组序列 :return: 返回排好序的序列 """ length = len(gList) for i in range(length - 1): flag = i for j in range(i+1, length): if gList[flag] > gList[j]: flag = j # 如果最小值的索引与最小值相对应,则无需再次交换 if flag != i: gList[flag], gList[i] = gList[i], gList[flag] return gList
1.1.3 选择排序分析
- 时间复杂度: 最好、最坏、平均的时间复杂度都为O(n2)
- 空间复杂度:O(1)
- 稳定性: 不稳定
1.2 冒泡排序
1.2.1 思想
对于给定的一组序列含 n 个元素,从第一个开始对相邻的两个记录进行比较,当前面的记录大于后面的记录,交换其位置,进行一轮比较和换位之后,最大记录在第 n 个位置;然后对前(n-1)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个时为止。
案例:冒泡,像气泡一样往上升
1.2.2 实现
def bubble_sort(gList): """冒泡排序""" length = len(gList) for i in range(length): for j in range(i+1, length): if gList[i] > gList[j]: gList[i], gList[j] = gList[j], gList[i] return gList
1.2.3 冒泡排序分析
- 时间复杂度:
- 最好时间复杂度:O(n)
- 最坏时间复杂度: O(n2)
- 平均时间复杂度: O(n2)
- 空间复杂度: O(1)
- 稳定性: 稳定的排序
1.3 插入排序
1.3.1 思想
对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列;接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止。
案例:抓扑克牌
1.3.2 实现
def insertion_sort(gList): """插入排序""" length = len(gList) for i in range(1, length): temp = gList[i] # 当前的待插入的值 j = i - 1 # 前一个值 while j >= 0: if gList[j] > temp: gList[j+1] = gList[j] # 插入的动作 gList[j] = temp # 插入完毕 j -= 1 return gList
1.3.3 插入排序分析
- 时间复杂度
- 最好时间复杂度:O(n)
- 最坏时间复杂度: O(n2)
- 平均时间复杂度: O(n2)
- 空间复杂度:O(1)
- 稳定性: 稳定的排序
1.4 归并排序 ☆☆★
1.4.1 思想
利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思,即递归地将数组折半地分离为单个数组。
给定一组序列含 n 个元素,首先将每两个相邻的长度为 1 的子序列进行归并,得到 n/2(向上取整)个长度为 2 或 1 的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列为止。
1.4.2 实现
def merge_sort(gList: list) -> list: """归并排序 :param gList: 给定序列 :return: 升序排列后的集合 """ def merge(left: list, right: list) -> list: """merge left and right :param left: left list :param right: right list :return: merge reslut """ i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result if len(gList) <= 1: return gList num = len(gList) // 2 left = merge_sort(gList[:num]) right = merge_sort(gList[num:]) return merge(left, right) if __name__ == '__main__': gList = [3, 5, 2, 4, 1] print("----排序前:", gList) print("----归并排序后: ", merge_sort(gList))
1.4.3 归并排序分析
- 时间复杂度: 最好、最坏和平均情况O(nlogn)
- 空间复杂度:O(n)
- 稳定性: 稳定
题目:100 个有序数列如何合成一个大数组?
1.5 快速排序☆★★
1.5.1 思想
高效的排序算法,它采用**“分而治之”的思想,把大的拆分为小的,小的再拆分为更小的。其原理**是:对于一组给定的记录,通过一趟排序后,将原序列分为两部分,其中前部分的所有记录均比后部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。
1.5.2 实现
# -*- coding: utf-8 -*- def quick_sort(gList, left=0, right=None) -> list: """快速排序 :param gList: 给定一组序列 :param left: :param right: :return: 升序排序后的序列 """ if right is None: right = len(gList)-1 if left > right: return gList key = gList[left] low = left high = right while left < right: while left < right and gList[right] >= key: right -= 1 gList[left] = gList[right] while left < right and gList[left] <= key: left += 1 gList[right] = gList[left] gList[right] = key quick_sort(gList, low, left-1) quick_sort(gList, left+1, high) return gList if __name__ == '__main__': gList = [3, 5, 2, 4, 1, 6, 7] print("----排序前:", gList) print("----快速排序后: ", quick_sort(gList))
1.5.3 快速排序分析
- 时间复杂度:
- 最坏时间复杂度:O(n2)
- 最好时间复杂度:O(nlogn)
- 平均时间复杂度: O(nlogn)
- 空间复杂度:O(logn)
- 稳定性:不稳定
扩展:随机快排
1.6 希尔排序
1.6.1 思想
希尔排序也称为“缩小增量排序”。它的基本原理是:首先将待排序的元素分成多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分别进行直接插入排序,待整个待排序序列“基本有序后”,再对所有元素进行一次直接插入排序。
1.6.2 实现
# -*- coding: utf-8 -*- def shell_sort(gList) -> list: """希尔排序""" length = len(gList) step = 2 group = length // step while group > 0: for startPos in range(group): gap_insertion_sort(gList, startPos, group) group = group // 2 return gList def gap_insertion_sort(gList, start, gap): for i in range(start+gap, len(gList), gap): curr_value = gList[i] pos = i while pos >= gap and gList[pos-gap] > curr_value: gList[pos] = gList[pos-gap] pos = pos - gap gList[pos] = curr_value if __name__ == '__main__': gList = [5, 4, 2, 1, 7, 3, 6] print("-----yuzhou1su-----", gList) print("-----希尔排序后:", shell_sort(gList))
1.6.3 希尔排序分析
- 时间复杂度:
- 最好时间复杂度:O(n)
- 最坏时间复杂度:O(ns)(1<s<2)
- 平均时间复杂度:O(nlogn)
- 空间复杂度:O(1)
- 稳定性: 不稳定