代码实现
########################################################## # 1、冒泡排序 # 每次将相邻两个数值进行对比，数值大的数字向后移； # 一轮遍历下来可以保证最后的数字为最大值，重复 def bubbleSort(nums): for i in range(len(nums) - 1): for j in range(len(nums) - i - 1): # 后i+1个数字已经排好序 if nums[j] > nums[j + 1]: nums[j], nums[j + 1] = nums[j + 1], nums[j] # 更大值放后面 return nums ########################################################## # 2、选择排序 # 选择最小的数据放在最前面 def selectSort(nums): for i in range(len(nums) - 1): min_n = i # 记录当前坐标 for j in range(i + 1, len(nums)): if nums[j] < nums[i]: min_n = j # 更新更小值的坐标 nums[min_n], nums[i] = nums[i], nums[min_n] # 更新相应位置的数值 return nums ########################################################## # 3、插入排序 # 逐个插入到前面的有序数组中，即前n个数已经是有序数组，然后倒叙进行数值大小对比 def insertSort(nums): for i in range(1, len(nums)): j = i - 1 key = nums[i] # 记录当前需要对比的数值 while j >= 0: # 对比前j个数值，确定当前数值应该插入到哪个位置，保持num[:j]有序 if nums[j] > key: nums[j + 1], nums[j] = nums[j], key j -= 1 return nums ########################################################## # 4、希尔排序 # 从大范围到小范围进行比较-交换 # 例如：len(nums)==8，首次对比将0&4、1&5...对比； # 再次对比是将0&2&4&6进行对比；再次将0&1&2&3...对比 def direct_insertion_sort(d): # 每次排序特定数组 d1 = [d[0]] for i in d[1:]: state = 1 for j in range(len(d1) - 1, -1, -1): # 已对比数据的倒叙 if i >= d1[j]: d1.insert(j + 1, i) # 将元素插入数组 state = 0 break if state: d1.insert(0, i) # 最小值插入最前方 return d1 def shell_sort(d): length = len(d) // 2 # 初始值-间隔长度 num = len(d) // length # 初始值-单次对比数组的长度 while 1: for i in range(length): d_mid = [] for j in range(num): d_mid.append(d[i + j * length]) # 将相同间隔的数组成数组 d_mid = direct_insertion_sort(d_mid) # 返回d_mid排序后结果 for j in range(num): d[i + j * length] = d_mid[j] # 将排序后数组重新插入原数组 length = length // 2 # 更新length if length == 0: break num = len(d) // length # 更新num return d ########################################################## # 归并排序 # 分治法，2-4-8插入排序，DFS实现 class MergeSort: def merge_sort(self, nums): mid = len(nums) // 2 # 取中值 nums0 = nums[:mid] nums1 = nums[mid:] # 判断是否排序 if len(nums0) > 1: nums0 = self.merge_sort(nums0) if len(nums1) > 1: nums1 = self.merge_sort(nums1) index = 0 # 插入排序，将两个数组进行合并的过程 for i in range(len(nums1)): state = 1 for j in range(index, len(nums0)): if nums1[i] < nums0[j]: state = 0 index = j + 1 nums0.insert(j, nums1[i]) break if state == 1: nums0.extend(nums1[i:]) break return nums0 if __name__ == '__main__': M = MergeSort() # 原始乱序 d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 正确排序 d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] d1 = M.merge_sort(d0) print(d1) print(d0_out) ########################################################## # 快速排序 # 选取一个基准值，小数在左大数在右 def quick_sort(data): d = [[], [], []] d_pivot = data[-1] # 依次与基准值进行对比 for i in data: if i < d_pivot: d[0].append(i) elif i > d_pivot: d[2].append(i) else: d[1].append(i) if len(d[0]) > 1: d[0] = quick_sort(d[0]) if len(d[2]) > 1: d[2] = quick_sort(d[2]) d[0].extend(d[1]) d[0].extend(d[2]) return d[0] # 堆排序 # 见最小堆实现 # 计数排序 # 字典计数进行排序 # 空间换时间 ########################################################## # 桶排序 # 链表实现 d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] d1 = [[] for x in range(10)] # 十位对应的数值 for i in d0: d1[i // 10].append(i) # 各位对应的数值 for i in range(len(d1)): if d1[i] is not None: d2 = [[] for x in range(10)] for j in d1[i]: d2[j % 10].append(j) d1[i] = d2 # 基数排序 # 最小为排序 >> 次低位排序... # %10 >> //10 >> //100...进行对比排序组成新的数组
参考
注：参考链接中有很直观的动图！！