插入排序的C、C++实现

一、插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

• 假设我们输入的是 5，1，4，2，3 我们从第二个数字开始，这个数字是 1 ，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比， 因此我们比较1和5，1比5小，所以我们就交换1和5 ，原来的排列就变成了 1，5，4，2，3
• 接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 1，4，5，2，3 ,我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。
• 再来看第四个数字，这个数字是2，我们将2和它左边的数字相比，都比2大，所以就将2一路往左移动，一直移到2的左边是1，这时候排序变成了 1，2，4，5，3
• 最后，我们检查第五个数字，这个数字是3，3必须往左移，一直移到3的左边是2为止，所以我们的排列就变成了 1，2，3，4，5 排序因此完成了。

说白了，插入排序就是假定第一个元素已经排好序，然后依次从剩下需要排序的元素中取元素，安装大小插入到已经排好序的元素中，所以叫插入排序。

二、程序实现

// 插入排序 Demo

#include<iostream>

using namespace std;

const int BUFFSIZE = 6;

void Insert_Sort(int Arr[]);

int main()

{

	int Arr[BUFFSIZE] = { 5,4,89,10,7,100};

	Insert_Sort(Arr);

	return 0;

}

// 插入排序

void Insert_Sort(int Arr[])

{

    // 假设第一个元素已经排好序，将后面的元素有序插入到已经排好序的元素中，所以从第二个元素开始(索引为1)

	for (int i = 1; i < BUFFSIZE; i++)

	{

        // 将第一个需要排序的元素，与已经排好序的对比，找到正确的插入位置。

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

		{

			if (Arr[j] < Arr[i])

			{

				int tmp = Arr[i];

				Arr[i] = Arr[j];

				Arr[j] = tmp;

			}

		}

	}

    //输出排序后的数组

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

	{

		cout << Arr[i] << " ";

	}

	cout << endl;

}