排序和排列——蓝桥杯备考

1.十大排序算法

本次用下面的例题详解这十种排序算法

题目描述

将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。

第二行包含 N 个空格隔开的正整数 ai，为你需要进行排序的数。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

输入
5
4 2 4 5 1
输出
1 2 4 4 5
说明/提示

对于 20% 的数据，有 1≤N≤103；

对于 100% 的数据，有 1≤N≤105，1≤ai≤109。

1.选择排序

效率极低，有O(n2)，但优点在于实现简单，逻辑符合日常思维

#include<iostream>
using namespace std;
int main()
{int n;long long int t = 0;cin >> n;long long int a[10000];for (int i = 0; i < n; i++){cin >> a[i];}int min = 0;for (int i = 0; i < n; i++){min = i;//重置最小值坐标for (int j = i; j < n; j++){if (a[j] < a[min]){min = j;}}t = a[min];a[min] = a[i];a[i] = t;}for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;
}

2.冒泡排序

冒泡排序在最坏的情况下时间复杂度也是O(n2)，但如果是在原数列有序的情况下，能够减少时间复杂度

#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],n;
void selection_sort()
{for (int i = 0; i < n-1; i++){bool swaped = true;for (int j = 0; j < n-i-1; j++){if (a[j] > a[j + 1]){swap(a[j], a[j + 1]);swaped = false;}}if (swaped){break;}}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}selection_sort();for (int i = 0; i < n; i++){cout << a[i] <<" ";}cout << endl;
}

3.插入排序

和冒泡排序一样依靠原数组部分有序来减少时间复杂度，最坏情况下还是O(n2)。

错误示例，意外写成了冒泡排序，通过 swap频繁交换元素，插入排序是不断比较然后一次性插入

#include<iostream>
using namespace std;
int a[100005], n;
void insertion_sort()
{for (int i = 1; i < n; i++)//之所以初值是1，因为要和他的前一位比较，防止溢出{int key = a[i];int j = i - 1;while (j >= 0 && key < a[j]){swap(a[j+1], a[j]);j--;}}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}insertion_sort();for (int i = 0; i < n; i++){cout<< a[i]<<" ";}cout << endl;
}

正确做法

#include<iostream>
using namespace std;
int a[100005], n;
void insertion_sort()
{for (int i = 1; i < n; i++)//之所以初值是1，因为要和他的前一位比较，防止溢出{int key = a[i];int j = i - 1;while (j >= 0 && key < a[j]){a[j + 1] = a[j];j--;}a[j + 1] = key;}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}insertion_sort();for (int i = 0; i < n; i++){cout<< a[i]<<" ";}cout << endl;
}