学习笔记 | 《算法导论》之从入门到放弃（1）

问题：XXXX
输入：XXXXXXXX
输出：XXXXXXXX
算法步骤：
1.XXXXXXXXXXX
2.XXXXXXXXXXX

输入：n个数的一个序列<a1,a2,...,an>
输出：输入序列的一个排列<a1’,a2’,...,an’>，满足a1’≤a2’≤...≤an’

#include<iostream>
using namespace std;

void insertionsort(int *A,int length){
    //插入排序
    int key; //暂存当前位置的值
    int i;
    for(int j=1;j<length;j++){
        key = A[j]; //暂存当前位置的值
        i= j-1;
        while(i>=0 && A[i]>key){ //如果前面的值比key大，则交换
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
}
int main(){
    int A[9]={9,3,4,2,6,7,5,1,8}; //举了个栗子
    int length=sizeof(A)/sizeof(A[0]); //求数组的长度的一种方法
    insertionsort(A,length);
    
    //输出排序后的序列
    for(int i=0;i<length;i++){
        cout<<A[i]<<" ";
    }
    return 0;
}

#include <iostream>
using namespace std;

void merge(int arr[],int left,int mid,int right)
{
    int aux[right-left+1];//开辟一个新的数组，将原数组映射进去
    for(int m=left;m<=right;m++)
    {
        aux[m-left]=arr[m];
    }

    int i=left,j=mid+1;//i和j分别指向两个子数组开头部分

    for(int k=left;k<=right;k++)
    {
        if(i>mid)//右边还有剩余
        {
            arr[k]=aux[j-left];
            j++;
        }
        else if(j>right)//左边还有剩余
        {
            arr[k]=aux[i-left];
            i++;
        }
        else if(aux[i-left]<aux[j-left])//左边小于右边
        {
            arr[k]=aux[i-left];
                i++;
        }
        else//右边小于左边
        {
            arr[k]=aux[j-left];
            j++;
        }
    }
}
//递归的使用归并排序，对arr[l....right]排序
void merge_sort(int arr[],int left,int right)
{
    if(left >=right)
        return ;
    int mid=(left+right)/2;
    merge_sort(arr,left,mid);
    merge_sort(arr,mid+1,right);
    merge(arr,left,mid,right);
}

void my_merge_sort(int arr[],int n)
{
    merge_sort(arr,0,n-1);
}

int main()
{
    //举个栗子
    int a[6];
    for(int i=0;i<6;i++)
    {
        cin>>a[i];
    }
    my_merge_sort(a,6);
    for(int i=0;i<6;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}