三大排序(冒泡、选择、插入）

#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;
        }
    }
}