内排序

2020-07-08 13:20:00 # ACM

各种内排序的性能

直接插入排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
} 

void InsertSort(){
	for(int i=1;i<len;i++){
		if(p[i]<p[i-1]){ // 该点数据 比 有序区的最后一个数据即最大的数据 大 
			int t = p[i]; // 记录该点数据 
			int j = i; // 记录该点下标 
			do{ // 有序区元素一一右移直到找到合适位置 
				p[j] = p[j-1];
				j--;
			} while(j>0&&t<p[j-1]);
			p[j] = t; // 放入记录的数据 
		}
	}
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	InsertSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1 

output:
1 2 3 4 5 6 7 8 9
*/

折半插入排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
} 

void BinInsertSort(){
	for(int i=1;i<len;i++){
		if(p[i]<p[i-1]){ // 该点数据 比 有序区的最后一个数据即最大的数据 大 
			int t = p[i]; 
			int l = 0 ,r = i-1;
			while(l<=r){ // 二分查找插入点 
				int mi = (l+r)/2;
				if(t>=p[mi]) l = mi+1;
				else r = mi-1;
			}
			for(int j=i;j>r;j--) p[j] = p[j-1]; //  插入点后数据后移 
			p[r+1] = t;
		}
	}
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	BinInsertSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

希尔排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void ShellSort(){
	int d = len/2;
	while(d>=1){
		// 对相邻 d 位置的元素组直接插入排序 
		for(int i=d;i<len;i++){
			int t = p[i];
			int j = i-d;
			while(j>=0&&t<p[j]){
				p[j+d] = p[j];
				j -= d;
			}
			p[j+d] = t;
		}
		d/=2;
	}
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	ShellSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

冒泡排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void BubbleSort(){
	int exchange; 
	for(int i=0;i<len-1;i++){
		exchange = 0; // 记录是否有交换记录 
		for(int j=len-1;j>i;j--){ // 将无序区最小的值交换到有序区的顶端 
			if(p[j]<p[j-1]){
				exchange = 1;
				int t = p[j];
				p[j] = p[j-1];
				p[j-1] = t;
			}
		}
		// 若无交换记录 则此时无序区已有序 
		if(exchange == 0) return;
	}
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	BubbleSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

快速排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

// 左闭右也闭 
void QuickSort(int s,int e){
	if(s>=e) return;
	int i = s ,j = e;
	// 一次划分 
	int t = p[i];
	while(i<j){
		while(j>i&&p[j]>=t) j--;
		p[i] = p[j];
		while(i<j&&p[i]<=t) i++;
		p[j] = p[i];
	}
	p[i] = t;
	// 左右递归 
	QuickSort(s,i-1);
	QuickSort(i+1,e);
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	QuickSort(0,len-1);
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

简单选择排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void SelectSort(){
	for(int i=0;i<len-1;i++){
		int k = i;
		for(int j=i+1;j<len;j++){ // 得到区间 i ~ len-1 的最小值下标 
			if(p[j]<p[k]) k = j;
		}
		if(i!=k){ // 交换 
			int t = p[k];
			p[k] = p[i];
			p[i] = t;
		}
	}
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	SelectSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

堆排序

基本思路

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[11];

void input(){
	for(int i=1;i<=len;i++) scanf("%d",&p[i]);
}

void sift(int low,int high){ // 调整堆 
	int i = low ,j = 2*i;
	int t = p[i];
	while(j<=high){
		if(j<high&&p[j+1]>p[j]) j++; // j 指向大孩子 
		if(p[j]>t){ // 父亲小 
			p[i] = p[j];
			i = j;
			j = 2*i;
		}
		else break;
	}
	p[i] = t;
}

void HeapSort(){
	for(int i=len/2;i>=1;i--){ // 初始化堆 
		sift(i,len);
	}
	for(int i=len;i>=2;i--){ // 将最大堆顶元素置于数组后边 
		int t = p[1];
		p[1] = p[i];
		p[i] = t;
		sift(1,i-1); // 调整 
	}
}

void output(){
	for(int i=1;i<=len;i++) printf("%d ",p[i]);
}

int main() {
	input(); // 用数组表示二叉树 
	HeapSort();
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

二路归并排序

基本思路

啊这图好啊

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
	for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void Merge(int low,int mid,int high){ // 相邻两个有序子序列归并成一个 
	int i = low ,j = mid+1 ,k = 0; // i ,j 分别为 1 ,2 段下标 
	int *r;
	r = (int*)malloc((high-low+1)*sizeof(int));
	while(i<=mid&&j<=high){
		if(p[i]<p[j]) r[k++] = p[i++];
		else r[k++] = p[j++];
	}
	while(i<=mid) r[k++] = p[i++];
	while(j<=high) r[k++] = p[j++];
	for(i=low,k=0;i<=high;i++,k++)
		p[i] = r[k];
	free(r);
}

void MergeSort(int l,int r){ // 左闭右闭 
	if(l>=r) return;
	int mid = (l+r)/2;
	MergeSort(l,mid);
	MergeSort(mid+1,r);
	Merge(l,mid,r);
}

void output(){
	for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
	input();
	MergeSort(0,len-1);
	output();
	
	return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

基数排序

基本思路

嘛… 是桶没错了

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output

const int maxn = 8; // 待排序的元素个数 
const int maxw = 3; // 位数最大值 236为 3，1233为 4 
const int maxj = 10; // 进制最大值 10进制则为 10 ，16进制为 16
 
struct node{
	char val[maxw]; // 用字符串存储数据 
	node *next; 
}*p,*head[maxj],*tail[maxj];

void input(){ // 带头结点尾插法建表 
	node *t,*r;
	p = (node*)malloc(sizeof(node)); // 创建头节点 
	r = p; // 始终指向尾节点 ，开始时指向头节点 
	for(int i=0;i<maxn;i++){
		t = (node*)malloc(sizeof(node)); // 创建数据节点 
		scanf("%s",t->val); // 输入数据 
		r->next = t; // 将 数据节点 t 插在 r 之后 
		r = t; // r 指向尾节点 
	}
	r->next = NULL; // 尾节点 指向 NULL 
}

void RadixSort(){
	p = p->next; // 指向头节点下一个带有数据的指针 
	node *tt;
	for(int i=maxw-1;i>=0;i--){ // 从最低位开始 
		for(int j=0;j<maxj;j++) // 初始化各个链队首尾指针 
			head[j] = tail[j] = NULL;
		while(p!=NULL){
			char k = p->val[i] - '0'; // 找到第 k个链队 
			if(head[k]==NULL){
				head[k] = p;
				tail[k] = p;
			}
			else{
				tail[k]->next = p;
				tail[k] = tail[k]->next;
			}
			p = p->next;
		}
		p = NULL;
		for(int j=0;j<maxj;j++){ // 对每个链表进行串联 
			if(head[j]!=NULL){
				if(p==NULL){
					p = head[j];
					tt = tail[j];
				}
				else{
					tt->next = head[j];
					tt = tail[j];
				}
			}
		}
		tt->next = NULL;
	} 
}

void output(){
	while(p!=NULL){
		printf("%s ",p->val);
		p = p->next;
	}
}

int main() {
	input();
	RadixSort();
	output();
	
	return 0; 
}

/*
input:
369 367 167 239 237 138 230 139

output:
138 139 167 230 237 239 367 369

*/

2020-07-08 13:20:00 # ACM