C++数据排序( 附源码 )

一.冒泡排序

原理:自左向右依次遍历,若相邻两数顺序错误,则交换两数.

这样,每一轮结束后,最大/最小的数就会到最后.

Code:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],in; 
void PrintArray(int a[],int n){
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	} 
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	}
	for(int i=1;i<=n-1;i++){
		bool flag=true;
		for(int j=1;j<=n-1;j++){
			if(a[j]>a[j+1]) swap(a[j],a[j+1]),flag=false;
		} 
		if(flag) break; 
	} 
	PrintArray(a,n);
	return 0;
}

我在此使用了函数.

二.选择排序

原理:自左向右依次遍历,选出最大/最小数,放到最前/最后

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1e5+1;
int n,a[N],in; 
void PrintArray(int a[],int n){
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" "; 
	} 
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	}
	for(int i=1;i<=n-1;i++){
		in=i;
		for(int j=i+1;j<=n;j++){
			if(a[j]<a[in]){
				in=j; 
			}			
		} 
		swap(a[in],a[i]);
	} 
	PrintArray(a,n);
	return 0;
}

函数与双指针搭配,非常好用!

三.桶排序

桶排序是最快的排序.

每个数都对应了一个桶,遍历查找,若有该数,桶为true,最后遍历输出(并无真正排序)

但无法创建过多桶(数组爆炸危机)

Code:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],t,Max; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&t);
		a[t]=1;
		Max=max(Max,t); 
	} 
	for(int i=1;i<=Max;i++){
		if(a[i]) cout<<i<<" "; 
	} 
	return 0;
}

但如果一个数有两个呢?如:2个2

升级:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],t,Max; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&t);
		a[t]++;
		Max=max(Max,t); 
	} 
	for(int i=0;i<=Max;i++){
		while(a[i]--) cout<<i<<" "; 
	} 
	return 0;
}

四.插入排序

插入排序,就是你打牌时摸牌并排序啦..

Code:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],in; 
void PrintArray(int a[],int n){
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" "; 
	} 
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	}
	for(int i=2;i<=n;i++){
		int in=i-1,now=i;
		while(in>=1 and a[now]<a[in]){
			swap(a[now--],a[in--]);			 
		} 
	} 
	PrintArray(a,n);
	return 0;
}

还有许多排序,等你去探索...

五.归并排序

#include <cstdio>
#include <malloc.h>
 
#define maxn 1000001

int a[maxn];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void MergeSort(int *nums, int l, int r) {
    int i, mid, p, lp, rp;
    int *tmp = (int *)malloc( (r-l+1) * sizeof(int) );    // (1)  
    if(l >= r) {
        return ;                                          // (2) 
    }
    mid = (l + r) >> 1;                                   // (3) 
    MergeSort(nums, l, mid);                              // (4) 
    MergeSort(nums, mid+1, r);                            // (5) 
    p = 0;                                                // (6) 
    lp = l, rp = mid+1;                                   // (7) 
    while(lp <= mid || rp <= r) {                         // (8) 
        if(lp > mid) {
            tmp[p++] = nums[rp++];                        // (9) 
        }else if(rp > r) {
            tmp[p++] = nums[lp++];                        // (10) 
        }else {
            if(nums[lp] <= nums[rp]) {                    // (11) 
                tmp[p++] = nums[lp++];
            }else {
                tmp[p++] = nums[rp++];
            }
        }
    }
    for(i = 0; i < r-l+1; ++i) {
        nums[l+i] = tmp[i];                               // (12) 
    } 
    free(tmp);                                            // (13) 
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        MergeSort(a, 0, n-1);
        Output(n, a);
    }
    return 0;
} 

彩蛋:

求一数是否是完全平方数(int范围内)

bool sq(int a){
	return int(sqrt(a))*int(sqrt(a))==a;
} 

需导入cmath头文件!