3214 字内容Markdown
三大基础排序算法详解
汇总一下三大基础排序算法的写法以及时间空间复杂度、稳定性
#排序
汇总一下三大基础排序算法的写法以及时间空间复杂度、稳定性
1-based 下标的冒泡排序,时间复杂度 O(n²),空间 O(1),稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
void bubble_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
bool flag = true;
for (int j = 1; j <= n - i; j++)
if (a[j] > a[j + 1]) {1-based 下标的插入排序,时间复杂度 O(n²),空间 O(1),稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
// 1. 后移法
void insert_sort1(int a[], int n) {
for (int i = 2; i <= n; i++) {
int key = a[i];1-based 下标的选择排序,时间复杂度 O(n²),空间 O(1),不稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
void select_sort(int a[], int n) {
for (int i = 1; i < n; i++){
int idx = i;
for (int j = i+1; j <= n; j++) {
if (a[j] < a[idx])