排序算法之插入排序

插入排序解釋：

有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法--插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分:第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外(讓數(shù)組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。

插入排序的基本思想是:每步將一個待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。

舉例：相當(dāng)于打撲克牌，每接一張牌然后就插入手上已排序的拍中，待接的牌相當(dāng)于待排序的數(shù)：

程序算法過程示意圖：

程序代碼：

/*
* 項目名稱：sort.h
* 作       者：鄒明
* 完成時間：2016.5.20
*/

#ifndef __SORT_H__
#define __SORT_H__
#include<iostream>
using namespace std;

void print(int a[], int size)  //輸出
{
	for (int j = 0; j<size; j++)
	{
		cout << a[j] << "  ";
	}
	cout << endl;
}

void InsertSort(int *a, int size)
{
	cout << "插入排序前數(shù)組：" << endl;
	print(a, size);
	if (size <= 1)
		return;
	for (int i = 1; i < size; i++)
	{
		if (a[i] < a[i - 1])
		{
			int j = i - 1;
			int x = a[i];
			while (x < a[j])
			{
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = x;
		}
	}
	cout<< "插入排序后數(shù)組：" << endl;
	print(a, size);
}

#endif

測試用例：

#define _CRT_SECURE_NO_WARNINGS 1
#include"sort.h"

int main()
{
	int arr[] = { 4, 5, 0, 6, 2, 1, 5, 8, 3, 9, 7, 3 };
	int size = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, size);
	system("pause");
	return 0;
}

結(jié)果：

感謝大家訪問，歡迎批評指正！