排序算法
...大约 16 分钟
排序算法
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 代码复杂度 | ||
|---|---|---|---|---|---|---|
| 最坏 | 平均 | 最好 | ||||
| 冒泡排序 | n^2 | n^2 | n | 1 | 稳定 | 简单 |
| 直接选择排序 | n^2 | n^2 | n^2 | 1 | 不稳定 | 简单 |
| 直接插入排序 | n^2 | n^2 | n^2 | 1 | 稳定 | 简单 |
| 折半插入排序 | n^2 | n^2 | n | 1 | 稳定 | 简单 |
| 快速排序 | n^2 | nlogn | nlogn | 平均logn,最坏n | 不稳定 | 较复杂 |
| 堆排序 | nlogn | nlogn | nlogn | 1 | 不稳定 | 复杂 |
| 归并排序 | nlogn | nlogn | nlogn | n | 稳定 | 较复杂 |
Low B 三人组
冒泡算法（Bubble Sort）
文字描述
冒泡排序（Bubble Sort）之所以被称为冒泡排序，是因为在排序过程中，较小的元素会像水中的气泡一样逐渐“冒”到数列的顶端。这个过程类似于水中气泡的上升，因此得名“冒泡排序”。排序时，通过重复比较和交换相邻元素的位置，就像气泡从水底升到水面一样，较小或较大的元素会逐步移动到数列的一端。
在具体实现中，冒泡排序会重复遍历要排序的数列，每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。这个过程会一直重复，直到没有相邻元素需要交换，也就是数列完全有序为止。
代码实现
C++
void Bubble_sort(vector<int>& arr)
{
for(int i = 0;i < arr.size()-1;i++)
{
bool exchange = false;
for(int j = 0;j < arr.size()-1-i;j++)
{
if(arr[j]>arr[j+1])
{
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
}
Python
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return
选择排序
文字描述
选择排序是一种简单直观的排序算法。它的工作原理是这样的：首先在未排序的序列中找到最小（或最大）的元素，然后将其存放到排序序列的起始位置。接着，从剩余未排序的元素中继续寻找最小（或最大）的元素，然后放到已排序序列的末尾。这个过程会重复进行，直到所有元素都被排序。
在选择排序的每一轮中，你会从当前未排序的元素中选出最小（或最大）的一个，这就像是每次都“选择”出最小（或最大）的元素一样，因此得名“选择排序”。这个算法的时间复杂度是 O(n²)，所以当数据规模较小的时候使用它比较合适。
代码实现
C++
void select_sort(vector<int> &arr)
{
for(int i = 0;i < arr.size();i++)
{
int min_loc = i;
for(int j = i+1;j < arr.size();j++)
{
if(arr[j]<arr[min_loc])
min_loc = j;
}
int temp = arr[i];
arr[i] = arr[min_loc];
arr[min_loc] = temp;
}
}
Python
def select_sort(li):
for i in range(len(li)-1): # i是第几趟
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
插入排序
文字描述
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这个过程就像我们整理手中的扑克牌，把每张新摸到的牌插入到适当的位置以保持手中的牌总是有序的。
具体的算法步骤如下：
- 将第一个元素看作是一个有序的序列，剩下的所有元素为未排序的序列。
- 从未排序序列中取出一个元素，与已排序序列的元素从后向前进行比较。
- 如果已排序的元素大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5，直到未排序序列中的所有元素都被遍历。
插入排序的平均和最坏时间复杂度都是 O(n²)，空间复杂度是 O(1)。它是一种稳定的排序算法，适合于小规模数据的排序或者大规模已经基本有序的数据排序。
代码实现
C++
void insert_sort(vector<int> &arr)
{
//i表示摸到的牌的下标
for(int i = 1;i < arr.size();i++)
{
int key = arr[i]；
j = j-1; //j表示手里的牌的尾标
//手里的牌比摸到的牌大，向右腾位置
while(j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j -= 1;
}
//插入摸到的牌
arr[j+1] = key;
}
}
Python
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
NB 三人组
三者时间复杂度都是O(nlogn)
一般情况下的运行时间 快速排序<归并排序<堆排序
快速排序
文字描述
快速排序是一种高效的排序算法，由C.R.A. Hoare在1962年提出。它的基本思想是采用分治法来对一组数据进行排序。快速排序的步骤如下：
- 从数列中挑出一个元素，称为“基准”（pivot）。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序的平均时间复杂度为 O(NlogN)，是一种非常高效的排序方法。它也有多种改进版本，例如随机选择基准数，或者在区间内数据较少时直接使用其他方法排序以减小递归深度。
代码实现
C++
int partition(vetor<int> &arr,int left,int right)
{
int pivot = arr[left];
while(left < right)
{
while(left < right && arr[right] >= pivot)
right -= 1;
arr[left] = arr[right];
while(left < right && arr[left] <= pivot)
left += 1;
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
void quick_sort(vector<int> &arr,int left,int right)
{
if(left < right)
{
int mid = partition(arr,left,right);
quick_sort(arr,left,mid-1);
quick_sort(arr,mid+1,right);
}
}
Python
//原地排序版
def partition(li, left, right):
pivot = li[left]
while left < right:
while left < right and li[right] >= pivot: #从右面找比tmp小的数
right -= 1 # 往左走一步
li[left] = li[right] #把右边的值写到左边空位上
while left < right and li[left] <= pivot:
left += 1 # 往右走一步
li[right] = li[left] #把左边的值写到右边空位上
li[left] = pivot # 把基准元素归位
return left # 返回基准元素下标
def quick_sort(li, left, right):
if left<right: # 至少两个元素
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, mid+1, right)
#创建新列表版(数据量小时可用)
def quick_sort(li):
if len(li) <= 1:
return li
else:
pivot = li[0]
left = [x for x in li[1:] if x < pivot]
right = [x for x in li[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
归并排序
文字描述
代码实现
C++
Python
def merge_sort(li):
if(len(li) <= 1):
return li;
else:
mid = len(li) // 2
left = merge_sort(ls[:mid])
right = merge_sort(ls[mid:])
return merge(left,right)
# 有序合并左右两列表
def merge(left,right):
result = []
# 下标置0
i,j = 0,0
while i < len(left) and j < len(right):
# 添加较小的数
if left[i] < right[j]:
result.append(keft[i])
i += 1
else:
result.append(right[j])
j += 1
#添加剩余元素
result += left[i:]
result += right[j:]
return result
堆排序
文字描述
堆排序（Heap Sort）是一种基于比较的排序算法，它利用堆这种数据结构的特性来进行排序。堆是一个近似完全二叉树的结构，并且满足堆的性质：每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。
堆排序的过程包括两个主要步骤：
- 建立堆：将待排序的序列构造成一个最大堆（用于升序排列）或最小堆（用于降序排列）。
- 排序：不断移除堆顶元素（最大或最小值），并将其放到序列的尾部，然后重新调整剩余元素，使其满足堆的性质。
堆排序的时间复杂度为 O(nlogn)，它是一种不稳定的排序算法，适合用于大数据量的排序。由于堆排序在排序过程中不需要额外的存储空间，因此它也是一种原地排序算法1
代码实现
C++
void heapify(vector<int> &arr, int n,int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// 如果左子节点存在且大于根节点，则更新最大值
if(left < n && arr[i] < arr[left])
largest = left;
// 如果右子节点存在且大于当前最大值，则更新最大值
if(right < n && arr[i] < arr[right])
largest = right;
// 如果最大值不是根节点，交换它们，并继续堆化
if(largest != i)
{
swap(arr[i],arr[largest];
heapify(arr,n,largest)
}
}
void heap_sort(vector<int> &arr)
{
int n = arr.size();
// 构建最大堆
for(int i = n/2 -1;i >= 0;i --)
heapify(arr,n,i);
// 一个个从堆顶取出元素
for(int i = n - 1;i >= 0;i --)
{
swap(arr[i],arr[0]);
heapify(arr,i,0);
}
Python
def heapify(arr, n, i): #i为根节点下标
largest = i
left = 2 * i + 1 #左孩子
right = 2 * i + 2 #右孩子
# 如果左子节点存在且大于根节点，则更新最大值
if left < n and arr[i] < arr[left]:
largest = left
# 如果右子节点存在且大于当前最大值，则更新最大值
if right < n and arr[largest] < arr[right]:
largest = right
# 如果最大值不是根节点，交换它们，并继续堆化
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(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[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
Top k 问题
取得前k大的数（部分有序）
代码实现
C++
void heapify(vector<int> &arr, int n,int i)
{
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// 如果左子节点存在且小于根节点，则更新最小值
if(left < n && arr[i] > arr[left])
smallest = left;
// 如果右子节点存在且小于当前最大值，则更新最小值
if(right < n && arr[i] > arr[right])
smallest = right;
// 如果最大值不是根节点，交换它们，并继续堆化
if(smallest != i)
{
swap(arr[i],arr[smallest];
heapify(arr,n,smallest)
}
}
vector<int> top(vector<int> &arr,k)
{
// 构建大小为 k 的最小堆
vector<int> heap(arr.begin(),arr.begin() + k);
for (int i = k / 2 - 1; i >= 0; --i) {
heapify(heap, k, i);
}
// 遍历数组中剩余的元素
for (int i = k; i < arr.size(); ++i) {
if (arr[i] > heap[0]) { // 如果当前元素大于堆顶元素
heap[0] = arr[i]; // 替换堆顶元素
heapify(heap, k, 0); // 重新堆化
}
}
return heap; // 返回包含前 k 个最大元素的堆
}
Python
def heapify(arr, n, i):
smallest = i # 初始化最小元素为根节点
left = 2 * i + 1 # 左子节点的索引
right = 2 * i + 2 # 右子节点的索引
# 如果左子节点存在且小于根节点，则更新最小值
if left < n and arr[smallest] > arr[left]:
smallest = left
# 如果右子节点存在且小于当前最小值，则更新最小值
if right < n and arr[smallest] > arr[right]:
smallest = right
# 如果最小值不是根节点，交换它们，并继续堆化
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i] # 交换
heapify(arr, n, smallest) # 递归地堆化子树
def top_k_elements(arr, k):
# 构建大小为 k 的最小堆
heap = arr[:k]
for i in range(k//2 - 1, -1, -1):
heapify(heap, k, i)
# 遍历数组中剩余的元素
for i in range(k, len(arr)):
if arr[i] > heap[0]: # 如果当前元素大于堆顶元素
heap[0] = arr[i] # 替换堆顶元素
heapify(heap, k, 0) # 重新堆化
return heap # 返回包含前 k 个最大元素的堆
其他排序
希尔排序
文字描述
希尔排序（Shell Sort）是一种基于插入排序的改进算法（分组插入排序），也称为缩小增量排序。它的核心思想是将待排序的数组分割成若干个子序列，每个子序列由相隔一定间隔（称为增量）的元素组成，然后对每个子序列进行直接插入排序。随着排序的进行，增量逐渐减小，直到为1时，整个数组变成一个子序列，再进行一次直接插入排序，完成整个排序过程。
希尔排序的性能优于简单的插入排序，特别是对于大规模的数据排序。这是因为它通过先比较距离较远的元素，而不是相邻的元素，可以快速减少大量的无序情况，从而减少了后续插入排序的工作量。
希尔排序的时间复杂度与增量的选择有关，最坏情况下的时间复杂度为 (O(n^2))，但是对于某些特定的增量序列，时间复杂度可以降低到 (O(n^{1.5})) 或更低。希尔排序是一种不稳定的排序算法，因为在排序过程中可能会改变相等元素的相对位置。
代码实现
C++
void insert_sort_gap(vector<int> &arr,int gap)
{
for(int i = gap;i < arr.size();i++)
{
int key = arr[i];
int j = i - gap;
while(i >= 0 && arr[j] > key)
{
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
void shell_sort(vector<int> &arr)
{
int d = arr.size() / 2;
while(d >= 1)
{
insert_sort_gap(arr,d);
d /= 2;
}
}
Python
def insert_sort_gap(li, gap):
for i in range(gap, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - gap #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 2
桶排序
文字描述
桶排序（Bucket Sort）是一种分布式排序算法，它通过将数组分到一定数量的有序的桶里，然后对每个桶内的元素进行排序，最后将各个桶中的元素依次取出，组成一个有序序列。桶排序适用于待排序数据值域较大但分布比较均匀的情况。
桶排序的基本步骤如下：
- 设置空桶：初始化一定数量的空桶。
- 分配元素：遍历原始数组，根据某种映射关系，将元素分配到对应的桶中。
- 桶内排序：对每个非空的桶进行排序，可以使用不同的排序算法，如快速排序或插入排序。
- 合并桶：按顺序从非空桶中取出元素，放回原始数组，得到有序序列。
桶排序的性能取决于数据的分布、桶的数量以及所使用的内部排序算法。在最佳情况下，当输入数据均匀分布时，桶排序的时间复杂度可以达到 (O(n+k))，其中 (n) 是元素数量，(k) 是桶的数量。桶排序是稳定的排序算法，因为它不会改变相同元素之间的相对顺序。
代码实现
C++
#include <vector>
vector<int> bucket_sort(vector<int>& li, int n = 100, int max_num = 10000) {
vector<vector<int>> buckets(n, vector<int>());
for (int var : li) {
int i = min(var / (max_num / n), n - 1);
buckets[i].push_back(var);
for (int j = buckets[i].size() - 1; j > 0; --j) {
if (buckets[i][j] < buckets[i][j - 1]) {
swap(buckets[i][j], buckets[i][j - 1]);
} else {
break;
}
}
}
vector<int> sorted_li;
for (const auto& buc : buckets) {
sorted_li.insert(sorted_li.end(), buc.begin(), buc.end());
}
return sorted_li;
}
Python
def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里
buckets[i].append(var) # 把var加到桶里边
# 保持桶内的顺序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
计数排序
文字描述
计数排序（Counting Sort）是一种非比较排序算法，主要用于对一定范围内的整数进行排序。它的工作原理是通过计算每个元素的出现次数来确定每个元素的排序位置。计数排序算法特别适合于数据范围不大的场景，因为它的时间复杂度为 (O(n+k))，其中 (n) 是数组长度，(k) 是数据的范围。
计数排序的基本步骤包括：
- 找出待排序数组中的最大值。
- 初始化计数数组，长度为最大值加一，所有计数初始化为0。
- 遍历原始数组，根据数组元素的值作为计数数组的索引，对应计数加一。
- 累加计数数组，使每个元素的计数等于自身及之前所有计数的总和。
- 反向填充目标数组，根据计数数组中的位置信息，将原始数组中的元素放置到正确的位置上。
计数排序是稳定的排序算法，因为相同的元素在排序后会保持它们原始的顺序。但是，如果数据范围 (k) 远大于元素个数 (n)，则计数排序可能不太适用，因为它需要创建一个很大的计数数组，这可能会导致空间浪费。
代码实现
C++
#include <vector>
using namespace std;
void count_sort(vector<int>& li, int max_count = 100) {
vector<int> count(max_count + 1, 0);
for (int val : li) {
count[val]++;
}
li.clear();
for (int ind = 0; ind <= max_count; ind++) {
for (int i = 0; i < count[ind]; i++) {
li.push_back(ind);
}
}
}
Python
def count_sort(li, max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)
基数排序
文字描述
基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序有两种方法：最低位优先（LSD）和最高位优先（MSD）。
- LSD（Least Significant Digit first）：从最低位开始进行排序，适用于位数较短的整数排序。
- MSD（Most Significant Digit first）：从最高位开始进行排序，适用于位数较长的字符串排序或其他需要考虑高位优先的场景。
基数排序的步骤通常如下：
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
- 从最低位或最高位开始，依次进行一次排序。
- 按照每个位数进行排序，可以使用计数排序或桶排序作为子过程。
- 从最低位排序一直到最高位排序完成以后，数列就变成了一个有序序列。
基数排序的时间复杂度为 (O(k \cdot N))，其中 (k) 是数字的最大位数，(N) 是排序元素的个数。空间复杂度为 (O(k + N))，并且基数排序是稳定的排序算法。
代码实现
C++
#include <vector>
void radix_sort(vector<int>& li) {
int max_num = *max_element(li.begin(), li.end());
int it = 0;
while (pow(10, it) <= max_num) {
vector<vector<int>> buckets(10, vector<int>());
for (int var : li) {
int digit = (var / (int)pow(10, it)) % 10;
buckets[digit].push_back(var);
}
li.clear();
for (const auto& buc : buckets) {
li.insert(li.end(), buc.begin(), buc.end());
}
it++;
}
}
Python
def radix_sort(li):
max_num = max(li) # 最大值 9->1, 99->2, 888->3, 10000->5
it = 0
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
# 987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10=9
digit = (var // 10 ** it) % 10
buckets[digit].append(var)
# 分桶完成
li.clear()
for buc in buckets:
li.extend(buc)
# 把数重新写回li
it += 1
Powered by Waline v3.2.1