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

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;
}

4.希尔排序

希尔排序是插入排序的改良版，既然插入排序依赖原数组的原本就有序的状态来减少时间复杂度，那么可以用”猜“的方式来减少最糟的无序状态

例如这个图中，假如索引为0和2的状态无序，在普通的插入排序下就需要比较两次，插入一次。如果直接交换的话会节省后续很多时间复杂度。之所以不直接去猜第一位和最后一位，是因为虽然这样一个的空间跨度大，但是这是牺牲其他组别的空间跨度来实现的，所以都差不多了，反而风险更高。