前语
近期在预备下半年的软考,在刷题进程中遇到了一些经典的数据结构与算法的经典例题,在这里我以博客的方法回忆记录下【排序算法】的运用以及相关拓展。
概述
常见10种的排序算法包含:【冒泡排序】、【刺进排序】、【挑选排序】、【快速排序】、归并排序】、【堆排序】、【希尔排序】【计数排序】、【桶排序】、【 基数排序】。在这里我们运用python语言来完结这些排序算法,简化下完结流程,我们生成一个长度为10的随机数组:
import random
# 生成一个长度为10,元素在0-100之间的随机数组
arr = [random.randint(0, 100) for _ in range(10)]
print(arr)
冒泡排序
冒泡排序是一种简略的排序算法,它的原理是经过不断交流相邻元素的方位,将最大的元素逐步“冒泡”到序列的结尾,然后完结排序。
详细完结进程如下:
- 首要,比较相邻的两个元素,假如前面的元素比后面的元素大,则交流它们的方位。
- 对每一对相邻的元素都进行上述比较和交流,这样一轮下来,最大的元素就会“冒泡”到序列的结尾。
- 针对剩下未排序的元素,重复第 1 步和第 2 步,直到整个序列都被排序。
在完结进程中,需求运用两层循环来完结冒泡排序。外层循环操控排序轮数,内层循环操控每轮比较的次数。详细完结进程如下:
- 首要,外层循环从第一个元素开端,顺次遍历到倒数第二个元素。
- 内层循环从第一个元素开端,顺次遍历到倒数第二个未排序的元素。
- 在内层循环中,比较相邻的两个元素,假如前面的元素比后面的元素大,则交流它们的方位。
- 每轮内层循环完毕后,最大的元素就会被“冒泡”到结尾,因而外层循环能够减少一次遍历。
- 终究,整个序列就被排好序了。
冒泡排序的时刻复杂度为 O(n^2),空间复杂度为O(1)。,因而它不适合用于大规划数据的排序。
# 冒泡
def bubble_sort(arr):
n = len(arr)
# 遍历一切数组元素
for i in range(n):
# 终究i个元素现已排好序,不需求再比较
for j in range(0, n-i-1):
# 假如当时元素大于下一个元素,则交流它们
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
刺进排序
刺进排序是一种简略的排序算法,其基本原理是将未排序的元素一个一个刺进到已排序的序列中,直到一切元素都被排序。
刺进排序的完结进程如下:
- 将序列的第一个元素视为已排序的序列。
- 从第二个元素开端,顺次将每个元素刺进到已排序的序列中。详细操作是将该元素与已排序序列中的元素从后往前比较,假如该元素比已排序序列中的元素小,则将已排序序列中的元素往后移动一个方位,直到找到该元素应该刺进的方位。
- 重复进程2,直到一切元素都被刺进到已排序序列中。
完结进程中,能够运用嵌套循环来完结刺进排序。外层循环从第二个元素开端遍历,内层循环从当时元素往前遍历已排序序列,直到找到该元素应该刺进的方位。在内层循环中,假如已排序序列中的元素比当时元素大,则将其往后移动一个方位。终究,将当时元素刺进到找到的方位。
# 刺进排序
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
刺进排序的时刻复杂度为O(n),空间复杂度为O(1)。尽管刺进排序的时刻复杂度不如快速排序和归并排序等算法,可是关于小规划数据的排序,刺进排序的功率比较高。
挑选排序
挑选排序是一种简略的排序算法,其基本原理是每次挑选未排序序列中的最小元素,将其放到已排序序列的结尾,直到一切元素都被排序。
挑选排序的完结进程如下:
- 将序列的第一个元素视为已排序的序列。
- 从第二个元素开端,顺次遍历未排序的序列,找到其间最小的元素,将其放到已排序序列的结尾。
- 重复进程2,直到一切元素都被排序。
完结进程中,能够运用嵌套循环来完结挑选排序。外层循环从第一个元素开端遍历,内层循环从当时元素的下一个元素开端遍历未排序的序列,找到其间最小的元素,并将其与当时元素交流方位。
挑选排序的时刻复杂度为O(n),空间复杂度为O(1)。尽管挑选排序的时刻复杂度不如快速排序和归并排序等算法,可是关于小规划数据的排序,挑选排序的功率比较高。
# 挑选排序
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
快速排序
快速排序是一种常用的排序算法,其原理是经过挑选一个基准元素,将序列分红两个子序列,将比基准元素小的元素放到左边,比基准元素大的元素放到右边,然后对左右两个子序列递归地进行快速排序,终究得到一个有序序列。
快速排序的完结进程如下:
- 挑选一个基准元素,一般挑选序列的第一个元素。
- 将序列分红两个子序列,一个子序列包含比基准元素小的元素,一个子序列包含比基准元素大的元素。
- 对左右两个子序列递归地进行快速排序。
- 将左子序列、基准元素、右子序列顺次连接起来,得到一个有序序列。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
归并排序
归并排序是一种依据分治思想的排序算法,它将待排序的序列分红两个子序列,对每个子序列递归地进行排序,然后将两个有序子序列兼并成一个有序序列。
其完结进程如下:
- 分解:将待排序的序列分红两个子序列,递归地将每个子序列分解成更小的子序列,直到每个子序列只要一个元素停止。
- 兼并:将两个有序子序列兼并成一个有序序列。详细地,能够运用两个指针分别指向两个子序列的头部,比较两个指针所指向的元素的巨细,将较小的元素放入成果序列中,并将该指针后移一位,直到其间一个子序列现已全部放入成果序列中,然后将另一个子序列中剩下的元素顺次放入成果序列中。
- 回来:将兼并后的有序序列作为成果回来。
归并排序的时刻复杂度为O(nlogn),空间复杂度为O(n),是一种稳定的排序算法。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
left_arr = merge_sort(left_arr)
right_arr = merge_sort(right_arr)
return merge(left_arr, right_arr)
def merge(left_arr, right_arr):
result = []
i, j = 0, 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
result += left_arr[i:]
result += right_arr[j:]
return result
堆排序
堆排序是一种依据堆的排序算法,它将待排序的序列构建成一个堆,然后顺次取出堆顶元素,将其放到已排序序列的结尾。
其完结进程如下:
- 构建堆:将待排序的序列构建成一个堆。详细地,能够先将序列当作一棵完全二叉树,然后从终究一个非叶子节点开端,顺次将每个节点与其子节点比较,假如节点的值比其子节点的值小,则交流这两个节点的值,然后持续向下比较,直到该节点没有子节点或者节点的值现已比其子节点的值大。
- 排序:顺次取出堆顶元素,将其放到已排序序列的结尾。详细地,能够将堆顶元素与堆底元素交流,然后将堆的巨细减1,然后从堆顶开端向下调整堆,以保持堆的性质。
- 重复:重复进程2,直到堆中只剩下一个元素停止。
堆排序的时刻复杂度为O(nlogn),空间复杂度为O(1),是一种不稳定的排序算法。
# 堆排序
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 顺次取出堆顶元素,将其放到已排序序列的结尾
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
# 在以i为根节点的子树中构建最大堆
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
希尔排序
希尔排序,也称递减增量排序,是刺进排序的一种改进版别。希尔排序的基本思想是将待排序的序列分红若干个子序列,对每个子序列进行刺进排序,然后逐步缩小子序列的长度,终究进行一次刺进排序,完结排序。
完结进程如下:
- 挑选一个增量序列,例如:N/2,N/4,N/8…直到增量为1。
- 关于每个增量,将待排序的序列分红若干个子序列,每个子序列的元素下标之间相差增量。
- 对每个子序列进行刺进排序。
- 逐步缩小增量,重复进程2和3,直到增量为1。
- 终究进行一次刺进排序,完结排序。
希尔排序的时刻复杂度取决于增量序列的挑选,一般状况下,时刻复杂度为O(n^2)。希尔排序是一种不稳定的排序算法,因为它会改变相等元素的原始次序。
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
计数排序
计数排序是一种非比较排序算法,其基本思想是核算每个元素在序列中呈现的次数,然后依据元素呈现的次数将元素排序。计数排序的时刻复杂度为 O(n+k),其间 n 是序列的长度,k 是序列中元素的取值范围。
计数排序的完结进程如下:
- 找出序列中的最大值和最小值,确定计数数组的长度。
- 核算每个元素在序列中呈现的次数,将其存储在计数数组中。
- 核算每个元素在有序序列中的方位,即前缀和数组。
- 从后往前遍历原序列,依据前缀和数组将元素放到有序序列中的对应方位。
def countingSort(arr):
# 找到数组中的最大值
max_value = max(arr)
# 初始化计数数组
count = [0] * (max_value + 1)
# 核算每个元素呈现的次数
for i in arr:
count[i] += 1
# 依据计数数组排序
sorted_arr = []
for i in range(max_value + 1):
sorted_arr.extend([i] * count[i])
return sorted_arr
桶排序
桶排序是一种非比较排序算法,它的核心思想是即将排序的数据分到几个有序的桶里,每个桶里的数据再独自进行排序,终究将每个桶中的数据依照次序顺次取出,即可得到排序成果。桶排序的时刻复杂度为O(n),但需求额定的空间来存储桶。
桶排序的完结进程如下:
- 找到待排序序列中的最大值和最小值。
- 核算出桶的个数,并创立相应个数的桶。
- 遍历待排序序列,将每个元素分配到对应的桶中。
- 对每个桶中的元素进行排序,能够运用恣意排序算法,如刺进排序等。
- 将每个桶中的元素依照次序顺次取出,即可得到排序成果。
桶排序的优化:
- 假如待排序序列中的元素散布不均匀,则能够运用动态桶的方法,即依据待排序数据的散布状况动态的调整桶的个数和桶的巨细。
- 假如待排序序列中的元素重复度较高,则能够运用计数排序的方法,即对每个桶中的元素进行计数,避免重复元素的排序。
- 假如待排序序列中的元素不是整数类型,能够考虑运用基数排序的方法,即依照元素的位数从低到高进行排序。
桶排序的适用场景:
桶排序适用于待排序序列中的元素散布均匀、元素重复度低、元素取值范围不大等状况。例如,对学生的成果进行排序,成果的取值范围一般是0到100,且散布比较均匀,这时候能够运用桶排序来进行排序。
def bucket_sort(arr, bucket_size=5):
if len(arr) == 0:
return arr
# 确定桶的个数
min_val, max_val = min(arr), max(arr)
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
# 将元素放入桶中
for i in range(len(arr)):
bucket_index = (arr[i] - min_val) // bucket_size
buckets[bucket_index].append(arr[i])
# 对每个桶进行排序
for i in range(bucket_count):
buckets[i].sort()
# 将桶中的元素按次序兼并
sorted_arr = []
for bucket in buckets:
sorted_arr += bucket
return sorted_arr
基数排序
基数排序是一种非比较排序算法,它的原理是将待排序的数字依照位数从低到高进行排序。
详细的完结进程如下:
- 找出待排序数列中最大的数字,并确定其位数。
- 依据位数从低到高的次序,顺次对数列进行排序。
- 关于每一位数,将待排序数列中的数字依照该位数进行分桶。例如,关于个位数,将一切数字依照个位数的巨细分为10个桶。
- 将分好的桶依照次序兼并成一个新的数列。
- 重复第3步和第4步,直到一切位数都处理完毕。
- 终究得到的数列即为排好序的成果。
基数排序的时刻复杂度为O(d * (n + k)),其间d是数字的位数,n是待排序数列的长度,k是数字的取值范围。由于基数排序需求运用桶来存储数字,因而它需求额定的空间来存储桶,空间复杂度为O(n + k)。
基数排序的长处是稳定性好,适用于数字比较小但位数比较多的数列。可是它的缺陷是需求额定的空间来存储桶,当数字的取值范围较大时,空间消耗会很大。
# 基数排序
def radix_sort(arr):
# 获取数组中的最大值
max_num = max(arr)
# 获取最大值的位数
digit = len(str(max_num))
# 初始化桶
bucket = [[] for _ in range(10)]
# 进行 digit 次排序
for i in range(digit):
# 将每个元素放入对应的桶中
for num in arr:
index = (num // (10 ** i)) % 10
bucket[index].append(num)
# 将桶中的元素按次序放回数组中
arr.clear()
for j in range(10):
arr.extend(bucket[j])
bucket[j].clear()
return arr
复杂度
在软考中常见呈现时刻复杂度以及空间复杂度,这里先带我们回忆下这两个复杂度的概念:
时刻复杂度和空间复杂度都是用于【衡量算法功率】的指标。
【时刻复杂度】 是指算法运转所需求的时刻,一般用大 O 表明法来表明。大 O 表明法是一种用于描绘算法时刻复杂度的符号表明法,它表明算法运转时刻的增加率和输入数据规划 n 的联系。例如,假如一个算法的时刻复杂度为 O(n),则算法的运转时刻跟着输入数据规划 n 的添加而线性增加。
【空间复杂度】是指算法运转所需求的空间,一般用大 O 表明法来表明。空间复杂度是指算法在运转进程中所需求的额定空间,不包含输入数据所占用的空间。例如,假如一个算法的空间复杂度为 O(n),则算法在运转进程中所需求的额定空间跟着输入数据规划 n 的添加而线性增加。
排序算法中的时刻复杂度和空间复杂度:
结尾
不知不觉中写了这么多,软考备考路漫漫,仅以此篇分享众朋客飨阅!若有误烦请谈论告知,感谢!