第二章 算法基础

2.1 插入排序

C++实现：

#include<iostream>
using namespace std;

void InsertSort(int arr[],int n)
{
    int i,j,key;
    for(i=1;i<n;++i)
    {
        key=arr[i];
        j=i-1;
        while(j>=0&&key<arr[j])
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key;
    }
}

int main()
{
    int arr[10]={14,25,53,23,2,6,74,34,67,39};
    InsertSort(arr,10);
    for(auto a:arr)
        cout<<a<<' ';
    cout<<endl;
}

2.3 分治法

合并操作代码

#include<iostream>
using namespace std;

void Merge(int arr[],int p,int q,int r)
{
    int i=0,j=0;
    int k;
    int n1=q-p+1;
    int n2=r-q;
    int temp[r-p+1];
    for(k=0;k<r-p+1;++k)
    {
        if(i<n1&&j<n2&&arr[p+i]<=arr[q+1+j])
        {
            temp[k]=arr[p+i];
            i++;
        }
        else if(i<n1&&j<n2&&arr[p+i]>arr[q+1+j])
        {
            temp[k]=arr[q+1+j];
            j++;
        }
        else if(i==n1||j==n2)
            break;
    }
    while(j<n2)
    {
        temp[k++]=arr[q+1+j];
        j++;
    }
    while(i<n1)
    {
        temp[k++]=arr[p+i];
        i++;
    }
    for(k=0;k<r-p+1;++k)
        cout<<temp[k]<<' ';
    cout<<endl;
}

int main()
{
    int arr[10]={1,6,9,12,56,2,31,45,67,78};
    Merge(arr,0,4,9);
}

2.3.1 合并排序

#include<iostream>
using namespace std;
void Merge(int arr[],int p,int q,int r);
void MergeSort(int arr[],int p,int r)
{
    int q;
    if(p < r) //只有一个或无记录时不须排序
    {
		q = (int)((p+r)/2);      //将data数组分成两半
		MergeSort(arr, p, q);   //递归拆分左数组
		MergeSort(arr, q+1, r); //递归拆分右数组
		Merge(arr, p, q, r);    //合并数组
    }
}

/*int main()
{
    int arr[10]={1,6,8,2,4,9,67,34,27,89};
    MergeSort(arr,0,9);
}*/
int main()
{
    int arr[10]={1,23,55,67,89,2,34,57,76,90};
    int k;
    for(k=0;k<10;++k)
    {
        cout<<arr[k]<<" ";
    }
    cout<<endl;
    MergeSort(arr,0,9);
    for(k=0;k<10;++k)
    {
        cout<<arr[k]<<" ";
    }
    cout<<endl;
}

void Merge(int arr[],int p,int q,int r)
{
    int i,j,k;
    int n1=q-p+1;
    int n2=r-q;
    int left[n1],right[n2];
    for(i=0; i<n1;i++)  //对左数组赋值
		left[i] = arr[p+i];
    for(j=0; j<n2;j++)  //对右数组赋值
		right[j] =arr[q+1+j];
    i=j=0;
    k=p;
    while(i<n1&&j<n2)
    {
        if(left[i]<=right[j])
        {
            arr[k++]=left[i++];
        }
        else
        {
            arr[k++]=right[j++];
        }
    }
    while(j<n2)
    {
        arr[k++]=right[j++];
    }
    while(i<n1)
    {
        arr[k++]=left[i++];
    }
}

或者

//Merge.cpp
#include<iostream>
using namespace std;

void Merge(int arr[],int p,int q,int r)
{
    int i=0,j=0;
    int k;
    int n1=q-p+1;
    int n2=r-q;
    int temp[r-p+1];
    for(k=0;k<r-p+1;++k)
    {
        if(i<n1&&j<n2&&arr[p+i]<=arr[q+1+j])
        {
            temp[k]=arr[p+i];
            i++;
        }
        else if(i<n1&&j<n2&&arr[p+i]>arr[q+1+j])
        {
            temp[k]=arr[q+1+j];
            j++;
        }
        else if(i==n1||j==n2)
            break;
    }
    while(j<n2)
    {
        temp[k++]=arr[q+1+j];
        j++;
    }
    while(i<n1)
    {
        temp[k++]=arr[p+i];
        i++;
    }
    for(k=0;k<r-p+1;++k)
        arr[p++]=temp[k];
}

//MergeSort.cpp
#include<iostream>
using namespace std;
void Merge(int arr[],int p,int q,int r);
void MergeSort(int arr[],int p,int r)
{
    int q;
    if(p < r) //只有一个或无记录时不须排序
    {
		q = ((p+r)/2);      //将data数组分成两半
		MergeSort(arr, p, q);   //递归拆分左数组
		MergeSort(arr, q+1, r); //递归拆分右数组
		Merge(arr, p, q, r);    //合并数组
    }
}

/*int main()
{
    int arr[10]={1,6,8,2,4,9,67,34,27,89};
    MergeSort(arr,0,9);
}*/
int main()
{
    int arr[10]={1,23,55,67,89,2,34,57,76,90};
    int k;
    for(k=0;k<10;++k)
    {
        cout<<arr[k]<<" ";
    }
    cout<<endl;
    MergeSort(arr,0,9);
    for(k=0;k<10;++k)
    {
        cout<<arr[k]<<" ";
    }
    cout<<endl;
}