赞
踩
如有错误,欢迎指出,多谢。
动图来自菜鸟教程,多谢。
一:堆排序
堆排序相对来说有些难度,这里给个链接,老师讲的很详细,C语言版的:
https://www.bilibili.com/video/av47196993
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆(大顶堆)
- 了解一下堆排序的大概流程:
- 1,我们给定一个数组,将数据依次放入堆节点中,它们的下标不变,上到下,左到右依次为0,1.....,
- 将父节点和子节点比较,最大的成为新的父节点,这个过程称之为heapify
- 2,我们使它在数据上也满足大顶堆的概念。从堆的倒数第二行向上遍历,比较每一个节点和它的的子节点,
- 使最大的变成新的父节点,我们发现,每完全执行一次,就会有一个最大数被换到堆顶,
- 这个过程称之为build_heap
- 3,我们将堆顶的最大数和堆的最后一个数交换,交换后,最大数位于堆的最底部,最右端,砍掉这个数不会影响堆的结构,
- 但我们就获得了最大数,这个就是heap_sort
- import random
- #该方法用于在父节点和子节点中找到最大值,将最大值变成父节点
- def heapify(arr,n,i):
- #递归出口
- # if i >= n:
- # return
- #左节点,右节点的下标
- left_index = 2*i+1
- right_index = 2*i+2
- #设父节点的下标为最大值的下标
- max_index = i
- #在下标未越界的条件下判断值是否大于父节点的值
- if left_index<n and arr[left_index]>arr[max_index]:
- max_index = left_index
- if right_index<n and arr[right_index]>arr[max_index]:
- max_index = right_index
- #如果max_index不等于i说明最大值不是父节点,交换
- if max_index != i:
- arr[max_index],arr[i] = arr[i],arr[max_index]
- #递归执行,自带出口
- heapify(arr,n,max_index)
- # print(max_index)
-
- #该方法用于建堆
- def build_heap(arr,n):
- #获取最后一个节点的下标
- last_index = n - 1
- #获取最后一个节点的父节点
- p_index = (last_index-1)//2
- #从最后一个父节点向前遍历节点,进行heapify
- i = p_index
- while i >= 0:
- heapify(arr,n,i)
- # print(arr)
- i = i - 1
-
- def heapsort(arr,n):
- build_heap(arr,n)
- i = n-1
- #从最后一个节点开始
- while i >= 0:
- #交换堆顶和堆尾的值,最大值在堆尾,堆的长度递减就不会再次比较堆尾的值
- # 即相当于去掉了堆尾
- arr[i],arr[0]=arr[0],arr[i]
- #交换完后继续进行heapify
- heapify(arr,i,0)
- i -= 1
-
- if __name__ == '__main__':
- arr = []
- x = random.randint(2,20)
- for i in range(0,x):
- arr.append(random.randint(1,1000))
- print("排序前:",arr)
- heapsort(arr,len(arr))
- # build_heap(arr,len(arr))
- # arr = [4,10,3,5,1,2]
- # heapify(arr,len(arr),0)
- print("排序后:",arr)
二:快速排序:
简单快排(即刻手写版)
缺点:需要额外申请空间
- import random
- def qsort_simple(arr):
- #递归出口
- if len(arr) < 2:
- return arr
- else:
- #取第一个为主元
- pivot_index = 0
- pivot = arr[pivot_index]
- #小于主元的放在左边,大于主元的放在右边,给两个数组
- left_arr = []
- right_arr = []
- for i in arr[pivot_index+1:]:
- if i > pivot:
- right_arr.append(i)
- else:
- left_arr.append(i)
- #调用递归,合并结果
- return qsort_simple(left_arr) + [pivot] + qsort_simple(right_arr)
-
- if __name__ == '__main__':
- arr = []
- x = random.randint(2,20)
- for i in range(0,x):
- arr.append(random.randint(1,1000))
- print("排序前:",arr)
- print("排序后:",qsort_simple(arr))
真正意义的快排:
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]的值交换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
- import random
- # #定义partition函数,参数数组,起始值,结尾值
- def partition(arr,beg,end):
- #主元下标取起始值
- pivot_index = beg
- pivot = arr[pivot_index]
- #获取指针,左指针为主元下标后一个,右指针最后一个
- left = pivot_index + 1
- right = end - 1
- while True:
- #当左指针小于等于右指针,且指针指向的数小于主元,指针右移
- while left <= right and arr[left] < pivot:
- left += 1
- #当右指针大于等于左指针,且指针指向的数大于等于主元,指针左移
- while right >= left and arr[right] >= pivot:
- right -= 1
- #退出条件,当左指针大于右指针,break
- if left > right:
- break
- #不满足条件且不满足退出时,交换值
- else:
- arr[left],arr[right] = arr[right],arr[left]
- #退出代表:此时的右指针在左指针的左侧,指向最小数,因此,需要将主元与right指向的数进行交换
- arr[pivot_index],arr[right] = arr[right],arr[pivot_index]
- #此时,主元的位置与right进行了交换,我们返回主元位置即返回right
- return right
-
- def qsort_partition(arr,beg,end):
- #递归出口
- if beg < end:
- #找到主元位置
- pivod = partition(arr,beg,end)
- #左右操作
- qsort_partition(arr,beg,pivod)
- qsort_partition(arr,pivod+1,end)
-
- if __name__ == '__main__':
- arr = []
- x = random.randint(2,20)
- for i in range(0,x):
- arr.append(random.randint(1,1000))
- print("排序前:",arr)
- qsort_partition(arr,0,len(arr))
- print("排序后:",arr)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。