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

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

插入排序是一种简单直观的排序方法，他模仿了人们打牌时候对牌进行插入排序的过程。它的工作原理是从左到右逐步构建递增或者递减序列，对于未排序数据，逐步在已排序的数据中找到合适的位置插入。下面小编将简单介绍一下这种排序方法的实现过程。

算法原理

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

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

举个例子来说明算法：

需要排序的序列为：

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

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

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

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

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

#include

using namespace std;

void insertsort(int arr[],int n)

{

int i,j,key;

for (i=1;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

{

cout<

}

}

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;

}