IT评测·应用市场-qidao123.com

标题: python实现各种算法详解，以及时间复杂度 [打印本页]
作者: 刘俊凯    时间: 2023-4-6 15:45
标题: python实现各种算法详解，以及时间复杂度
python实现各种排序



1. 快速排序

1：首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。
2：从后向前扫描，找小于等于pivot的数，如果找到，R与R[j]交换，i++。
3：从前往后扫描，找大于pivot的数，如果找到，R与R[j]交换，j--。
4：重复2~3，直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后，以mid为界，将序列分为两部分，左序列都比pivot小，有序列都比pivot大，然后再分别对这两个子序列进行快速排序。
以序列（30，24，5，58，16，36，12，42，39）为例，进行演示：
1、初始化，i=low,j=high,pivot=R[low]=30：
ij302455816261241392、从后往前找小于等于pivot的数，找到R[j]=12
ij30245581626124139
ij122455816263041393、从前往后找大于pivot的数，找到R=58
ij12245581626304139

  • R与R[j]交换，j--
ij122453016265841394、从后往前找小于等于pivot的数，找到R[j]=16
ij12245301626584139

  • R与R[j]交换，i++
i,j12245163026584139
5、从前往后找大于pivot的数，这时i=j,第一轮排序结束，返回i的位置，mid=i
Lowmid-1midmid+1High1224516302658413此时已mid为界，将原序列一分为二，左子序列为（12，24，5，18）元素都比pivot小，右子序列为（36，58，42，39）元素都比pivot大。然后在分别对两个子序列进行快速排序，最后即可得到排序后的结果。
  1. def quicksort(low,high,li):
  2.     if low >= high:
  3.         return li
  4.     i = low
  5.     j= high
  6.     pivot = li[low]
  7.     while i<j:
  8.         while i<j and li[j]>pivot:
  9.             j -= 1
  10.         li[i] = li[j]
  11.         while i<j and li[i]<pivot:
  12.             i += 1
  13.         li[j] = li[i]
  15.     li[j] = pivot
  16.     quicksort(low,i-1,li)
  17.     quicksort(i+1,high,li)
  18.     return li
  22. lists=[30,24,5,58,18,36,12,42,39]
  23. print("排序前的序列为：")
  24. for i in lists:
  25.     print(i,end =" ")
  26. print("\n排序后的序列为：")
  27. for i in quicksort(0,len(lists)-1,lists):
  28.     print(i,end=" ")
复制代码
5. 归并排序

将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些问题，然后再合并其结果，就得到原问题的解。从上图看分解后的数列很像一个二叉树。
归并排序采用分而治之的原理：

  • 将一个序列从中间位置分成两个序列；
  • 在将这两个子序列按照第一步继续二分下去；
  • 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

[code]def merge(left,right):    r,l = 0,0    res = []    while r < len(right) and l < len(left):        if left[l] < right[r]:  # 排序，小于等于的放左边            res.append(left[l])            l += 1        else:            res.append(right[r])  # 排序，大的放右边            r += 1    res +=(left[l:])    res +=(right[r:])      return resdef mergesort(li):    if(len(li))



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4