【数据结构和算法】排序算法

使用swap函数来交换列表中的两项的位置

1 def swap(lyst,i,j):
2     '''交换列表中两项的位置'''
3     temp = lyst[i]
4     lyst[i] = lyst[j]
5     lyst[j] = temp

① 选择排序

处于列表第一项，先找到最小项的位置，如果该位置不是列表的第一项，算法会交换这两个位置的项，然后算法回到第二项并重复上述过程，如果第二项比最小值要大，则交换位置，当算法到列表最后的位置时，列表排序好了

 1 def swap(lyst,i,j):
 2     '''交换列表中两项的位置'''
 3     temp = lyst[i]
 4     lyst[i] = lyst[j]
 5     lyst[j] = temp
 6 
 7 def selectionSort(lyst):
 8     i = 0
 9     while i < len(lyst): #Do n -1 searches
10         minIndex = i     #for the smallest
11         j = i + 1
12         while j < len(lyst):  #start a search
13             if lyst[j] < lyst[minIndex]:
14                 minIndex = j
15             j = j + 1
16         if minIndex != i:
17             swap(lyst,minIndex,i)
18 
19         i += 1

② 冒泡排序

从列表得开头处开始，比较相邻两项，每当左边的比右边的时，算法就交换其位置，这样效果就将最大项以冒泡的方式排到列表末尾，然后算法从列表开头到倒数第二项重复上述过程。

 1 def swap(lyst,i,j):
 2     '''交换列表中两项的位置'''
 3     temp = lyst[i]
 4     lyst[i] = lyst[j]
 5     lyst[j] = temp
 6 
 7 def bubbleSort(lyst):
 8     n = len(lyst):
 9     while n > 1:      #Do n-1 bubble
10         i = 1         #start each bubble    
11         while i < n :
12             if lyst[i] < lyst[i-1]: #exchange if needed
13                 swap(lyst,i,i-1)
14             i += 1
15         n -= 1

在最好的情况下，第一轮发生已经排序好了

 1 def swap(lyst,i,j):
 2     '''交换列表中两项的位置'''
 3     temp = lyst[i]
 4     lyst[i] = lyst[j]
 5     lyst[j] = temp
 6 
 7 def bubbleSort(lyst):
 8     n = len(lyst):
 9     while n > 1:      #Do n-1 bubble
10     swapped = False
11         i = 1         #start each bubble    
12         while i < n :
13             if lyst[i] < lyst[i-1]: #exchange if needed
14                 swap(lyst,i,i-1)
15                 swapped = True
16             i += 1
17         if not swapped:return   #return if no swaps
18         n -= 1 

③ 插入排序

类似扑克牌的顺序，如果按照顺序放好了i-1张牌，对于抓取第i张牌，将其手中的这些牌进行比较，知道找到合适的位置

第i轮之后，前i项应该是排好序的

 1 def insertionSort(lyst):
 2     i = 1
 3     while i < len(lyst):
 4         itemToInsert = lyst[i]
 5         j = i - 1
 6         while j >= 0:
 7             if itemToInsert < lyst[j]:
 8                 lyst[j + 1] = lyst[j]
 9                 j -= 1
10             else:
11                 break
12         lyst[j + 1] = itemToInsert
13         i += 1

 阶段总结：

1.冒泡排序在最好情况下（列表已经排好序）性能为O(n)，在最好的情况下是O(n^2)，平均情况下性能更接近于O(n^2)

2.插入排序在最好情况下（列表有序）性能为O(n)，最坏情况下复杂度为O(n^2)，平均情况下也是O(n^2)

3.选择排序在各种情况下的排序都为O(n^2)

④ 快速排序

1.找到基准点，将大于基准点的项放在一个子列表，小于基准点的项放在一个子列表

2.对上述子列表重复上述过程

在最坏的情况下，快速排序算法的性能是O(n^2)  -->>>>>每一次基准值都取第一个

一般请款修改，快速排序算法的性能是O(nlog2^n) ->>>>>>>每一次都从中间取基准值

每次递归调用都需要固定大小的内存用于栈，并且在每一次分割之后都有两次递归调用，因此在最好的情况下，内存使用是O(log2^n)，最坏的情况下，内存是O(n)

实现：

 1 def swap(lyst,i,j):
 2     '''交换列表中两项的位置'''
 3     temp = lyst[i]
 4     lyst[i] = lyst[j]
 5     lyst[j] = temp
 6 
 7 def quicksort(lyst):
 8     quicksortHelper(lyst, 0, len(lyst) - 1)
 9 
10 def quicksortHelper(lyst, left, right):
11     if left < right:
12         pivotLocation = partition(lyst, left, right)
13         quicksortHelper(lyst, left, pivotLocation - 1)
14         quicksortHelper(lyst, pivotLocation + 1, right)
15 
16 def partition(lyst, left, right):
17     # 找到基准值，并与最后一项进行交换
18     middle = (left + right) // 2
19     pivot = lyst[middle]
20     lyst[middle] = lyst[right]
21     lyst[right] = pivot
22     # 将最左边的点设置边界
23     boundary = left
24     # 将小于基准值的项移到边界的左边
25     for index in range(left,right):
26         if lyst[index] < pivot:
27             swap(lyst, index, boundary)
28             boundary += 1
29     # 将边界点与基准值点进行交换
30     swap(lyst, right, boundary)
31     return boundary
32 
33 import random
34 
35 def main(size=20, sort=quicksort):
36     lyst = []
37     for count in range(size):
38         while len(lyst) < 20:
39             num = random.randint(1,size + 1)
40             if num not in lyst:
41                 lyst.append(num)
42     print(lyst)
43     sort(lyst)
44     print(lyst)
45 
46 if __name__ == '__main__':
47     main()

④ 合并排序

合并排序利用了递归，分而治之的策略来突破O（n^2）的障碍

 1 import random
 2 import array
 3 
 4 def mergeSort(lyst):
 5     copyBuffer = array.array('b')
 6     mergeSortHelper(lyst, copyBuffer, 0, len(lyst) - 1)
 7 
 8 def mergeSortHelper(lyst, copyBuffer, low, high):
 9     if low < high:
10         middle = (low + high) // 2
11         mergeSortHelper(lyst, copyBuffer, low, middle)
12         mergeSortHelper(lyst, copyBuffer, middle + 1, high)
13         merge(lyst, copyBuffer, low, middle, high)
14 
15 def merge(lyst, copyBuffer, low, middle, high):
16     i1 = low
17     i2 = middle + 1
18 
19     for i in range(low, high + 1):
20         if i1 > middle:
21             copyBuffer[i] = lyst[i2]  #first sublist exhaust
22             i2 += 1
23         elif i2 > high:
24             copyBuffer[i] = lyst[i1]  #second sublist exhaust
25             i1 += 1
26         elif lyst[i1] < lyst[i2]:
27             copyBuffer[i] = lyst[i1]  # item in first sublist
28             i1 += 1
29         elif lyst[i1] > lyst[i2]:
30             copyBuffer[i] = lyst[i2]     #item in second sublist
31             i2 += 1
32         else:
33             pass
34 
35     for i in range(low, high + 1):    #copy sorted items to lyst
36         lyst[i] = copyBuffer[i]
37 
38 def main(size=10, sort=mergeSort):
39     lyst = []
40     for count in range(size):
41         while len(lyst) < 8:
42             num = random.randint(1, size + 1)
43             if num not in lyst:
44                 lyst.append(num)
45     print(lyst)
46     mergeSort(lyst)
47     print(lyst)
48 
49 if __name__ == '__main__':
50     main()

根据列表的大小，合并排序有两个空间需求，首先是在支持递归调用的调用栈上需要O(log2^n)，其次在复制缓存需要使用O(n)的空间

因此合并排序算法的复杂度为O(nlog2^n)