记录python几个算法的实例分析

记录python几个算法的实例分析，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

（一）插入排序

插入排序原址排序输入的数，算法在数组A中重排这些数，

在任何时候，最多只有常数个数字存储在数组外部。

插入排序是原地排序，基本无需外部空间。

从第二个元素开始，依次遍历全部数组。

其中，前半截为已排好的有序数组而后半截为待排序的无序数组。

每个元素从后向前依次对比，直到找到自己的位置。

插入排序是稳定排序。

def insert_sort(list1):
for j in range(1,len(list1)): # 从第二个元素开始遍历，依次将元素放在指定位置
key = list1[j] #记录当前值
i = j -1 #将当前值从当前位置之前逆序依次比较
while i>=0 and list1[i] >key:#如果当前值小于之前值，则说明当前值位于之前值的前面
list1[i+1] = list1[i] #将大于当前值的元素依次后移一位，给当前值留位置
i -=1
list1[i+1] = key # 将当前值插入第一个小于它的值的后面
return list1

if __name__ == "__main__":
list1 = [380,22,64,75,327,98]
list2 = ["wang","zhe","tian","jin","da","xue"]
ordered_list1 = insert_sort(list1)
ordered_list2 = insert_sort(list2)
print(ordered_list1) #[2,3,4,5,6,7]
print(ordered_list2) #['da']

（2）冒泡排序

冒泡排序原址排序输入的数，算法在数组A中重排这些数，

在任何时候，最多只有常数个数字存储在数组外部。

冒泡排序是原地排序，基本无需外部空间。

冒泡排序依次循环数组，每轮循环从前向后依次比较两个元素，排列使得后一个元素总是大于前一个元素。

因此，每轮循环可以保证当前未排序的列表中最大的元素放置在列表末尾。

即每轮循环后，可以使得未排序的列表长度减1。

重复直到列表仅剩唯一一个元素。

冒泡排序是稳定排序。

Python实现代码如下：

1. # -*- coding: utf-8 -*-
   def bubbleSort(bubbleList):
   listLength = len(bubbleList) #计算排序列表的长度
   while listLength > 0:
   for i in range(listLength - 1):
   if bubbleList[i] > bubbleList[i+1]:
   temp = bubbleList[i+1]
   bubbleList[i+1] = bubbleList[i]
   bubbleList[i] = temp #交换bubbleList[i]与bubbleList[i+1]的值
   listLength -= 1 #每轮排序结束后，最后一个元素已经是最大的。因此只需要排前N-1个元素即可。
   return bubbleList
   
   if __name__ == '__main__':
   list1 = [3,2,4,6,7,5]
   list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
   ordered_list1 = bubbleSort(list1)
   ordered_list2 = bubbleSort(list2)
   print(ordered_list1) #[2, 3, 4, 5, 6, 7]
   print(ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
   

（3）

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

归并排序是通过递归和合并来实现的。

即首先将一个列表分为两个字列表，字列表长度为1。然后在依次合并，使得合成的列表有序。

归并排序的时间复杂度是nlogn。空间复杂度是n。

归并排序是稳定排序。

Python的实现代码如下：

# -*- coding: utf-8 -*-
def mergeSort(lists):
if len(lists) <= 1: #当数组长度为1时，则无需排序。
return lists
num = int(len(lists) / 2) #将一个数组分为两个部分
left = mergeSort(lists[:num]) #分别对左右两个部分进行排序
right = mergeSort(lists[num:])
return merge(left, right) #将左右两个有序数组合并为一个有序数组

def merge(left, right):
r, l = 0, 0 #初始化左右索引为0
result = [] #初始化结果列表
while l < len(left) and r < len(right): #当左右索引都尚未达到列表长度时。
if left[l] < right[r]: #如果左列表的值小于右列表的值
result.append(left[l]) #将左列表当前值存入结果列表中
l += 1 #左列表索引加1
else:
result.append(right[r]) #否则将右列表当前值存入结果列表中
r += 1 #右列表索引加1
result += right[r:] #将剩余元素存入结果列表中
result += left[l:]
return result

if __name__ == '__main__':
list1 = [3,2,4,6,7,5]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = mergeSort(list1)
ordered_list2 = mergeSort(list2)
print (ordered_list1) #[2, 3, 4, 5, 6, 7]
print (ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']

（4）

快速排序是指：

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

快速排序在平均情况下时间复杂度为nlogn。

但是在最坏情况（本身为正序或者逆序时），时间复杂度为n*n。

快速排序是不稳定排序。即对于本身值相同的元素，在经过快速排序后，元素的先后位置可能会发生变化。

一趟快速排序的算法是：

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-完成的时候，此时令循环结束）。

Python的实现方式如下：

# -*- coding: utf-8 -*-
def quickSortFunction(L, low, high):
i = low #i表示被排序列表的起点
j = high #j表示被排序列表的终点
if i >= j: #若当起点和终点重合或起点在终点后时，则无需进一步排序
return L
key = L[i] #将起点元素选为被对比元素
while i < j: #当起点与终点尚未重合时
while i < j and L[j] >= key: #找到第一个小于key的元素的位置
j -= 1
L[i] = L[j] #将第一个小于key元素的值放入key元素的位置
while i < j and L[i] <= key: #找到第一个大于key元素值，放入刚才小于key元素的位置
i += 1
L[j] = L[i]
L[i] = key #当i和j重合时，将key元素放置在重合位置。表示该位置前的元素都小于该元素，而该位置后的元素都大于该元素。
quickSortFunction(L, low, i-1) #利用归并的方法继续对low到i-1和j+1到high的部分进行排序
quickSortFunction(L, j+1, high)
return L

def quickSort(list1): #调用quickSortFunction进行快速排序
return quickSortFunction(list1, 0, len(list1)-1) #low和high分别为0和len-1，表示对列表整体进行快速排序

if __name__ == '__main__':
list1 = [3,2,4,6,7,5,1,8,10,9]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = quickSort(list1)
ordered_list2 = quickSort(list2)
print (ordered_list1) #[2, 3, 4, 5, 6, 7]
print (ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']


（5）堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆排序首先将待排序的数组存入堆中，并将堆构造为最大/最小堆。再依次从堆中取出堆顶元素，从而得到有序数组。

构造堆时，所用的方法为从最底层有子节点的节点开始依次向上处理。

取出顶元素恢复堆时则是先将末尾元素与顶元素交换位置，在对顶元素进行下沉处理即可。

堆排序是不稳定排序。即相同的元素再经过堆排序后，其先后位置可能发生变化。

堆排序的时间复杂度为N*logN。

Python的代码实现如下：

[python] view plain copy

1. # -*- coding: utf-8 -*-

2. #用列表表示一个堆，其中列表中索引为0的位置为空。从索引1开始存放元素。

3. def parent(i): #在堆中，某个节点的父节点为其索引值整除2。例如索引为4的父节点的索引为2。索引为9的父节点的索引为4。

4. return i/2

5. def left(i): #某个节点的左子节点的索引为i*2

6. return i*2

7. def right(i): #某个节点的右子节点的索引为i*2+1

8. return i*2+1

9. class Heap: #堆的数据结构类

10. def __init__(self, heapList=[None]): #对堆进行初始化。没有给堆初始列表时，初始化为仅包含一个None元素的列表。

11. self.heapList = [None] + heapList #有初始化列表时，堆列表为初始化列表前插入None元素

12. def max_heapfy(self, i): #表明对i节点进行最大堆恢复

13. if (i*2) > self.length-1: #该元素没有子节点时

14. maxIndex = i

15. elif (i*2+1) > self.length-1: #该元素只有左节点时

16. maxIndex = left(i)

17. elif self.heapList[left(i)] > self.heapList[right(i)]: #该元素同时有左右节点，且左节点的值大于右节点时

18. maxIndex = left(i)

19. else: #该元素同时有左右节点，且左节点的值小于右节点时

20. maxIndex = right(i)

21. if self.heapList[i] < self.heapList[maxIndex]: #当其子节点值大于其节点值时：

22. self.heapList[i], self.heapList[maxIndex] = self.heapList[maxIndex], self.heapList[i]

23. #交换其子节点的值和其值

24. self.max_heapfy(maxIndex) #并对其子节点进行最大堆化

25. def build_max_heap(self): #构建最大堆

26. self.length = len(self.heapList) #计算堆的大小（包含第一个空元素）

27. for i in range(self.length/2, 0, -1): #从包含子节点的节点开始依次向上遍历

28. self.max_heapfy(i)

29. def insert(self, k): #向堆内插入元素

30. self.length += 1 #堆的规模加1

31. self.heapList.append(float("-inf")) #向堆内插入一个负无穷的数

32. self.increase_key(self.length, k) #增加元素

33. def maxinum(self): #查询堆内最大元素，即为索引为1的元素值。

34. return self.heapList[1]

35. def extract_max(self): #弹出堆内最大元素。

36. maxValue = self.heapList[1] #取得最大元素值

37. self.heapList[1] = self.heapList[self.length] #将末尾元素移至堆头

38. del self.heapList[self.length] #删除末尾元素

39. self.length -= 1 #将堆的规模减1

40. self.max_heapfy(1) #对堆顶元素最大堆化

41. return maxValue

42. def increase_key(self, x, k): #增加元素

43. self.heapList[x] = k #将新增的负无穷位置赋予插入值

44. while x > 1 and self.heapList[parent(x)] < self.heapList[x]: #当元素索引大于1且其值大于其父节点值

45. self.heapList[parent(x)], self.heapList[x] = self.heapList[x], self.heapList[parent(x)]

46. #交换其值和其父节点的值

47. x = parent(x) #继续对其父节点进行判断

48. def show(self): #展示堆

49. print "the length of queue is", self.length - 1

50. print "the heapList is", self.heapList[1:]

51. def heapSort(unsortedList):

52. heap = Heap(unsortedList) #将乱序列表转换为堆

53. heap.build_max_heap() #将堆构建为最大堆

54. print heap.heapList

55. print "*************heap has been build up*********"

56. for i in range(len(unsortedList), 1, -1):

57. heap.heapList[i], heap.heapList[1] = heap.heapList[1], heap.heapList[i] #将末尾节点与根节点进行交换，

58. #交换完成后，i位置的节点为当前堆中最大的元素。即每次循环中得到的i索引的元素为已有序的列表。

59. heap.length -= 1 #未排序的堆的规模减小1

60. heap.max_heapfy(1) #此时，根节点不满足最大堆的要求，需要对堆进行最大堆恢复

61. return heap.heapList[1:]

62. if __name__ == '__main__':

63. list1 = [3,2,4,6,7,5,1,8,10,9]

64. list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]

65. ordered_list1 = heapSort(list1)

66. ordered_list2 = heapSort(list2)

67. print ordered_list1 #[2, 3, 4, 5, 6, 7]

68. print ordered_list2 #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
    

看完上述内容，你们掌握记录python几个算法的实例分析的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注行业资讯频道，感谢各位的阅读！