排序算法

1.插入排序

(1)插入排序算法

时间复杂度为O(n^2)空间复杂度为O(1)是稳定的排序方法

思想：

数组内部的操作，选择的元素不断插入前面已经排好序的有序元素中。 def insert(L): for i in range(len(L)): for j in range(i,0,-1): if L[j]<L[j-1]: L[j-1],L[j]=L[j],L[j-1] print(L) return L

(2).折半插入排序

思想：

分别指向数列的第一位和末位，下标为low和highm = (low + high)/2如果要插入的数小于m位置的数，说明要在低半区查找，high = m - 1如果要插入的数大于m位置的数，说明要在高半区查找，low = m + 1如果要插入的数等于m位置的数，直接退出，high=m当low > high时，停止查找插入的位置为high+1

在有序数组中插入一个元素

def binaryinsert_a(l,a): low = 0 high = len(l) - 1 mid = (low + high) // 2 while low <= high: if l[mid] > a: high = mid - 1 elif l[mid] < a: low = mid + 1 else: high = mid mid = (low + high) // 2 l.insert(high + 1, a) return l

无序数组的排序

def binaryinsert(l,a): for i in range(len(l)): low=0 high=len(a)-1 mid=(low+high)//2 while low<=high: if a[mid]>l[i]: high=mid-1 elif a[mid]<l[i]: low=mid+1 else: high=mid mid=(low+high)//2 a.insert(high+1,l[i]) return a l=[3,1,2,5,6,7,9,4] a=[] a=binaryinsert(l,a) a_1=binaryinsert_a(sorted(l),8) print(a) print(a_1) [1, 2, 3, 4, 5, 6, 7, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9]

(3).希尔排序

传送门

希尔排序的思想建立在插入排序的想法上，加了一个想法就是加上按列排序。

时间复杂度为O(n^2)空间复杂度为O(1)是不稳定的排序方法 def shell_sort(L): shell=len(l)//2 while shell>=1: for i in range(shell,len(L)): j=i while j-shell>=0: if L[j] < L[j - shell]: L[j - shell], L[j] = L[j], L[j - shell] j=j-shell shell=shell//2 return L l=[3,1,2,5,6,7,9,4] shell=shell_sort(l) print(shell)

[1, 2, 3, 4, 5, 6, 7, 9]

2.交换类算法

(1).冒泡排序

每遍历一次就确定一个元素每比较一次就是两两互换 def bubble_sort(s): for i in range(len(s)-1): for j in range(len(s)-i-1): if s[j]>s[j+1]: s[j+1],s[j]=s[j],s[j+1] return s l=[3,1,2,5,6,7,9,4] bubble=bubble_sort(l) print(bubble)

(2).快速排序

思想：

定一个基准比基准大的放在右边，比基准小的放在左边从左边和右边中分别做前面两个操作直到长度为2返回，使用递归完成 def quick_sort(data): """quick_sort""" if len(data) >= 2: mid = data[0] left,right = [], [] data.remove(mid) for num in data: if num >= mid: right.append(num) else: left.append(num) return quick_sort(left) + [mid] + quick_sort(right) else: return data

3.选择排序

(1).直接选择排序

每一次从候选元素中选择出一个最小/大的值，直接插入该元素所在位置，交换元素 def select_sort(l): for i in range(len(l)): min=l[i] min_index=i for j in range(i,len(l)): if l[j]<min: min_index=j min=l[j] l[i],l[min_index]=l[min_index], l[i] return l

(2).堆排序

传送门来啦 写的超级好 大根堆：每个结点的值都大于或等于左右子结点 小根堆：每个结点的值都小于或等于左右子结点

时间复杂度：O(nlogn)空间复杂度： 因为堆排序是就地排序，空间复杂度为常数：O(1)

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中：

父节点i的左子节点在位置(2*i+1);父节点i的右子节点在位置(2*i+2);子节点i的父节点在位置(i-1)//2; 堆的操作过程： 大根堆调整(max_heapify)： 将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值，当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，同理，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。 def max_heapify(heap,heapSize,root): # 调整列表中的元素并保证以root为根的堆是一个大根堆 ''' 给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。 父节点：(root-1)//2 左子节点：2*root + 1 右子节点：2*root + 2 即：左子节点 + 1 ''' left = 2*root + 1 right = left + 1 larger = root if left < heapSize and heap[larger] < heap[left]: larger = left if right < heapSize and heap[larger] < heap[right]: larger = right if larger != root: # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作 heap[larger], heap[root] = heap[root], heap[larger] # 递归的对子树做调整 max_heapify(heap, heapSize, larger) 建立大根堆(build_max_heap)： 将堆中所有的数据重新排序。建堆的过程其实就是不断做大根堆调整的过程，从(heapSize-2)//2处开始调整，一直调整到第一个根节点。 def build_max_heap(heap): # 构造一个堆，将堆中所有数据重新排序 heapSize = len(heap) for i in range((heapSize -2)//2,-1,-1): # 自底向上建堆 max_heapify(heap, heapSize, i) 堆排序(heap_sort)： 将根节点取出与最后一位做对调，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。 首先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len(heap)-1个节点继续做堆调整，直到将所有的节点取出，对于有n个元素的一维数组我们只需要做n-1次操作。 import random def heap_sort(heap): # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。 build_max_heap(heap) # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆 for i in range(len(heap)-1, -1, -1): heap[0], heap[i] = heap[i], heap[0] max_heapify(heap, i, 0) # 测试 if __name__ == '__main__': a = [30, 50, 57, 77, 62, 78, 94, 80, 84] print(a) heap_sort(a) print(a) b = [random.randint(1,1000) for i in range(1000)] print(b) heap_sort(b) print(b)

我是小小搬运工~~

3.归并排序

最优时间复杂度：O(nlongn)最坏时间复杂度 ：O(nlongn)稳定性：稳定

归并排序思想：（合-分-合)

将一个序列从中间位置分成两个序列；. 在将这两个子序列按照第一步继续二分下去；直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。 def merge_sort(lists): ''' 递归进行归并排序。 ''' # 递归结束条件 if len(lists) <= 1: return lists ########合-分######### # 分治进行递归 middle = len(lists) // 2 left = merge_sort(lists[:middle]) right = merge_sort(lists[middle:]) ########分-合######## # 将两个有序数组进行合并 result = [] i = j = 0 while i < len(left) and j < len(right): # 将较小值放入到result中 if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # 将未被扫描到的直接追加到result后面 if i == len(left): result.extend(right[j:]) else: result.extend(left[i:]) return result if __name__ == '__main__': a = [2, 6, 10, 3, 5, 8, 4] print(merge_sort(a))

基数排序

太简单易懂了

(1).基数排序

根据位数排序： 需要10个桶，分别是从0-9：

先是按照个位数大小把元素有序的装进桶中从0-9个桶，一次收集数据先是按照十位数大小把元素有序的装进桶中重复过程 def RadixSort(a): i = 0 #初始为个位排序 n = 1 #最小的位数置为1（包含0） max_num = max(a) #得到带排序数组中最大数 while max_num >= 10**n: #得到最大数是几位数 n += 1 while i < n: bucket = {} #用字典构建桶 for x in range(10): bucket.setdefault(x, []) #将每个桶置空 for x in a: #对每一位进行排序 radix =int((x / (10**i)) % 10) #得到每位的基数 bucket[radix].append(x) #将对应的数组元素加入到相应位基数的桶中 j = 0 for k in range(10): if len(bucket[k]) != 0: #若桶不为空 for y in bucket[k]: #将该桶中每个元素 a[j] = y #放回到数组中 j += 1 i += 1 if __name__ == '__main__': a = [12,3,45,3543,214,1,4553] RadixSort(a) print(a)

(2).多关键字排序

多关键字排序就是根据多个关键字的重要性排序。在python排序时需要利用sort和sorted两个内置函数完成。

sort()方法

直接改变数组的值返回Nonereverse：True，False（默认升序）

sorted()方法

返回为排序后的数组reverse：True，False（默认升序）利用key进行多关键字排序

单关键字排序

l=[2,1,3,5,4,8,7,9] l.sort(reverse=True) l2=sorted(l,reverse=True) print(l) print(l2)

多关键字排序

students = [ ('john', 'A', 18), ('jane', 'B', 19), ('dave', 'B', 17) ] print(sorted(students, key=lambda s: s[0])) [('dave', 'B', 17), ('jane', 'B', 19), ('john', 'A', 18)] L = [ ('摩洛哥', 2, 2, 0, 1), ('葡萄牙', 5, 4, 1, 5), ('西班牙', 6, 5, 1, 5), ('伊朗', 2, 2, 0, 4) ] L = sorted(L, key=lambda t: t[1],reverse=True) # 积分数 print(L) L = sorted(L, key=lambda t: t[3], reverse=True) # 净胜球数 print(L) L = sorted(L, key=lambda t: t[4], reverse=True) # 进球数 print(L) [('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('摩洛哥', 2, 2, 0, 1), ('伊朗', 2, 2, 0, 4)] [('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('摩洛哥', 2, 2, 0, 1), ('伊朗', 2, 2, 0, 4)] [('西班牙', 6, 5, 1, 5), ('葡萄牙', 5, 4, 1, 5), ('伊朗', 2, 2, 0, 4), ('摩洛哥', 2, 2, 0, 1)]

两个关键字排序：正序

arr=[(1,4,3),(1,3,3),(2,1,4),(3,5,1)] arr.sort(key=lambda s:(s[0],s[1])) #两个关键字排序 print(arr) # 可以看到输出结果是根据列表中元组的第一项和第二项排序

第一个关键字正序，第二个关键字倒序

arr=[(1,4,3),(1,3,3),(2,1,4),(3,5,1)] arr.sort(key=lambda s:(s[0],-s[1])) #两个关键字排序,在需要倒序排列的关键字前加`-`号 print(arr)