学习目标

1. 排序的概念
2. 冒泡排序
3. 选择排序

未来新型计算机

基于集成电路的计算机短期内还不会退出历史舞台。但一些新的计算机正在跃跃欲试地加紧研究。光学计算机:利用光子取代电子进行数据运算、传输和存储。
DNA计算机:以编码的DNA序列为运算对象,通过分子生物学的运算操作以解决复杂的数学难题。
量子计算机:利用处于多现实态下的原子进行运算的计算机,这种多现实态是量子力学的标志。

排序

● 在现实生活中,我们收集到的数据大多是无序的
· 而我们需要使之有序,也就是进行排序
· 排序作为重要的算法工具,可以将无序变有序,使问题更好的得到处理

例如,若一个序列是有序的,我们可以在O(1)时间内查找第k小的元素,但对于
无序序列就很困难。

排序算法

基本的排序算法有:比较排序\非比较排序
◆冒泡排序、选择排序、插入排序
◆快速排序
◆计数排序等
以上类型中,除了计数排序,其他都是基于比较的排序
● 不同的排序算法适用于不同场景,各有特点
● 所以上述排序方法尽可能都要掌握

排序算法的稳定性

● 排序算法可以分为稳定排序和不稳定排序。
● 如果任意两个相等的数据在排序前后的顺序不改变,那么这种
排序算法就是稳定的
例如
原始序列:12 34 10 23 45 12

稳定排序:10 12 12 23 34 45

不稳定排序:10 12 12 23 34 45

冒泡排序

● 冒泡排序(Bubble Sort)来源于对日常生活的观察,汽水中常常有许多小小的气泡,哗
啦哗啦飘到上面来
● 排序思路是对相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下
来,最大(小)值就会排列在一端。整个过程如同气泡冒起,因此被称作冒泡排序
●冒泡排序是一种基础的,基于比较的排序方法

对于长度为n的序列(有效数值存储在下标1~n):
1.扫描序列n-1次
2.第i(1 <= i <= n-1)次扫描,从前往后比较相邻的两个元素,既比较a[j与a[j+1],其中1 <= j <= n-i
3.每次比较时,如果a[j]>a[j+1],则交换它们,否则不做操作

冒泡排序的核心代码:

(升序)
// 扫描序列n-1次
for (int i=1; i <= n-1; i++) {
// 第i趟,进行n-i次比较
	for (int j=1; j <= n-i; j++) {
// 如果前一个元素大于后一个元素,则交换它们
		if (a[j] > a[j+1]) {
			swap (a [j] , a [j+1] ) ;

}

swap是C语言提供的函数,用于交换两个变量的值。
· 时间复杂度为O(n2)
· 若相邻元素值相等,不会进行交换,所以冒泡排序是稳定的排序

冒泡排序的特性

● 不管序列中的数怎么排列,冒泡排序时都要进行固定次数的比较
· n-1次扫描
· 每次进行n-i次比较(1 <= i <= n-1)
总比较次数=(n-1)+(n-2)+…+2+1=n(n-1)/2
● 但是交换的次数,是由数的排列情况决定
例如,
1、2、3 扫描2次,比较3次,交换0次
3、2、1 扫描2次,比较3次,交换3次
可优化!只需要扫描1次即可完成排序!

冒泡算法的优化

某次扫描没有发生元素交换,说明序列已经有序

bool flag = false;// 记录本次扫描是否发生过交换
for (int i=1; i <= n-1; i++) {
	flag = false;// 初始值
	for (int j=0; j <= n-i-1; j++) {
		if (a[j] > a[j+1]) {
			swap (a [j] , a [ j+1] ) ;
			flag = true;// 记录发生交换
		}
	}
	if(flag == false)// 没有发生交换则已有序,跳出循环
		break;
}

最优情况下初始序列已经有序,只进行了1次扫描。最优时间复杂度为O(n)
最差情况下初始序列反序,需要进行n-1次扫描。最差时间复杂度为O(n2)

选择排序

对于长度为n的序列(有效数值存储在下标1~n):

1. 扫描序列n-1次
2. 第i(1 <= i <= n-1)次扫描,找到a[i]、a[i+1]、 … a[n]中最小的元素a[pos]
3. 交换a[i]与a[pos]

选择排序的核心代码:

(升序)
// 扫描序列n-1次
for (int i=1; i <= n-1; i++) {
	int pos=i;
	for (int j=i+1; j <= n; j++) {
		//找到a[i]~a[n]中最小的元素的位置
		if (a[j] < a[pos])
			pos = j;
		}
		swap(a[i],a[pos]); // 交换
	}

1. 时间复杂度为O(n2)
2. 需要额外的空间来存储找 到的最小元素(的位置)
3. 选择排序是不稳定的排序
   
   | 方法 | 时间复杂度 | 是否稳定 | 是否比较排序 |
   | -------- | ---------- | -------- | ------------ |
   | 冒泡排序 | O(n²) | √ | 是 |
   | 选择排序 | O(n²) | × | 是 |

· n为待排序元素的数量
· 稳定性仅针对本课中该算法的实现方式而言

第k小的数

给定一个长度为n(0<n <= 10000)的序列,保证每一个序列中的数字a[i]是正整数,编程求出整个序列中第k小的数字。(O<k <= n)
【输入】第一行为2个数n,k(含义如上题)第二行为n个数,表示这个
序列。
【输出】第k小的数
【输入样例】
5 2
1 23 4 5

【输出样例】2

思路

先排序、后查找
思路1:

1. 进行冒泡排序
2. 输出第k小的数

思路2:

1. 进行选择排序(选到k个数即可,无需完成全部)
2. 输出第k小的数

第k小的数-冒泡排序法

针对长度为n的序列a[]:

1. 输入n个数,从下标1开始放
2. 冒泡排序,得到小到大的排序
   ① 扫描a序列n-1次
   ② 第i(1 <= i <= n-1)次扫描,从前往后比较相邻的两个元素,既比较a[]与a[j+1], 其中1 <= j <= n-i
   ③每次比较时,如果a[j]>a[j+1],则交换它们,否则不做操作
3. 输出第k个数

#include<iostream>
using namespace std;
int a [10001] = {0};
int main() {
		int n, k;
		cin>>n>>k;
		for(int i=1; i <= n; i++)
			cin>>a[i];
		for(int i=1; i <= n-1; i++) {
			for(int j=1; j <= n-i; j++) {
				if (a[j]>a [j+1]) {
					swap (a[j], a[j+1]);
		cout << a[k];
		return 0;
}

【注意】总数0<n <= 10000,序列太长,建议a[]定义为全局变量,长度为10000+1.

【完整代码示例】基于冒泡排序的代码

#include<iostream>
using namespace std;
int a[10001]={0};//建议大数组(超过1000个元素)定义为全局变量
 //如果不显式初始化,全局变量会自动进行初始化操作,全部都会成为 0
int main(){
	int n,k;
	cin>>n>>k;
	//输入n个数,从下标1开始放
	for (int i=1; i <= n; i++)
		cin>>a[i];
	// 冒泡排序,得到小到大的排序
	for (int i=1; i <= n-1; i++) {
		for (int j=1; j <= n-i; j++) {
			if (a[j]>a[j+1]){//判断是否逆序
				swap (a [j] , a [j+1]) ;
				}
			}
		}
	// 输出第k个数
	cout << a[k];
	return 0;
}

【注意】双重循环各自的循环范围

【思考】这个算法的时间复杂度是?
O(n2)

第k小的数-选择排序法

针对长度为n的序列a[]:

1. 输入n个数,从下标1开始放
2. 选择排序(到k个数为止)
   ① 扫描序列k次
   ②第i(1 <= i <= k)次扫描,找到a[j]、a[i+1]、 …… a[n]中最小的元素a[pos]

③ 交换a[i]与a[pos]
3. 输出第k个数

#include<iostream>
using namespace std;
int a [10001] = {0};
int main() {
	int n, k, pos;
	cin>>n>>k;
	for (int i=1; i <= n; i++)
		cin>>a[i];
	for(int i=1; i <= k; i++) {
		pos=i;
		for(int j=i+1; j <= n; j++)
			if (a[j] < a[pos])
				pos = j;
		}
		swap(a[i],a[pos]); // 交换
	}
	cout << a[k];
	return 0;

【完整代码示例】基于选择排序的代码

int main () {

#include<iostream>
using namespace std;
int a[10001];//建议大数组(超过1000个元素)定义为全局变量
//全局变量会自动进行初始化操作,全部都会成为0
int main(){
	int n, k,pos;
	cin>>n>>k;
	//输入n个数,从下标1开始放
	for (int i=1; i <= n; i++)
		cin>>a[i];
	// 选择排序(到k个数为止)
	for (int i=1; i <= k; i++) {
		pos=i;
		for (int j=i+1; j <= n; j++) {
		//找到a[i]~a[n]中最小的元素的位置
			if (a[j] < a[pos])
				pos = j;
		}
		swap(a[i],a[pos]);// 交换
	}
	// 输出第k个数
	cout << a[k] ;
	return 0;
}

【注意】双重循环各自的循环范围

【思考】这个算法的时间复杂度是?
O(nk)
由于0<k <= n,所以O(nk)的复杂度<= O(n2)。

车厢重组

在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工
发现桥的长度最多能容纳两节车厢,如果将桥旋转180度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后,火车站决定将这一工作自动化,其中一项重要的工作是编一个程序,输入初始的车厢顺序,计算最少用多少步就能将车厢排序。
【输入】输入有两行数据,第一行是车厢总数N(不大于10000),第二行是N个不同的数表
示初始的车厢顺序。
【输出】一个数据,表示最少的旋转次数。
【输入样例】
4
4 3 2 1

【输出用例】6
读题可知,这是一个需要有序地、不重复地
对相邻元素进行比较+交换
达到排序目的的问题

● 可以用冒泡排序算法进行模拟
● 在冒泡过程中统计交换次数
长度n的车厢编号序列a[],从a[1]开始放第1个车厢编号:

1. 输入n个车厢号到a[]
2. 冒泡排序并统计次数
   ①扫描a序列n-1次
   ②第i(1 <= i <= n-1)次扫描,从前往后比较相邻的两个元素,既比较aj]与a[j+1],其中1 <= j <= n-i
   ③每次比较时,如果a[j]>a[j+1],则交换它们并统计次数s,否则不做操作

#include<iostream>
using namespace std;
int a[10001];

int main() {
	int n, s=0;
	cin>>n;
	for (int i=1; i <= n; i++)
		cin>>a[i];
	for(int i=1; i <= n-1; i++) {
		for(int j=1; j <= n-i; j++) {
			if (a [j]>a[j+1]) {
				swap (a[j],a[j+1]);
				s++;//统计交换次数
				}
			}
		}
	cout << s；
	return 0;
}

在C++中,全局变量如果不显式初始化,将自动初始化为0。

【完整代码示例】

#include<iostream>
using namespace std;
int a[10001];// 建议大数组(超过1000个元素)定义为全局变量
// 全局变量会自动进行初始化操作,全部都会成为 0
int main() {
	int n,s=0;
	cin>>n;
	for (int i=1; i <= n; i++)
		cin>>a[i];//输入n个车厢号
	for (int i=1; i <= n-1; i++){// 用冒泡排序模拟相邻车厢的交换
		for (int j=1; j <= n-i; j++) {
			if (a[j]>a[j+1]){//判断车厢号是否逆序
				swap (a[j] , a[j+1]) ;
				s++;//统计车厢旋转的次数
				}
			}
	}
	cout << s;//最少的旋转次数
	return 0;
}

【注意】如果a[]定义成main函数的局部变量,请确保对数组进行显式的初始化:int a[10001]={0};

【挑战一下】试着改写成优化的冒泡算法

#include<iostream>
using namespace std;
int a[10001];// 建议大数组(超过1000个元素)定义为全局变量
// 全局变量会自动进行初始化操作,全部都会成为0
int main(){
	int n,s=0:
	bool flag;
	cin on;
	for (int i=1; i <= n; i++)
		cin>>a[i];//输入n个车厢号
	for_(int i=1;i <= n-1; i++){//用冒泡排序模拟相邻车厢的交换
		flag = false;
		for tint j-i, j <- n-i; j++) {
			if (a[j]>a[j+1]){//判断车厢号是否逆序
				swap (a [j] , a[j+1]) ;
				S++://统计车厢旋转的次数
				flag = true;
				}
			}
		if(!flag)
		break;
	}
	cout << s;//最少的旋转次数
	return 0;
}

本次课程的知识点

1. 排序的概念
2. 排序的稳定性
3. 冒泡排序的原理和方法
4. 选择排序的原理和方法
5. 排序练习:第k小的数、车厢重组
   
   

跳绳比赛

【编程挑战】学校举行1分钟跳绳比赛,初赛10人一小组,前三名可以参加决赛。试编一程序,输入小组内所有同学的跳绳次数,按次数由多到少的顺序输出前三名的跳绳次数。
【输入】10个人的跳绳次数
【输出】前三名的跳绳次数(由多到少的顺序)
【输入样例】126 80 98 158 204 200 122 135 143 100
【输出样例】204 200 158
【提示】推荐用选择排序

#include<iostream>
using namespace std;
int main(){
	int a[11]={0};
	int pos;
	//输入10个数,从下标1开始放
	for (int i=1; i <= 10; i++)
		cin>>a[i];
	// 选择排序(前3个数)
	for (int i=1; i <= 3; i++) {
		pos=i;
		for (int j=i+1; j <= 10; j++) {
			//找到a[i]~a[n]中最大的元素的位置
			if (a[j] > a[pos])
				pos = j;
		}
		swap (a[i], a[pos]) ; //交换
	}
	// 输出前3个数
	cout << a[1] << " " << a[2] << " " << a[3];
	return 0;
}

【注意】每次选择最大的值交换到未排序
区间的头部。