#include <iostream>
using namespace std;
//冒泡排序
void mSort(int a[],int n);
//选择排序
void SelectSort(int a[],int n);
//插入排序
void InsertSort(int a[], int n);
int main(){
int n;
cin>>n;
int a[n];
for(int i=0; i<n; i++){
cin>>a[i];
}
//排序
// mSort(a,n);
// SelectSort(a,n);
InsertSort(a,n);
//打印
for(int i=0; i<n; i++){
cout<<a[i]<<" ";
}
return 0;
}
/**冒泡排序
1、比较相邻的元素,如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。
这步做完后,最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字
需要比较
*/
void mSort(int a[],int n){
for(int i=0; i<n-1; i++){
for(int j=0; j<n-1-i; j++){
if(a[j]>a[j+1]){
//交换
swap(a[j],a[j+1]);
}
}
}
}
/**选择排序
1、在末排序序列中找到最小(大)元素,存放到排序序列的起始位置
2、从剩余末排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾
3、以此类推,直到所有元素排序完毕
*/
void SelectSort(int a[],int n){
int minIndex,temp;
for(int i=0; i<n-1; i++){
minIndex = i;
for(int j=i+1; j<n; j++){
if(a[j]<a[minIndex]){
minIndex = j;
}
}
swap(a[i],a[minIndex]);
}
}
/**
1、从第一个元素开始,该元素可以认为已经被排序
2、取出下一个元素,在已经排序的元素序列中从后向前扫描
3、如果该元素(已排序)大于新元素,将该元素移到下一位置
4、重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
5、重复步骤 2~5
*/
void InsertSort(int a[], int n){
for(int i=1; i<n; i++){
if(a[i]<a[i-1]){
int j = i-1;
int x = a[i];
a[i] = a[i-1];
while(x<a[j]){
a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
}
}
网友评论