算法|用Python 实现的九种排序算法 python|排序算法|python

用Python 实现的九种排序算法

用Python 实现的九种排序算法

冒泡排序

直接插入排序

希尔排序

选择排序

堆排序

快速排序

归并排序

计数排序

基数排序

冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这3.一点，最后的元素应该会是最大的数。
4.针对所有的元素重复以上的步骤，除了最后一个。
5.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(nums): count = len(nums) for i in range(0, count): for j in range(i + 1, count): if nums[i] > nums[j]: nums[i],nums[j] = nums[j],nums[i]

可优化部分：设置一个flag，在某次循环未曾交换元素，则可以停止整个大循环
直接插入排序

⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5

def insert_sort(nums): for i in range(1,len(nums)): save = nums[i] j = i while j > 0 and nums[j - 1] > save:#找到新插入数据应处的位置 nums[j] = nums[j - 1] j -= 1 nums[j] = save

希尔排序

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

def shell_sort(nums): nums_len = len(nums) gap = nums_len / 2 # 增量 while gap > 0: for i in range(nums_len): m = i j = i + 1 while j < nums_len: if nums[j] < nums[m]: m = j j += gap if m != i: nums[m],nums[i] =nums[i],nums[m] gap /= 2

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置，直到全部待排序的数据元素排完。

def select_sort(nums): for i in range(len(nums)): min_index = i for j in range(i + 1, len(nums)): if nums[min_index] > nums[j]: min_index = j nums[i],nums[min_index] = nums[min_index],nums[i]

堆排序

好麻烦

#数组编号从0开始 def left(i): return 2 * i + 1def right(i): return 2 * i + 2#保持最大堆性质是以i为根的子树成为最大堆 def max_heapify(nums, i ,heap_size): if heap_size <= 0: return l = left(i) r = right(i); largest = i #选出子节点中较大的节点 ifl < len(nums) and nums[l] > nums[largest]: largest = l; ifr < len(nums) and nums[r] > nums[largest]: largest = r if i != largest: #说明当前节点不是最大的，下移 nums[i],nums[largest] = nums[largest],nums[i] max_heapify(nums,largest,heap_size) #建堆 def build_max_heap(nums): heap_size = len(nums) if heap_size > 1 : node = heap_size / 2 - 1 while node >= 0 : max_heapify(nums, node, heap_size) node -= 1# 堆排序下标从0开始，结果顺序为从大到小 def heap_sort(nums): build_max_heap(nums) heap_size = len(nums) i = heap_size - 1 while i > 0: nums[0],nums[i] = nums[i],nums[0] # 对中的最大值存入数组适当的位置，并且进行交换 heap_size -= 1# heap 大小递减1 i -= 1# 存放堆中最大值的下标递减 1 max_heapify(nums,0,heap_size)

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

def quick_sort(nums,left,right): if left >= right: return key = nums[left] low = left high = right while left < right: while left < right and nums[right] >= key: right -= 1 nums[left] = nums[right] while left < right and nums[left] <= key: left += 1 nums[right] = nums[left] nums[right] = key quick_sort(nums,low,left - 1) quick_sort(nums,left + 1, high)

归并排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

def quick_sort(nums,left,right): if left >= right: return key = nums[left] low = left high = right while left < right: while left < right and nums[right] >= key: right -= 1 nums[left] = nums[right] while left < right and nums[left] <= key: left += 1 nums[right] = nums[left] nums[right] = key quick_sort(nums,low,left - 1) quick_sort(nums,left + 1, high)

计数排序

只能排正整数

import math import sysdef count_sort(nums): min = sys.maxint max = 0 # 取得最大值和最小值 for x in nums: if x > max: max = x if x < min: min = x # 创建数组C count = [0] * (max - min +1) for index in nums: count[index - min] += 1 index = 0 # 填值 for a in range(max - min+1): for c in range(count[a]): nums[index] = a + min index += 1

基数排序

【算法|用Python 实现的九种排序算法】只能排正整数

import sys import math def radix_sort(a, radix=10): """a为整数列表， radix为基数""" K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数 bucket = [[] for i in range(radix)] # 不能用 [[]]*radix for i in range(1, K+1): # K次循环 for val in a: bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字（从低到高） del a[:] for each in bucket: a.extend(each) # 桶合并 bucket = [[] for i in range(radix)]