Python实现排序：插入排序、希尔排序、选择排序、快速排序、交换排序、堆排序、归并排序_分别用递归和非递归实现选择排序、插入排序和交换排序 没有任务详情

算法复杂度及稳定性比较

排序算法的稳定性

  若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。

算法稳定的好处：

• 排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用；
• 可以避免多余的比较。
  

---

1. 插入排序

  插入排序基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录插入完成为止。

1.1 直接插入排序

  假设待排序的记录存放在数组arr中，排序过程的某一中间时刻，arr被划分成两个子区间[R[1],R[i-1]]和[R[i],R[n-1]]，其中前一个子区间是已排好序的有序区，后一个子区间则是当前未排好序的部分，即无序区。直接插入排序的基本操作就是将当前无序区的第1个记录插入到有序区中适当位置，保证有序区有序。

特点：

• 稳定；
• 第n趟排序后，前n+1个元素是有序的；
• 最坏情况下比较n*(n-1)/2次，最好情况下比较n-1次。

def insertionSort(arr):
	n=len(arr)
	for i in range(1,n):# 依次将arr[i]插入有序区
		key=arr[i]
		while arr[i-1]>key:# 边比较边交换
			arr[i]=arr[i-1]
			i-=1
			if i==0:
 				break
 		arr[i]=key	
1
2
3
4
5
6
7
8
9
10

1.2 希尔排序

  取定一个小于$n$的整数$d_1$作为第一个增量，把文件的全部记录分成$d_1$个组（所有距离为$d_1$倍数的记录放在同一个组），各组内进行直接插入排序；取第二个增量$d_2<d_1$，重复上述分组和排序，直至所取增量为1。

特点：

• 不稳定，每次排序后不能保证有一个元素在最终位置上

def shellSort(arr):
    n=len(arr)
    gap=int(n/2)
    while gap>0:
        for i in range(gap,n):
            key=arr[i]
            j=i
            while j>=gap and arr[j-gap]>key:
                arr[j]=arr[j-gap]
                j-=gap
            arr[j]=key
        gap//=2
1
2
3
4
5
6
7
8
9
10
11
12

---

2. 交换排序

  两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直至没有反序的记录为止。

2.1 冒泡排序

• 降序：一趟排序降最“轻”的放前面
• 升序：一趟排序降最“重”的放后面

特点：

• 稳定，每次排序后，后面的元素肯定是已经排好序的，所以每次排序后可以确定一个元素在其最终的位置上

def bubbleSort(arr):
    n=len(arr)
    for j in range(n,1,-1):
    	# 前j个元素，将最大的放在最后
        for i in range(j-1):
            if arr[i]>arr[i+1]:
                arr[i],arr[i+1]=arr[i+1],arr[i]
1
2
3
4
5
6
7

2.2 快速排序

  快速排序是一种分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，根据实现算法的不同，元素的选择一般有如下几种：

1. 永远选择第一个元素
2. 永远选择最后一个元素
3. 随机选择元素
4. 取中间值

  整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。

特点：

• 不稳定；
• 快速排序过程中不会产生有序子序列，但每一趟排序后都有一个元素放在其最终位置上；
• 每次选择的关键值可以把数组分为两个子数组的时候，快速排序算法的速度最快，当数组已经是正序或逆序时速度最慢；
• 递归次数与每次划分后得到的分区的处理顺序无关；
• 对n个关键字进行快速排序，最大递归深度为n，最小递归深度为log2n；

'''low起始索引，high结束索引
永远选最后一个元素为基准
 partition返回分区后基准所在位置'''

def partition(arr,low,high):
    i=low-1# 当前比基准值小的元素的最大下标
    pivot=arr[high]
    # 遍历除了基准元素外的所有值
    for j in range(low,high):
        if arr[j]<=pivot:
            i+=1
            arr[i],arr[j]=arr[j],arr[i]   
            
    arr[i+1],arr[high]=arr[high],arr[i+1]
    return i+1

def quickSort(arr,low,high):
    if low<high:
        pi=partition(arr,low,high)
        quickSort(arr,low,pi-1)
        quickSort(arr,pi+1,high)

arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

3. 选择排序

  每一趟从待排序的记录中选出关键字最大或最小的记录，顺序放在已排好序的子文件的最后，直至全部记录排序完毕。

3.1 直接选择排序

  假设待排序的记录存放在数组arr中，排序过程的某一中间时刻，arr被划分成两个子区间[R[1],R[i-1]]和[R[i],R[n-1]]，其中后一个子区间是已排好序的有序区，前一个子区间则是当前未排好序的部分，即无序区。直接选择排序就是将当前无序区的最大元素加入有序区。

特点：

• 每趟排序都使有序区中增加一个记录，且有序区中记录的关键字均不小于无序区中的关键字。
• 第n趟前n个位置正确
• 不稳定，每趟排序后前面的元素肯定是已经排好序的了，每次排序后可以确定一个元素会在其最终位置上.

# arr前n个元素中最大的元素位置
def findMaxPos(arr,n):
  	pos=0
  	maxnum=arr[0]
  	for i in range(1,n):
  		if arr[i]>maxnum:
  			maxnum=arr[i]
  			pos=i
  	return pos
  
def selectionSort(arr):
	n=len(arr)
  	for i in range(n,1,-1):
  		pos=findMaxPos(arr,i)
  		arr[i-1],arr[pos]=arr[pos],arr[i-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2 堆排序

  堆是一个近似完全二叉树的结构，且满足子结点的键值或索引总是小于（或者大于）它的父节点。堆排序是一树形选择排序，在排序过程中，将arr看做是一棵完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录。

• $n$个关键字序列$K_1,K_2,...,K_n$称为大根堆，当且仅当该序列满足特性：$K_i\ge K_{2i},K_i\ge K_{2i+1}(1\le i\le \lfloor n/2\rfloor )$，即完全二叉树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。大根堆的堆顶关键字最大。
• $n$个关键字序列$K_1,K_2,...,K_n$称为小根堆，当且仅当该序列满足特性：$K_i\le K_{2i},K_i\le K_{2i+1}(1\le i\le \lfloor n/2\rfloor )$，即完全二叉树中任一非叶子结点的关键字均小于等于其孩子结点的关键字。小根堆的堆顶关键字最小。

建堆（大根堆）：

  只有一个结点的树显然是堆。在完全二叉树中，所有序号$i>\lfloor n/2\rfloor$的结点都是叶子，因此以这些结点为根的树均已是堆。这样，我们只需依次将序号为$\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,...,1$的结点作为根的子树调整为堆即可。

  已知结点 $R[i]$ 的左右子树已是堆，将以 $R[i]$ 为根的完全二叉树调整为堆（筛选法）： 在 $R[i]$和它的左右孩子中选取关键字最大的结点放到 $R[i]$ 的位置上：

• 若 $R[i]$ 的关键字已是三者众最大者，则无须做任何调整，以 $R[i]$ 为根的子树已构成堆；
• 否则，不妨设左孩子 $R[2i]$ 的关键字最大，则将 $R[i]$ 和 $R[2i]$ 交换位置，交换后可能导致以 $R[2i]$ 为根的子树不再是堆，但 $R[2i]$ 的左右子树仍是堆，则可重复上述过程，将以 $R[2i]$ 为根的子树调整为堆，…，如此重复下去。

堆排序：

  利用大根堆排序，每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中最后一个记录交换

特点：

• 第n趟前或后n个位置正确
• 不稳定

# 对编号为i的结点做heapify（大根堆）操作，只考虑tree的前n个结点
def heapify(tree,n,i):
  	#递归出口：叶子结点不需要heapify
 	if i>n:return
 	#比较i和其子结点，返回值最大的结点下标
 	c1,c2=2*i+1,2*i+2
 	maxp=i
 	if c1<n and tree[c1]>tree[maxp]:
 		maxp=c1
 	if c2<n and tree[c2]>tree[maxp]:
 		maxp=c2
 	# 如果值最大的不是i结点，则交换，并heapify调整子树
 	if maxp!=i:
 		tree[maxp],tree[i]=tree[i],tree[maxp]
 		heapify(tree,n,maxp)
  
# 建堆
# 从最后一个非叶子结点（最后一个结点的父结点）开始递减做heapify
def build_heap(tree):
	n=len(tree)
  	last_node=n-1
  	parent=last_node//2
  	for i in range(parent,-1,-1):
  		heapify(tree,n,i)
  
# 堆排序
def heap_sort(tree):
  	n=len(tree)
  	build_heap(tree)
  	for i in range(n-1,-1,-1):
  		tree[0],tree[i]=tree[i],tree[0]
  		# 重建堆，不考虑已经排好序的结点，由于此时根结点左右子树已是堆，只需heapify操作
  		heapify(tree,i,0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Python中的堆：heapq库（小根堆）

heapq.heapify(x)

• 将list x 转换成堆。

heapq.heappush(heap, item)

• 将 item 的值加入 heap 中，保持堆的不变性。

heapq.heappop(heap)

• 弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。

heapq.heappushpop(heap, item)

• 将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。

heapq.heapreplace(heap, item)

• 弹出并返回 heap 中最小的一项，同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError。这个单步骤操作比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆时更为适宜。

heapq.merge(*iterables, key=None, reverse=False)

• 将多个已排序的输入合并为一个已排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。 返回已排序值的 iterator。类似于 sorted(itertools.chain(*iterables)) 但返回一个可迭代对象，不会一次性地将数据全部放入内存，并假定每个输入流都是已排序的（从小到大）。
• 具有两个可选参数，它们都必须指定为关键字参数。在 3.5 版更改: 添加了可选的 key 和 reverse 形参。
  • key 指定带有单个参数的 key function，用于从每个输入元素中提取比较键。 默认值为 None (直接比较元素)。
  • reverse 为一个布尔值。 如果设为 True，则输入元素将按比较结果逆序进行合并。 要达成与 sorted(itertools.chain(*iterables), reverse=True) 类似的行为，所有可迭代对象必须是已从大到小排序的。

heapq.nlargest(n, iterable, key=None)

• 从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key, reverse=True)[:n]。

heapq.nsmallest(n, iterable, key=None)

• 从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]。

后两个函数在 n 值较小时性能最好。 对于更大的值，使用 sorted() 函数会更有效率。 此外，当 n==1 时，使用内置的 min() 和 max() 函数会更有效率。 如果需要重复使用这些函数，请考虑将可迭代对象转为真正的堆。

堆排序

堆排序 可以通过将所有值推入堆中然后每次弹出一个最小值项来实现。

def heapsort(iterable):
	h = []
	for value in iterable:
		heappush(h, value)
	return [heappop(h) for i in range(len(h))]
1
2
3
4
5

堆元素可以为元组。 这适用于将比较值（例如任务优先级）与跟踪的主记录进行赋值的场合：

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
1
2
3
4
5
6
7

heapq — 堆队列算法官方文档

---

4. 归并排序

  “归并”是指将若干个已排序的子文件合并成一个有序文件。

  二路归并排序思想：将待排序文件 $R[0]$ 到 $R[n-1]$ 看成 n 个长度为1的有序子文件，把这些子文件两两归并，得到$\lceil n/2\rceil$个有序的子文件；然后再把这$\lceil n/2\rceil$个有序的子文件两两归并，如此反复，直到最后得到一个长度为 n 的有序文件为止。

# arr[L,M-1]、arr[M,R]是两个已排好序（升序）的区间段，归并
def merge(arr,L,M,R):
  	left_size=M-L
  	right_size=R-M+1
  	left=arr[L:M]
  	right=arr[M:]
  	# i指向left,j指向right，k指向当前合并的arr位置
  	i,j,k=0,0,L
  	while i<left_size and j<right_size:
 		if left[i]<right[j]:
 			arr[k]=left[i] 
  			i+=1
  			k+=1
  		else:
  			arr[k]=right[j]
  			j+=1
  			k+=1
  	while i<left_size:
        arr[k]=left[i]
        k+=1
        i+=1
    while j<right_size:
        arr[k]=right[j]
        k+=1
        j+=1
  
# 归并排序
def mergeSort(arr,L,R):
	if L<R: 
  		M=(L+R)//2
  		mergeSort(arr,L,M)
  		mergeSort(arr,M+1,R)
 		merge(arr,L,M+1,R)
  
arr=[6,8,9,10,4,5,2,7]
L,R=0,7
mergeSort(arr,L,R)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

5. 分配排序

5.1 桶排序/箱排序

  桶排序的原理是将数组分到有限数量的桶中，再对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶；
2. 将待排序的一组数，分档归入这些子桶，并将桶中的数据进行排序；
3. 将各个桶中的数据有序的合并起来。

5.2 基数排序

  基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

---

数据结构——用C语言描述（唐策善等）