如何使用c++语言简单实现插入排序

1、算法原理

// 排序一个大小为n的数组arr[]，insertionSort(arr, n)i从1到n-1逐步变大

将元素arr[i] 插入到有序序列 arr[1...i-1]中

2、举个例子来说明算法：

需要排序的序列为：

4,3,2,10,12,1,5,6

3、第一步，由于第二个元素3小于第一个元素4。将元素3插入到元素4的前面。

4、第二步：将第三个元素2，插入到序列3,4 中。2插入第一个位置，3,4分别往后移动一位。

5、剩下的插入步骤与第一步和第二步类似，我们展示在下面，并不细讲

6、这一步提供算法实现的代码。

#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&&arr[j]>key)

            {

                  arr[j+1]=arr[j];

                  j--;

            }

            arr[j+1]=key;

      }

}

void printarray(int arr[],int n)

{

    for (int i=0;i<n;i++)

    {

         cout<<arr[i]<<endl;

    }

}

int main()

{

    int arr[]={9,3,2,1,5,13,4};

    int n=sizeof(arr)/sizeof(int);

    insertsort(arr,n);

    printarray(arr,n);

    return 0;

}