编程奇境：C++之旅，从新手村到ACM/OI算法竞赛大门（武器：排序算法）

引言

现在你已经拥有了c++的基础语法知识，人物已经有了基本属性，那么想要打怪，手里必须要有趁手的武器，各种算法就是手中的武器，要根据怪物的不同特性来选择不同的武器。本章节讲的就是新手第一把武器：排序算法。

所谓排序算法就是把一些乱序的序列按照从小到大或从大到小进行排序，是竞赛和生活中非常常见的一种算法。

一般有八大排序算法：

1. 直接插入排序
2. 希尔排序
3. 简单选择排序
4. 堆排序
5. 冒泡排序
6. 快速排序
7. 归并排序
8. 桶排序/基数排序

但是为了方便新人们入门，我们只先讲最常见的冒泡排序。

学习和掌握这些排序算法，不仅仅是记忆代码那么简单，更重要的是理解它们背后的逻辑和思想。这将帮助你在未来的编程之旅中，面对更加复杂的怪物和难题时，能够迅速挑选出最适合当前场景的“武器”，以智慧和策略，一步步揭开数据世界的奥秘，成为真正的编程高手。

冒泡排序

时间复杂度：O(n^2)

冒泡排序，想象一下你手上有一串彩色的气泡，它们代表着一组数字，但是这些气泡乱了顺序，你需要让它们按照大小整齐排列。怎么办呢？你开始轻轻地吹每一个气泡，让相邻的两个气泡相互比较大小，如果前面的气泡比后面的还要大，它们就会互换位置，“咕咚”一声，大的气泡就像被吹到了后面。就这样，一轮轮吹过去，每一圈结束后，最大的气泡就会自然而然地“浮”到最右边。接着，你再次从头开始吹，只不过这次可以少吹一个已经到位的大气泡，因为你知道它已经是最大的了。这个过程重复，直到所有的气泡都乖乖地按大小顺序排列好了。

#include <iostream>
using namespace std;
 
void bubbleSort(int arr[], int n) {
    // 外层循环控制需要进行几轮比较
    for (int i = 0; i < n - 1; i++) {
   
        // 内层循环负责具体的比较和交换操作
        for (int j = 0; j < n - 1 - i; j++) {
            // 如果前一个元素大于后一个元素，则交换它们
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);//swap为交换函数，swap(a,b)交换a和b的值
                
            }
        }
        
    }
}
 
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n =7;
    bubbleSort(arr, n);
    cout << "排序后的数组: \n";
    for(int i=0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

sort()函数 

时间复杂度:O(nlogn)

古代有弓箭，现代有步枪，弓箭虽然能杀敌，但是手动攻击速度很慢，步枪则是自动，突突突贼快。前面说的冒泡排序就是手动排序过程，对于一个数组要写好几行代码才能排序完成，并且时间复杂度为O(n^2)较高。

现在介绍一个自动挡排序，sort()函数。

sort(数组名+第一个下标,数组名+需要排序的个数)

//从小到大排序
//如果有一个数组，从0开始输入，有n个
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	 } 
	 sort(a,a+n);
	
	//如果有一个数组，从1开始输入，有n个
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	 } 
	 sort(a+1,a+n+1);

 那如果想要从大到小怎么办呢？

需要添加一个自己写的bool类型的cmp函数来控制。

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y)
{
	return x>y;//从大到小 
}
int main()
{
	//如果有一个数组，从0开始输入，有n个
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	 } 
	 sort(a,a+n,cmp);
	
	//如果有一个数组，从1开始输入，有n个
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	 } 
	 sort(a+1,a+n+1,cmp);
	return 0;
}

这样一来是不是简单多了呢，好几行的代码直接压缩成一行就可以了。通常排序操作是在一个题目中一个很小的部分，如果排序需要自己手写那么长，会使得代码可读性变低并且降低写题速度。

 练习场

P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1271 【深基9.例1】选举学生会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1781 宇宙总统 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1059 [NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1093 [NOIP2007 普及组] 奖学金 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1068 [NOIP2009 普及组] 分数线划定 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1051 [NOIP2005 提高组] 谁拿了最多奖学金 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

白看不如一练，只有实践才是进步最快的方式，更要独立思考，如果想不出来了就看题解，会有眼前一亮的感觉。好啦，今天就到这里吧。下一期再见，记得给专栏点个关注，明天接着来哦~