所有实例均为以下题干:
请对 n 长数列 a_1,a_2...,a_n从小到大排序并输出结果。1 <= a_i <= 10^9
算法稳定性:“稳定”的算法意味着对于序列中的相等元素,排序后它们的相对顺序不会改变
O(n^2)排序算法
1 <= n <= 10^4
插入排序
简单来说,就是在已经排列好的数列中,插进下一个数———稳定
代码实现:
#include <iostream>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; ++i)
{
//开始插入
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
for(int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}
冒泡排序
当相邻两数成逆序对时,交换两数位置———稳定
代码实现:
#include <iostream>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
bool flag = true;
while (flag)
{
flag = false;
for (int i = 1; i < n; ++i)
{
//交换两数
if (a[i] > a[i + 1])
{
flag = true;
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
for(int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}
选择排序
每次在未排序的序列中找到最小的数放到序列最前方,直到所有数·都被选择过一次———不稳定
代码实现:
#include <iostream>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; ++i)
{
int ith = i;
for (int j = i + 1; j <= n; ++j)
{
if (a[j] < a[ith])
{
ith = j;
}
}
swap(a[i], a[ith]);
}
for(int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}
O(nlogn)排序算法
1 <= n <= 10^6
归并排序
每次将序列一分为二,得到新的有序数列,运用了分治法———稳定
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
int a[1000010], b[1000010], n;
void ms(int a[], int b[], int left, int right)
{
if(left >= right) return ;
int len = right - left, mid = (left + right) / 2;
int left1 = left, right1 = mid;
int left2 = mid + 1, right2 = right;
ms(a, b, left1, right1);
ms(a, b, left2, right2);
int k = left;
while(left1 <= right1 && left2 <= right2)
{
if(a[left1] < a[left2])
b[k++] = a[left1++];
else
b[k++] = a[left2++];
}
while(left1 <= right1) b[k++] = a[left1++];
while(left2 <= right2) b[k++] = a[left2++];
for(k = left; k <= right; k++) a[k] = b[k];
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) b[i] = a[i];
ms(a, b, 1, n);
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
快速排序
冒泡排序的升级版。先选出一个基准数,接着遍历,把比它小的数放它左边,比它大的放它右边——不稳定
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
int a[1000010];
void qs(int a[], int left, int right)
{
if(left > right) return ;
int p = a[left];
int i = left + 1;
int j = right;
while(i <= j)
{
while(i <= j && a[i] <= p) i++;
while(i <= j && a[j] > p) j--;
if(i < j) swap(a[i], a[j]);
}
swap(a[left], a[j]);
qs(a, left, j - 1);
qs(a, j + 1, right);
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
qs(a, 1, n);
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
堆排序
类似于完全二叉树,每次比较父节点与子节点——不稳定
代码如下:
//仅有函数,出自百度
void heapify(int arr[], int idx, int heap_size) {
int largest = idx;
int left_child = 2 * idx + 1;
int right_child = 2 * idx + 2;
if (left_child < heap_size && arr[left_child] > arr[largest])
largest = left_child;
if (right_child < heap_size && arr[right_child] > arr[largest])
largest = right_child;
if (largest != idx) {
swap(arr[idx], arr[largest]);
heapify(arr, largest, heap_size);
}
}
void build_heap(int arr[], int heap_size) {
for (int i = heap_size / 2 - 1; i >= 0; i--)
heapify(arr, i, heap_size);
}
void heapSort(int arr[], int heap_size) {
build_heap(arr, heap_size);
for (int i = heap_size - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heap_size -= 1;
heapify(arr, 0, heap_size);
}
}
特殊排序
希尔排序
按增量分组,每组都执行一次插入排序——不稳定
代码如下:
//由百度app生成
#include <iostream>
#include <vector>
using namespace std;
void shellSort(vector<int> &arr, int n) {
// Start with a large gap, and reduce gap by factor of 2
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do insertion sort for all groups
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
// Main function to test above
int main() {
vector<int> arr = {12, 34, 54, 2, 3};
int n = arr.size();
shellSort(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
计数排序
箱排序(真正的计数排序)
统计每个数的个数——稳定
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3e6,M = 1e7;
int a[N + 5],n,box[M+5];
void counting_sort(int a[],int box[],int n)
{
memset(box,0,sizeof(box));
int maxn = 0,minn = 1e9;
for (int i = 1;i <= n;i++)
{
box[a[i]]++;
minn = min(minn,a[i]);
maxn = max(maxn,a[i]);
}
int cnt = 0;
for (int i = minn;i <= maxn;i++)
{
for (int j = 1;j <= box[i];j++) a[++cnt] = i;
}
}
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
counting_sort(a,box,n);
for (int i = 1;i <= n;i++) printf("%d ",a[i]);
return 0;
}
桶排序
计数排序的升级版——稳定
代码如下:
//由百度app生成
#include <iostream>
#include <vector>
#include <list>
void bucketSort(std::vector<int>& arr, int bucketSize) {
if (arr.empty()) return;
int minValue = *std::min_element(arr.begin(), arr.end());
int maxValue = *std::max_element(arr.begin(), arr.end());
int numBuckets = (maxValue - minValue) / bucketSize + 1;
std::vector<std::list<int>> buckets(numBuckets);
// 分配元素到桶中
for (int i : arr) {
int bucketIndex = (i - minValue) / bucketSize;
buckets[bucketIndex].push_back(i);
}
// 对每个桶进行排序
for (auto& bucket : buckets) {
bucket.sort();
}
// 合并桶回到原数组
arr.clear();
for (auto& bucket : buckets) {
for (int elem : bucket) {
arr.push_back(elem);
}
}
}
int main() {
std::vector<int> data = {5, 3, 2, 4, 1, 6, 10, 8, 7};
int bucketSize = 2; // 可以根据实际情况调整桶的大小
bucketSort(data, bucketSize);
for (int num : data) {
std::cout << num << " ";
}
return 0;
}
基数排序
基数排序属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。(由百度app生成)——稳定
//感谢a5156520, hbqjzx
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000];
void radix_sort(int a[],int size) {
int n;
for(int i=1; i<=100; i=i*10) {
int tmp[1000][10];
memset(tmp,0,sizeof(tmp));
//建立一个1000行,10列的数组,每一列分别代表0~9位数,1000行代表能存放的总个数
for(int j=0;j<size;j++) {
n=(a[j]/i)%10;
tmp[j][n]=a[j];
}
int k=0;
for(int p=0; p<10; p++)
for(int q=0; q<size; q++) {
if(tmp[q][p]!=0)
a[k++]=tmp[q][p];
}
}
}
int main() {
// https://blog.csdn.net/hbqjzx/article/details/109109080
// 代码来源于上面的链接
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%d",&a[i]);
radix_sort(a,n);
for(int i=0; i<n; i++) printf("%d ",a[i]);
printf("\n");
return 0;
}
完结放松
奇奇怪怪的排序,介绍两种
猴子排序(出自看云)
猴子排序 (Bogo Sort) 是个既不实用又原始的排序算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自 Quantum bogodynamics,又称 bozo sort、blort sort 或猴子排序(参见无限猴子定理)。并且在最坏的情况下所需时间是无限的。
睡眠排序(出自博客园——护发师兄)
https://www.cnblogs.com/jonil/p/17784368.html
睡眠排序(Sleep Sort)是一个非常有趣且奇特的排序算法,第一次看到就大吃一惊。睡眠排序并不是一个实际可用于大规模数据排序的算法,而更像是一种编程趣味或者计算机科学的玩笑。原理基于多线程和睡眠的概念,不是传统的比较排序算法。
睡眠排序的主要思想是将待排序的一组整数分配给多个线程,每个线程负责处理一个整数,它们根据整数的值来设置睡眠时间。整数越小,睡眠时间越短,整数越大,睡眠时间越长。当所有线程都完成睡眠后,它们按照睡眠时间的长短排列,从而实现排序。