阿夢的程式設計天地

插入排序法實際執行狀況如下:

1.從序列中第一個元素開始，然後先把第一個元素視為已經排序

2.取出下一個元素，在已經排序的元素序列中從後向前掃描

3.如果當下被比較的元素(已排序的)大於新元素(未排序的當下所選取的拿個)，則將當下被排序的元素移動到下一個位置

4.重複步驟3，直到已經排序的元素小於或等於新元素的值

5.將新元素插入到已排序元素中小於或等於新元素的值之後

6.重複步驟2~5

範例:  排序 3 7 1 2 9 4 

3 7 1 2 9 4  (已排序: 3 未排序: 7 1 2 9 4 行為:7比3大 所以7的位置不變將7加入到已排序中 )
3 7 7 2 9 4  (已排序:3 7  未排序: 1 2 9 4 行為:1比7小 所以 7的位置後移一個 )
3 3 7 2 9 4  (已排序: 3 7  未排序:1 2 9 4  行為: 1 比3小 所以3的位置後移一個)
1 3 7 2 9 4  (已排序:1 3 7  未排序: 2 9 4  行為: 1在第一個位置沒得比了 將1加入到已排序中)
1 3 7 7 9 4  (已排序: 1 3 7 未排序: 2 9 4  行為: 2比7小 所以7的位置後移一個)
1 3 3 7 9 4  (已排序: 1 3 7 未排序: 2 9 4行為: 2比3小 所以3的位置後移一個)
1 2 3 7 9 4  (已排序: 1 2 3 7 未排序:9 4 行為: 2比1大所以將2插入到1的位置的後面)
1 2 3 7 9 4  (已排序: 1 2 3 7 9 未排序:4 行為: 9比7大 9的位置不變 將9加入到已排序)
1 2 3 7 9 9  (已排序:1 2 3 7 9 未排序:4 行為: 4比9小 將9的位置後移一個)
1 2 3 7 7 9  (已排序: 1 2 3 7 9 未排序:4 行為:4比7小 將7的位置後移一個)
1 2 3 4 7 9  (已排序:1 2 3 4 7 9 未排序: 行為:4比3大 所已將4插入到3的位置的後面)

時間複雜度如下:

最佳時間複雜度：O(n) 
當資料的排序恰好由小到大時。

平均時間複雜度：O(n^2)
第n筆資料，平均比較n/2次。

最差時間複雜度：O(n^2)
當資料的順序剛好由大到小時，第n回合需比n次。

PseudoCode 大致如下:

void insertionSort(int array[], int size) {

	for (int i = 0; i < size - 1; i++) {

		int j = i + 1;

		int tmp = array[j];

		while (j > 0 && tmp > array[j - 1]) {

			array[j] = array[j - 1];

			j--;

		}

		array[j] = tmp;

	}

}

完整程式碼如下:

#include <iostream>
using namespace std;

int insertionSort(int [], int);


int main()
{

	int *ptr;//宣告指標ptr
	int size;//宣告陣列大小

	cout << "請輸入陣列大小:";
	cin >> size;//輸入陣列大小

	ptr = new int [size];//建立動態記憶體陣列

	for (int i = 0; i < size; i++)
	{
		cin >> *(ptr + i);//輸入陣列中的資料
	}

	cout << "排序前:" << endl;

	for (int j = 0; j < size; j++)
	{
		cout << *(ptr + j)<<" ";//印出陣列中的資料
	}

	cout << endl;

	insertionSort(ptr, size);

	cout << "排序後:" << endl;

	for (int k = 0; k < size; k++)
	{
		cout << *(ptr + k) << " ";//印出排序後的陣列中的資料
	}
	system("pause");
	return 0;
}

int insertionSort(int a[], int arraySize)
{
	int temp = 0;
	int next = 0;
	
	for (int i = 1; i < arraySize; i++)
	{
		temp = a[i];//未排序中要拿來排的值
		next = i;//在已排序中最後一個數值的位置

		while ((next>0) && (a[next-1]>temp))//在已排序中的第一個位置要大於零 且 已排序中的值要比 未排序中要拿來比較的值大
		{
			a[next] = a[next - 1];
			next--;
		}

		a[next] = temp;//將未排序中要拿來排的值插入到排序中的元素當中比他小或是等於他的值後面

	}
	return *a;
}

執行結果如下:

有夢最美 築夢踏實

活在當下 認真過每一天

我是阿夢 也是Ace