​
​

活动地址：CSDN21天学习挑战赛

1.排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减排列起来的操作。排序是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列。

评价指标

• 时间复杂度
• 空间复杂度
• 使用场景：针对实际对节省时间和空间的不同需求，选择适用于不同场景的排序算法
• 稳定性：稳定的算法在排序过程中不会改变元素彼此之间次序

不同排序算法O(n)分类

2. 选择排序

选择排序（Selection-sort）是一种简单直观的排序算法。工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，存放到已排序序列的末尾。依此类推，直到所有元素均排序完毕。常用的选择排序方法有两种，直接选择排序和树形选择排序。

2.1 直接选择排序

算法流程

图片来源：一文学懂经典算法系列之直接选择排序

伪代码

for i = 1 to n - 1
    k = i
    for j = i + 1 to n
        if A[j] < A[k]
            k = j
    if k != i
        exchange A[i] with A[k]

算法评价

• 时间复杂度：$O(n^2)$，
• 空间复杂度：$O(1)$

2.2 树形选择排序

树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

排序思想

（1）两两比较待排序的n个记录的关键字，并取出较小者。
（2）在n/2个较小者中，采用同样的方法比较选出每两个中的较小者。
（3）如此反复上述过程，直至选出最小关键字记录为止。
可以用一棵有n个节点的树来表示，选出的最小关键字记录就是这棵树的根节点。当输出最小关键字之后，为了选出次小关键字，可以设置根节点（最小关键字记录所对应的叶节点）的关键字值为∞，然后再进行上述的过程，直到所有的记录全部输出为止。例如存在如下数据：49，38，65，97，76，13，27，49。如果想从上述8个数据中选出最小数据，具体实现过程如图所示。

在树形选择排序中，被选中的关键字都走了一条由叶节点到根节点的比较过程。因为含有n个叶节点的完全二叉树的深度为[log 2 n]+1，所以在树形选择排序中，每当选择一个关键字都需要进行log 2 n次比较，其时间复杂度为O（log 2 n）。因为移动记录次数不超过比较次数，所以总的算法时间复杂度为O（nlog 2 n）。与简单选择排序相比，树形选择排序降低了比较次数的数量级，增加了n-1个存放中间比较结果的额外存储空间，并同时附加了与∞进行比较的时间耗费。

算法评价

• 时间复杂度：$O(n\ast \log n)$
• 空间复杂度：$O(n)$

2.3 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

算法流程

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

3. 算法实践(Python)

3.1 直接插入排序

def selectedSort(myList):
	# 获取长度列表
	length = len(myList)

	for i in range(0, length-1):
		# 设置最小值的index为当前值
		smallest = i
		# 若当前最小index的值分别与后面的值比较，以便获取最小index
		for j in range(i+1, length):
			# 如果找到比当前值小的index，则进行两值交换
			if myList[j] < myList[smallest]:
				tmp = myList[j]
				myList[j] = myList[smallest]
				myList[smallest] = tmp
			# 打印每一轮比较好的列表
			print('Round',i,':',myList)

myList = [1,4,5,0,6]
print('selected Sort: ')
selectedSort(myList)

selected Sort:
Round  0 :  [0, 4, 5, 1, 6]
Round  1 :  [0, 1, 5, 4, 6]
Round  2 :  [0, 1, 4, 5, 6]
Round  3 :  [0, 1, 4, 5, 6]

3.2 堆排序

参考代码折半插入排序的 python 实现

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

参考

1.一文学懂经典算法系列之直接选择排序
2.张清云.《Python数据结构学习笔记》(ISBN：9787113269999)
3. Python 十大经典排序算法实现详解

@夏日回音
​