c/c++——排序

排序

1.sort函数排序

我们可以使用头文件 中的 sort 函数对数组进行排序。

(1)顺序排序

#include <cstdio>
#include <functional>
#include <algorithm>
const int N = 1007;
int a[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    //默认从小到大排序，第一个参数是待排序中第一个元素的地址，第二个参数是最后一个元素的地址的下一个位置
    std::sort(a+1, a+n+1, std::greater<int>());
    for (int i = 1; i <= n; ++i)
        printf("%d ", a[i]);
    return 0;
}

输入数据 2

5
3 7 1 0 4

输出数据 2

7 4 3 1 0

（2）

奇数在前 偶数在后

奇数从小到达 偶数从大到小

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1007;
int a[N];
bool cmp(const int &a, const int &b){
	if(a%2==1 && b%2==0) return true; //奇数在前 偶数在后
	if(a%2==1 && b%2==1 && a<b) return true; //奇数从小到大
	if(a%2==0 && b%2==0 && a>b) return true; //偶数从大到小
	return false; 
}
int main(){
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", a+i);
	//第三个参数是比较函数名
	std::sort(a+1, a+n+1, cmp);
	for(int i=1; i<=n; i++)
		printf("%d ", a[i]);
	return 0;
}

输入数据 3

10
1 2 3 4 5 6 7 8 9 10

输出数据 3

1 3 5 7 9 10 8 6 4 2

2.选择排序

时间复杂度：

最好：O*(n)，最坏：O(*n^2)

不稳定：无法保证相等的两个元素相对位置不变

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1007;
int a[N];
int main(){
	int n, i, id, j, t;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", a+i);
	for(i=1; i<=n; i++){
		id = i;
		//寻找最小值 将最小值与第i个数交换
		for(j=i+1; j<=n; j++)
			if(a[j]<a[id]) id = j;
		//若当前值即为最小值就不进行交换 否则交换
		if(id!=i)
			t=a[id], a[id]=a[i], a[i]=t;
	}
	for(int i=1; i<=n; i++)
		printf("%d ", a[i]);
	return 0;
}

输入数据 4

10
8 2 5 9 7 1 3 4 6 0

输出数据 4

0 1 2 3 4 5 6 7 8 9

3.插入排序

时间复杂度：

最好：O*(n)，最坏：O(*n^2)

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1007;
int a[N];
int main(){
	int n, i, j, k;
	scanf("%d", &n);
	for(i=1; i<=n; i++) scanf("%d", a+i);
	for(i=2; i<=n; ++i){
		//先插入第一个数 再将第二个数和第一个数比较 
		//把大于a[i]的数都往后挪
		for(j=i-1, k=a[i]; j && a[j]>k; --j)
			a[j+1] = a[j];
		a[j+1] = k;
	}
	for(int i=1; i<=n; i++) printf("%d ", a[i]);
	return 0;
}

4.冒泡排序

#include <stdio.h>
int a[607];
int main(){
	int n, i, j, t;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
	//冒泡排序
	for (i = n-1; i; --i) {
        for (j = 1; j <= i; ++j)
            //轻者上浮 浊者下沉
            if (a[j] > a[j+1])
                t = a[j], a[j] = a[j+1], a[j+1] = t;
	}
	for(int i=1; i<=n; i++)
		printf("%d ", a[i]);
	return 0;
}

5.归并排序

逆序对个数

#include <iostream>
typedef long long LL;
const int N = 1e5 + 7;
int a[N], b[N];
LL msort(int lo, int hi) {
    if (lo == hi) return 0;
    int mid = (lo + hi) >> 1;
    //ans记录逆序对的个数
    LL ans = msort(lo, mid) + msort(mid+1, hi);
    //i合并后的新编号，j左半边的编号，k右半边的编号
    for (int i=lo, j=lo, k=mid+1; i <= hi; ++i) {
        if (j > mid) { b[i] = a[k++]; continue; }
        if (k > hi) { b[i] = a[j++]; continue; }
        if (a[j] <= a[k]) { b[i] = a[j++]; continue; }
        ans += mid - j + 1, b[i] = a[k++];
    }
    for (int i = lo; i <= hi; ++i) a[i] = b[i];
    return ans;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    LL ans = msort(1, n);
    printf("%lld", ans);
    return 0;
}

输入数据

3 2 1 8 9 6 7 4 5 0

输出数据

24