学习目标

1. 插入排序
2. 快速排序

计算机语言发展历史(一)

程序设计语言的发展经历了机器语言、汇编语言、高级语言三个阶段。第一代计算机语言称为机器语言。计算机只能识别o和1。机器语言就是0/1组成的序列。机器语言是计算机唯一能够直接识别并执行的语言,但不易学习和修改,且不同类型机器的机器语言不同,只适合专业人员使用,现在几乎已经没有人用机器语言直接编程了。

插入排序

● 类比抓牌,打牌时一边抓牌一边按花色和大小插入到恰当的位置,当抓完所有的牌时,手中的牌便是有序的,这排序方法即为插入排序
● 也可以类比插队,其他人已经按身高排好队了,新来的人要根据自己的身高找到合适位置插队
● 插入排序的基本思想:每次将下一个元素插入到已排序序列中正确的位置

插入排序的主要步骤如下:(升序为例)

1. 总共n-1趟(1 <= i <= n-1)
2. 第i趟,需要将第i+1个元素插入到前i个元素组成的有序序列中。
   ①将第i+1个元素存放在临时变量t中
   ②把第j个元素和t的值进行比较(j从i递减到1,逆向)
   ③如果第j个元素的值>t,则将该元素后移一个位置
   ④否则,找到插入位置为j+1,将t的值放在j+1位置

插入排序的核心代码:(升序)

for (int i=1; i <= n-1; i++) {
	int t = a[i+1];
	int j = i;
	while( j>=1 && a[j]>t ) {
		a[j+1]= a[j];//a[j]的值后移到j+1
		j --;// 指针前移
		}//循环终止说明已找到插入位置
		a[j+1]= t;// 插入
}

其中循环可以用for循环

for( j=i;j>=1;j -- ) {
	if(a[j]>t) a[j+1] = a[j];
	else break;
}

· 时间复杂度为O(n2)
· 需要额外的空间来存储当前元素
·插入排序是稳定的排序

插入排序是稳定的排序

例如,初始序列(2,2,1):
2 2 1->2 2 1->1 2 2

第1趟,第二个2不大于第一个2,所以没有发生后移和插入,两个2的顺序没有发生变化。而后面即便有其他的元素的插入,也不会使已排序的元素的前后顺序发生颠倒,所以插入排序是稳定的排序!

为什么冒泡排序、选择排序和插入排序都需要O(n2)的时间?

因为理论上任意两个不同元素都需要比较,共n(n-1)/2次。
是否可以减少比较次数?有没有快一点的比较排序法?
·由C.A.R.Hoare在1960年提出
· 也是基于比较的排序方法
· 平均时间复杂度为O(n log n)
· 是比较快速的排序方法

快速排序

快速排序的基本思想:

● 采用分治的策略,将一个大序列分成两个小序列,然后递归地对这两个小序列进行排序。
● 其核心在于选择一个基准值(pivot),通过一趟排序将待排序列分割成独立的两部分,左边的子序列中是所有 <= 基准值的数,右边部分是所有>=基准值的数,且子序列内部不保证有序:
【 <= 基准值的数 …… 】【>=基准值的数.】
● 继续对两个子序列进行排序,直到全部有序
单趟快排:选基准值并分区

什么是对数

快速排序-扩展

排序算法比较

·n为待排序元素的数量
· 稳定性仅针对本课中该算法的实现方式而言
给定num组数据(1<num <= 100),每组数据包含一个长度n(0<n <= 10000)和n个整数组成的序
列。要求用快速排序法把这些序列的数从小到大排序,然后输出,每组一行。
【输入】多行。第一行为数字num,其后是num组数据。每组由两行组成:第一行为长度n,
第二行为n个整数,数之间空格隔开。
【输出】n行。每行是对应的升序排序后的数,数之间空格隔开。
【输入样例】
1
10
5 4 9 7 6 2 1 3 8 -1
【输出样例】-1 1 2 3 4 5 6 7 8 9

1. 声明qsort函数

void qsort(int a[],int start,int end);

2. 写出主函数

对num组输入的序列:

1. 读入n个数放入数组a[]
2. 调用qsort函数对a[]的数排
3. 输出排序后的a[]
4. 实现你的qsort函数

int main()
{
	int num,n;
	cin>>num;
	int a[n+1]={0};
	for(int i=1;i<=num;i++)
	{
		cin>>n;
		//输入n个数，从下标1开始放 
		for(int j=1;j<=n;j++)
			cin>>a[j];
		//排序 
		qsort(a,1,n);
		//输出
		for(int x=1;x<=n;x++) 
			cout<<a[x]<<" ";
		cout<<endl;
	}
	return 0;
}

实现qsort函数

完整代码

#include<bits/stdc++.h>
using namespace std;

/*函数qsort完成对数组a中指定
范围内元素的快速排序
a:待排序的数组

start: 待排序元素的最小下标
end:待排序元素的最大下标

left:左指针,从左往右移动
right:右指针,从右往左移动
pivot: 基准值
*/
void qsort(int a[],int start,int end);

int main()
{
	int num,n;
	cin>>num;
	int a[n+1]={0};
	for(int i=1;i<=num;i++)
	{
		cin>>n;
		//输入n个数，从下标1开始放 
		for(int j=1;j<=n;j++)
			cin>>a[j];
		//排序 
		qsort(a,1,n);
		//输出
		for(int x=1;x<=n;x++) 
			cout<<a[x]<<" ";
		cout<<endl;
	}
	return 0;
}
void qsort(int a[],int start,int end){
	if(start>=end)	return;//递归出口
	int left=start,right=end,pivot=a[(start+end)/2] ;
	do{
		while(a[left]<pivot) left++;//从左到右找>=pivot的元素
		while(a[right]>pivot) right--;//从右到左找<=pivot的元素
		if(left<=right){//若找到且满足条件，则交换 
			swap(a[left],a[right]) ;
			left++;right--;//跳过发生过交换的元素 
		} 
	}while(left<=right);
	qsort(a,start,right);
	qsort(a,left,end);
}

第k小的数

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

1 2 3 4 5

【输出样例】2

插入排序法

针对长度为n的序列:

1. 输入n个数,放在a
2. 进行插入排序:把第i+1个元素插入合适的位置(1 <= i <= n-1)

①将第i+1个元素存放在临时变量t中
②把第j个元素和t比较(j从i递减到1)
③如果第j个元素的值>t,则将该元素后移一个位置
④否则,将t插入j+1位置
3. 输出第k个数

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n+1]={0};
	//输入n个数，从下标1开始放 
	for(int i=1;i<=n;i++)
		cin>>a[i];
	//插入排序，得到升序的排序 
	for(int i=1;i<=n-1;i++)//n-1趟 
	{
		int t=a[i+1];
		int j=i;
		while(j>=1;&& a[j]>t){
			a[j+1]=a[j];//a[j]的值后移到j+1 
			j--;//指针前移 
		}//循环终止说明已找到插入位置 
		a[j+1]=t;//插入 
	}
	cout<<a[k] ;
	return 0;
}

快速排序法

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

1. 输入n个数,从下标1开始放
2. 调用qsort函数快速排序
3. 输出第k个数

#include<bits/stdc++.h> 
using namespace std;
void qsort(int a[],int start,int end){
	if(start>=end)	return;//递归出口
	int left=start,right=end,pivot=a[(start+end)/2] ;
	do{
		while(a[left]<pivot) left++;//从左到右找>=pivot的元素
		while(a[right]>pivot) right--;//从右到左找<=pivot的元素
		if(left<=right){//若找到且满足条件，则交换 
			swap(a[left],a[right]) ;
			left++;right--;//跳过发生过交换的元素 
		} 
	}while(left<=right);
	qsort(a,start,right);
	qsort(a,left,end);
}
int main()
{
	int n,k,pos;
	cin>>n>>k;
	int a[n+1]={0};
	for(int i=1;i<=n;i++)
		cin>>a[i];
	qsort(a,1,n);
	
	cout<<a[k];
	return 0;
}

本次课程的知识点

1. 插入排序的原理和方法
2. 快速排序的原理和方法
3. 排序练习:快速排序、第k小的数

发牌理牌

【编程挑战】模拟发牌理牌过程。输入牌的张数n(1 <= n <= 24)和每张牌的值。边收牌边整理。把拿到的牌插入合适的位置,使手里的牌从小到大排序。最后输出排序后的数。
【输入】两行,第一行是牌的张数n(1 <= n <= 24),第二行是n每张牌的值,空格隔开。
【输出】一行,排序后的值,空格隔开。
【输入示例】12

14 4 1 5 8 9 10 2 12 13 3 6

【输出示例】1 2 3 4 5 6 8 9 10 12 13 14

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,temp;
	cin>>n;
	int a[n+1]={0};
	cin>>a[1];//输入第一张牌 
	//剩下的牌依次去整理插入排序 
	for(int i=1;i<=n-1;i++)
	{
		cin>>temp;// 先拿在手里
		int j=i;
		while(j>=1 && a[j]>temp){
			a[j+1]=a[j];//a[j]的值后移到j+1
			j--;//指针前移 
		} //循环终止说明已找到插入位置
		a[j+1]=temp;//插入 
	}
	//输出排序结果
	for(int i=1;i<=n;i++) 
		cout<<a[i]<<" " ;
	return 0;
}