1.简介

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

△ 相关概念&名词解释

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
• n：数据规模。
• k：“桶”的个数。
• In-place：占用常数内存，不占用额外内存。
• Out-place：占用额外内存。

△ 排序算法可以分为非线性时间比较类和线性时间非比较类

• 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。
• 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

△ 排序算法可以分为内部排序和外部排序：

• 内部排序是数据记录在内存中进行排序。
• 外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

2.排序算法

2.1.冒泡排序（Bubble Sort）

2.1.1. 算法概述

• 冒泡排序是一种简单的排序算法。它重复地遍历待排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止，此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.1.2. 算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素进行同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤 1~3，直到排序完成。

2.1.3. 算法特点

• 什么时候最快（Best Cases）：当输入的数据已经是正序时。
• 什么时候最慢（Worst Cases）：当输入的数据是反序时。

2.1.4. python代码实现

# 时间复杂度:最好:O(n) 平均:O(n²) 最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:稳定

def bubble_sort(self, nums: List[int]) -> List[int]:
	# 遍历len(nums)-1趟
	for i in range(len(nums)):
		is_sorted = True
		# 已经排序好的部分不用排序
		for j in range(len(nums) - i - 1):
			if nums[j] > nums[j + 1]:
				nums[j], nums[j + 1] = nums[j + 1], nums[j]
				is_sorted = False
		if is_sorted:
			break
	return nums

2.2. 选择排序（Selection Sort）

2.2.1.算法概述

• 工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。即 选择数组中最小的数字放到index=0的位置，数组会越来越小，数组为0时，排序完毕。

2.2.2.算法步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

2.2.3.算法特点

• 选择排序是一种简单直观的排序算法。表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

2.2.4. python代码实现

# 时间复杂度:最好:O(n²) 平均:O(n²) 最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:不稳定

def select_sort(self, nums: List[int]) -> List[int]:
	for i in range(len(nums)):
		# 默认最小值的索引,默认第一个元素已经排序
		min_index = i
		for j in range(i + 1, len(nums) - 1):
			# 每次遍历的值与最小值进行比较
			if nums[j] < nums[min_index]:
				min_index = j
				# 每一轮选出最小的元素,并放置在有序序列的末尾
         if min_index != i:
			nums[i], nums[min_index] = nums[min_index], nums[i]
	return nums

2.3.插入排序（Insertion Sort）

2.3.1.算法概述

• 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入
  

2.3.2.算法步骤

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后； 重复步骤 2~5。

2.3.3.算法特点

• 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。插入排序的核心在于，它把一个无序数列看成两个数列，假如第一个元素构成了第一个数列，那么余下的元素构成了第二个数列，很显然，第一个数列是有序的（因为只有一个元素嘛，肯定有序哦），那么我们把第二个数列的第一个元素拿出来插入到第一个数列，使它依然构成一个有序数列，直到第二个数列中的所有元素全部插入到第一个数列，这时候就排好序了。

2.3.4.python代码实现

# 时间复杂度:最好:O(n) 平均:O(n²)最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:稳定

def insert_sort(self, nums: List[int]) -> List[int]:
	# 遍历len(nums)-1轮
	for i in range(len(nums) - 1):
		# curNum 保存待插入元素
		curNum, preIndex = nums[i + 1], i
		# 如果待插入元素小于当前元素,当前元素值向后移动,同时下标向前移动
		while preIndex >= 0 and curNum < nums[preIndex]:
			nums[preIndex + 1] = nums[preIndex]
			preIndex -= 1
		# curNum插入的正确位置
		nums[preIndex + 1] = curNum
	return nums

2.4.快速排序（Quick Sort）

2.4.1.算法概述

• 快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

2.4.2.算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
   

2.4.3.算法特点

• 快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。

2.4.4.python代码实现

# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(n²)
# 空间复杂度:O(nlogn)
# 稳定性:不稳定

# 实现方式1:
def quick_sort(self, nums: List[int]) -> List[int]:
    # 递归终止条件
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    # 单层递归逻辑
    left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot]
    right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
    return self.quick_sort(left) + [pivot] + self.quick_sort(right)

# 实现方式2:
def quick_sort1(self, nums: List[int], left: int, right: int) -> List[int]:
	if left < right:
		pivotIndex = self.partition(nums, left, right)
		self.quick_sort1(nums, left, pivotIndex - 1)
		self.quick_sort1(nums, pivotIndex + 1, right)
	return nums

def partition(self, nums: List[int], left: int, right: int) -> int:
    """
    分区操作
    """
	pivot = nums[left]
	# left 向右移动,直至遇到大于等于pivot的元素停止
	# right 向左移动,直至遇到小于等于pivot的元素停止
	while left < right:
		while left < right and nums[right] >= pivot:
			right -= 1
		nums[left] = nums[right]
		while left < right and nums[left] <= pivot:
			left += 1
		nums[right] = nums[left]
	nums[left] = pivot
	return left

2.5.希尔排序（Shell Sort）

2.5.1.算法概述

• 希尔排序是希尔 (Donald Shell) 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破O(n²)的第一批算法之一。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
  1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
• 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序”时，再对全体记录进行依次直接插入排序。

2.5.2.算法步骤

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2.5.3.算法特点

• 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

2.5.4.python代码实现

# 时间复杂度:最好:O(n) 平均:O(n²)最差:O(n²)
# 空间复杂度:O(1)
# 稳定性:不稳定

def shell_sort(self, nums: List[int]) -> List[int]:
	# 定义间隔序列
	gap = len(nums) // 2
	# 当gap = 0时,排序已经全部完成
	while gap > 0:
		# 遍历的时候加了gap
		for i in range(gap, len(nums)):
			# curNum保存待插入元素,操作元素之间的间隔为gap
			curNum, preIndex = nums[i], i - gap
			while preIndex >= 0 and curNum < nums[preIndex]:
				# 大的数据往后移动
				nums[preIndex + gap] = nums[preIndex]
				preIndex -= gap
			# curNum插入的正确位置
			nums[preIndex + gap] = curNum
		# 更新间隔
		gap //= 2
	return nums

2.6.归并排序（Merge Sort）

2.6.1. 算法概述

• 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并， 得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。

2.6.2. 算法步骤

归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：

1. 如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子列；
2. 分别对这两个子序列进行归并排序，使子序列变为有序状态；
3. 设定两个指针，分别指向两个已经排序子序列的起始位置；
4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
5. 重复步骤 3 ~4 直到某一指针达到序列尾；
6. 将另一序列剩下的所有元素直接复制到合并序列尾。

2.6.3. 算法特点

• 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn)的时间复杂度。代价是需要额外的内存空间。

2.6.4. python代码实现

# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(nlogn)
# 空间复杂度:O(n)
# 稳定性:稳定

def merge_sort(self, nums: List[int]) -> List[int]:
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = self.merge_sort(nums[:mid])
    right = self.merge_sort(nums[mid:])
    return self.merge(left, right)

def merge(self, left: List[int], right: List[int]) -> List[int]:
    # 存储排序之后的结果
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 剩余元素加入到result的结尾
    result = result + left[i:] + right[j:]
    return result

2.7. 堆排序（Heap Sort）

2.7.1.算法概述

• 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
  1. 大根堆：每个节点的值都大于或等于其子节点的值，用于升序排列；
  2. 小根堆：每个节点的值都小于或等于其子节点的值，用于降序排列

2.7.2.算法步骤

• 将初始待排序列 (R1, R2, ……, Rn) 构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]<=R[n]；
• 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2, ……, Rn-2)和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

2.7.3.python代码实现

# 时间复杂度:最好:O(nlogn) 平均:O(nlogn) 最差:O(nlogn)
# 空间复杂度:O(1)
# 稳定性:不稳定
# 堆排序的核心:1.堆初始化 2.调整堆

def heap_sort(self, nums: List[int]) -> List[int]:
	# 1.堆初始化,从最后一个非叶子节点创建大顶堆
	for i in range(len(nums) // 2)[::-1]:
		self.adjust_heap(nums, i, len(nums))
	# 2.输出堆顶元素后,剩余元素继续调整为堆
	for i in range(len(nums))[::-1]:
		# 每次最大的元素在根节点
		nums[0], nums[i] = nums[i], nums[0]
		# 继续调整堆
		self.adjust_heap(nums, 0, i)
	return nums

# 调整堆
def adjust_heap(self, nums: List[int], i: int, l: int)->None:
	# 左右孩子节点的索引
	lchild, rchild = 2 * i + 1, 2 * i + 2
	# 最大元素的索引
	largest = i
	# 从当前节点,左孩子以及右孩子节点选出最大元素的索引
	if lchild < l and nums[lchild] > nums[largest]:
		largest = lchild
	if rchild < l and nums[rchild] > nums[largest]:
		largest = rchild
	# 如果当前元素不是最大值,则更换最大值,继续调整堆
	if largest != i:
		nums[largest], nums[i] = nums[i], nums[largest]
		# largest调整后的值,大的元素在上面
		self.adjust_heap(nums, largest, l)

2.8.计数排序（Counting Sort）

2.8.1. 算法概述

• 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 计数排序 (Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C来将 A 中的元素排到正确的位置。它只能对整数进行排序。

2.8.2. 算法步骤

1. 找出数组中的最大值 max、最小值 min；
2. 创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
3. 遍历原数组 A中的元素 A[i]，以 A[i]-min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出 现次数作为 C[A[i]-min]的值；
4. 对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
5. 创建结果数组 R，长度和原始数组一样；
6. 从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min作为索引，在计数数组 C 中找到对应的值 C[A[i]-min]，C[A[i]-min]-1 就是 A[i] 在结果数组 R中的位置，做完上述这些操作，将 count[A[i]-min] 减小 1。

2.8.3. python代码实现

# 时间复杂度:最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
# 空间复杂度:O(n+k)
# 稳定性:稳定

def count_sort(self, nums: List[int]) -> List[int]:
	# 1.创建一个大小为:最大值-最小值+1的数组,初始值为0
	bucket = [0] * (max(nums) - min(nums) + 1)
	# 2.统计原数组中每个元素出现的个数,存储在新开辟的数组中
	for num in nums:
		bucket[num - min(nums)] += 1
	# nums的下标
	i = 0
	# 根据每个元素出现的次数,按照新开辟数组的元素从小到大依次填充到原来的数组中
	for j in range(len(bucket)):
		while bucket[j] > 0:
			nums[i] = j + min(nums)
			bucket[j] -= 1
			i += 1
	return nums

2.9. 桶排序（Bucket Sort）

2.9.1.算法概述

• 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
  1. 在额外空间充足的情况下，尽量增大桶的数量；
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
• 桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。
• 对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

2.9.2.算法步骤

1. 设置一个 BucketSize，作为每个桶所能放置多少个不同数值；
2. 遍历输入数据，并且把数据依次映射到对应的桶里去；
3. 对每个非空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
4. 从非空桶里把排好序的数据拼接起来。

2.9.3.算法特点

• 什么时候最快：当输入的数据可以均匀的分配到每一个桶中。
• 什么时候最慢：当输入的数据被分配到了同一个桶中。

2.9.4. python代码实现

# 时间复杂度：最佳：O(n+k) 最差：O(n²) 平均：O(n+k)
# 空间复杂度：O(n+k)
# 稳定性：稳定

def bucket_sort(self, nums: List[int]) -> List[int]:
	# 1.数据分桶
	# 定义桶的大小
	bucketSize = 4
	# 桶的个数
	bucketCount = (max(nums) - min(nums)) // bucketSize + 1
	# 初始化桶,二维数组
	buckets = [[] for _ in range(bucketCount)]
	# 2.数据入桶,利用函数映射将数据入桶
	for num in nums:
		buckets[(num - min(nums)) // bucketSize].append(num)
	nums.clear()  # 清空nums数组
	# 3.桶内排序,合并结果
	for bucket in buckets:
		self.insert_sort(bucket)
		# extend() 函数用于在列表末尾一次性追加另一个序列中的多个值
		nums.extend(bucket)
	return nums

2.10.基数排序（Radix Sort）

2.10.1. 算法概述

• 基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 O(n×k)，n 为数组长度，k为数组中元素的最大的位数；基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

2.10.2. 算法步骤

1. 取得数组中的最大数，并取得位数，即为迭代次数 N（例如：数组中最大数值为 1000，则 N=4）；
2. A为原始数组，从最低位开始取每个位组成 radix 数组；
3. 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）； 将
4. radix 依次赋值给原数组； 重复 2~4 步骤 N 次。

2.10.3. 算法特点

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值。

2.10.3. python代码实现

# 时间复杂度：最佳：O(n×k) 最差：O(n×k) 平均：O(n×k)
# 空间复杂度：O(n+k)
# 稳定性：稳定

def radix_sort(self, nums: List[int]) -> List[int]:
    mod, div = 10, 1
    # 最大元素位数的长度决定外循环的次数
    mostBit = len(str(max(nums)))
    # 初始化一个0-9的桶
    buckets = [[] for i in range(mod)]
    while mostBit:
        # 数据入桶
        for num in nums:
            buckets[num // div % mod].append(num)
        i = 0
        # 收集结果,从每个桶中取数
        for bucket in buckets:
            while bucket:
                nums[i] = bucket.pop(0)
                i += 1
        # 高位
        div *= 10
        mostBit -= 1
    return nums

######################################################################################################