最近翻了一下大一整理的一些代码,做个小笔记
十大排序是排序里面最经典的了,掌握它其实也不难,只要理解就好了,看不懂就带数演练就好
以下文字解释来自于我的理解,图片来自于网络,如有冒犯,请与我联系删除
小目录:
一.冒泡排序
二.选择排序
三.插入排序
四.希尔排序
五.快速排序
六.桶排序
七.基数排序
八.计数排序
九.归并排序
十.堆排序
一.冒泡排序
算法原理:(小->大)
比较相邻两个数的大小,前一个大于后一个就交换,第一次得到最后一个最大,之后最后一个就不参与比较,直至只剩最后一个元素为止
代码如下:
#include<iostream>
using namespace std;
int main(){
int n,t,a[100];
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
二、选择排序
算法原理:(小->大)
第一次先把里面最大的值的下标记录下来,然后放入最后一位,之后最后一位当作不存在,接着比较剩下的,以此类推
代码如下:
#include<iostream>
using namespace std;
int main(){
int a[10],i,j;
for(i=0;i<10;i++)cin>>a[i];
for(i=0;i<10;i++){
int k=i;//记录下标
for(j=i;j<10;j++)
if(a[k]<a[j])
k=j;
if(k!=i){//符合条件交换
int t=a[i];
a[i]=a[k];
a[k]=t;
}
}
for(i=0;i<10;i++)cout<<a[i]<<" ";
return 0;
}
三、插入排序
算法原理:(小->大)
这个举例子吧
【50,40,70,20,60】从第二个位置开始
第一次:比较50与40,小,往前走,最后结果【40,50,70,20,60】
第二次:70与前一位比较,大,直接结束,放置当前位,最后结果【40,50,70,20,60】
第三次:20与70比较,小,交换得【40,50,20,70,60】,接着再与50比较,换得【40,20,50,70,60】,再与40比较最终得【20,40,50,70,60】
第四次:60与70比较,小,换【20,40,50,60,70】,与50比较,大,停止
结束最终得【20,40,50,60,70】
代码如下:
#include<iostream>
using namespace std;
int n,a[10];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<n;i++){
for(int j=i;j>0;j--){
if(a[j]<a[j-1]){
int t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
else break;
}
}
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
四、希尔排序
算法原理:(小->大)
代码如下:
# include<iostream>
using namespace std;
void shellsort(int a[], int size){
int i, j, gap;
for (gap = size / 2; gap > 0; gap /= 2){ // 每次的增量,递减趋势
for (i = gap; i < size; i++) //每次增量下,进行几组插入排序,如第一步就是(从12,9,73,26,37)5次
for (j = i ; j -gap >= 0 && a[j-gap] > a[j]; j -= gap)// 每个元素组中进行直接插入排序
swap(a[j-gap], a[j]); //交换函数
for(int k=0; k<size; k++) // 输出每轮排序结果
cout<<a[k]<<",";
cout<<endl;
}
}
int main(){
int array [10] = {8,9,1,7,2,3,5,4,6,0};
int len = 10;
cout<<"输入的原始序列: ";
for(int i=0; i<len; i++)cout<<array[i]<<","; // 输出原序列
cout<<endl<<endl;
cout<<" ----希尔排序开始---- " << endl;
shellsort(array,len); // 调用排序函数
return 0;
}
五.快速排序
算法原理:(小->大)
1、从数列中取出一个数作为基准数(x)。
2、将数组进行划分,将比基准数大的元素都移至枢轴右边,将小于等于基准数的元素都移至枢轴左边。
3、再对左右的子区间重复第二步的划分操作,直至每个子区间只有一个元素。
代码如下:
#include<iostream>
using namespace std;
int ssort(int a[],int l,int r){
int i=l,x=a[l];//x为基准数
for(int j=l+1;j<=r;j++){
if(a[j]<=x){
i++;//i的位置前面都是小于等于基准数的
swap(a[i],a[j]);//交换函数,比它小,放左边
}
}
swap(a[i],a[l]);//最终i的位置为基准数的最终位置
return i;
}
void ksort(int a[],int l,int r){
if(l<r){
int i=ssort(a,l,r);
ssort(a,l,i-1);//左右两边继续递归
ssort(a,i+1,r);
}
}
int main(){
int a[100],n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
ksort(a,0,n-1);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
六.桶排序
简单桶排序
算法原理:(小->大)
1、建立好对应的桶
2、把要排序的数组分别放入对应的桶中
3、统计元素在桶中出现的次数
4、按照桶的顺序输出同理的元素
代码如下:
#include <iostream>
#include<cstring>
using namespace std;
int max1=8;//数组中的最大值
int Score[5]={5,3,5,2,8};
void TongSort(int *score,int num){
int a[max1+1];
memset(a,0,sizeof a);//桶的初始化
for(int i=0;i<num;i++){
int temp=score[i];
a[temp]++;
}
for(int i=0;i<max1+1;i++){
for(int j=1;j<=a[i];j++)
cout<<i<<" ";
}
}
int main(){
int num=5;
TongSort(Score,num);
return 0;
}
基本桶排序
算法原理:(小->大)
设置一个定量的数组当作空桶;
遍历输入数据,并且把数据一个一个放到对应的桶里去;
对每个不是空的桶进行排序;
从不是空的桶里把排好序的数据拼接起来。
代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bksort(float A[],int l,int h){
int size = h-l+1;
vector<float> b[size];//有size个数据,就分配size个桶
for(int i=l;i<=h;i++){
int bi = size*A[i];//元素A[i]的桶编号
b[bi].push_back(A[i]);//将元素A[i]压入桶中
}
for(int i=0;i<size;i++)
sort(b[i].begin(),b[i].end());//桶内排序
int idx = l;//指向数组A的下标
for(int i=0;i<size;i++){//遍历桶
for(int j=0;j<b[i].size();j++){//遍历桶内元素
A[idx++] = b[i][j];
}
}
}
int main(){
float A[] = {0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
bksort(A,0,9);
for(int i=0;i<10;i++)
cout<<A[i]<<" ";
}
七.基数排序
算法原理:(小->大)
从低位开始排,之后再往前一位,直至最后
代码如下:
#include<iostream>
using namespace std;
void kkk(int a[],int n){
for(int i=1;i<=100;i*=10){
int tmp[20][10]={0};//临时存放的位数地址数组
for(int j=0;j<n;j++){
int t=(a[j]/i)%10;
tmp[j][t]=a[j];//存放在与当前位数相同的数的位置
}
int k=0;
for(int p=0;p<10;p++){
for(int q=0;q<n;q++){
if(tmp[q][p]!=0)
a[k++]=tmp[q][p];//更新数组
}
}
}
}
int main(){
int a[100]={11,99,25,31,51,12,85,123};
int n=8;
kkk(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
八.计数排序
算法原理:(小->大)
记录比当前位小的数的个数n,然后放入另一个数组的第n位储存,如果已经储存了之前相同的数,那就往后挪一位
代码如下:
#include<iostream>
using namespace std;
void kkk(int a[],int len,int b[]){
if(len<1)
return ;
for(int i=0;i<len;i++){
int cc=0;//对第i个数计数,记录比它小的数的个数
for(int j=0;j<len;j++){
if(a[i]>a[j])
cc++;
}
while(b[cc]==a[i])
cc++;//如果有多个相同的往后移位
b[cc]=a[i];
}
}
int main(){
int a[10]={45,12,100,14,12,85,12,45,85,65};
int b[10]={0};
int n=10;
cout<<"before:";
for(int i=0;i<n;i++)cout<<a[i]<<" ";
kkk(a,n,b);
cout<<endl<<"after:";
for(int i=0;i<n;i++)cout<<b[i]<<" ";
return 0;
}
九.归并排序
算法原理:(小->大)
采用分治法,划分最小块,然后相邻比较,之后又跟相邻的比较,看动图就理解了
代码如下:
#include<iostream>
#include <cstdlib>
using namespace std;
void Merge(int A[],int B[], int L, int mid, int R){
int i = L, j=mid+1, k = L;
while(i!=mid+1 && j!=R+1){
if(A[i] > A[j])
B[k++] = A[j++];
else
B[k++] = A[i++];
}
while(i != mid+1)
B[k++] = A[i++];
while(j != R+1)
B[k++] = A[j++];
for(i=L; i<=R; i++)
A[i] = B[i];
}
//内部使用递归
void vvv(int A[], int B[], int l, int r){
int mid;
if(l < r) {
mid= l + (r-l) / 2;//避免溢出int
vvv(A, B, l, mid);
vvv(A, B, mid+1, r);
Merge(A, B, l, mid, r);
}
}
int main(){
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
vvv(a, b, 0, 7);
for(i=0; i<8; i++)cout<<a[i]<<" ";
return 0;
}
十.堆排序
算法原理:(小->大)
先组成一个大顶堆,之后每次输出a[0],从而完成排序
动图演示
代码如下:
#include<bits/stdc++.h>
using namespace std;
void paixu(int a[],int star,int end1){
int dad=star;
int son=dad*2+1;
while(son<=end1){
if(son+1<=end1&&a[son]<a[son+1])//这个判断是否有右孩子,以及左右孩子的大小
son++;//记录较大孩子
if(a[son]<a[dad])
return ;
else{
int t=a[son];
a[son]=a[dad];
a[dad]=t;
dad=son;
son=dad*2+1;
}
}
}
void duipai(int a[],int n){
for(int i=n/2-1;i>=0;i--)//即有孩子的父亲开始,完成大顶堆
paixu(a,i,n-1);
for(int i=n-1;i>0;i--){//将每a[0]放置最后一位代表输出了
int t=a[i];
a[i]=a[0];
a[0]=t;
paixu(a,0,i-1);
}
}
int main(){
int a[10]={10,80,50,20,60,30,90,40,70,100};
int n=10;
duipai(a,n);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
return 0;
}
网友评论