排序算法

冒泡排序

冒泡排序可视化_哔哩哔哩_bilibili

冒泡排序（英语：Bubble sort）是一种简单的排序算法．由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序．

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换．当没有相邻的元素需要交换时，排序就完成了．

经过 𝑖 次扫描后，数列的末尾 𝑖 项必然是最大的 𝑖 项，因此冒泡排序最多需要扫描 𝑛 −1 遍数组就能完成排序．

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 𝑂(𝑛)．

在最坏情况下，冒泡排序要执行 (𝑛−1)𝑛2 次交换操作，时间复杂度为 𝑂(𝑛2)．

冒泡排序的平均时间复杂度为 𝑂(𝑛2)．

for(int i=1;i<=n;i++){//可以写n-1
    for(int j=1;j<=n-1;j++){
        if(a[j]>a[j+1]){
            swap(a[j],a[j+1]);
        }
    }
}

任务1：补全程序，输出每次交换后的数组

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
   	 for(int j=1;j<=n-1;j++){
    	    if(a[j]>a[j+1]){
   	         swap(a[j],a[j+1]);
  	 		} 
 	  }
      //补全
        
	}   
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

input

10
16 78 90 100 65 14 34 89 1 50

任务2：补全程序，让数组从大到小排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
	int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
   	 for(int j=1;j<=n-1;j++){
    	    if(         ){//补全
   	         swap(a[j],a[j+1]);
  	 		} 
 	  }
	}    
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

input

10
16 78 90 100 65 14 34 89 1 50

任务3：修改程序，让程序对字符串按字典序从小到大排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
   	 for(int j=1;j<=n-1;j++){
    	    if(a[j]>a[j+1]){
   	         swap(a[j],a[j+1]);
  	 		} 
 	  }
        
	}    
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

input

10
Hello
Alice
Bob
alice
Nihao
apple
appll
appla
pear
applE

选择排序

选择排序（英语：Selection sort）是一种简单直观的排序算法．它的工作原理是每次找出第 𝑖 小的元素（也就是 𝐴𝑖..𝑛 中最小的元素），然后将这个元素与数组第 𝑖 个位置上的元素交换．

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 𝑂(𝑛2)．

for(int i=1;i<=n;i++){
    int now=a[i];
    for(int j=i;j<=n;j++){
        if(now>a[j]){
            swap(now,a[j]);
        }
    }
    a[i]=now;
}

任务1：补全程序，输出每次交换后的数组

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
    	int now=a[i];
    	for(int j=i;j<=n;j++){
      	  if(now>a[j]){
      	      swap(now,a[j]);
      	  }
 	  	 }
 	   a[i]=now;
        //补全
	}
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

input

10
16 78 90 100 65 14 34 89 1 50

任务2：补全程序，让数组从大到小输出

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
    	int now=a[i];
    	for(int j=i;j<=n;j++){
      	  if(       ){//补全
      	      swap(now,a[j]);
      	  }
 	  	 }
 	   a[i]=now;
	}
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

我们会在赛后检查代码相似度。