挿入ソートおよび時間空間複雑度分析

ソートの挿入
げんりぶんせき
並べ替えられたシーケンスにレコードを挿入し、新しいシーケンスを得る
シーケンスの最初のデータを秩序化されたサブシーケンスと見なし、シーケンス全体が秩序化されるまで、2番目のレコードから秩序化されたサブシーケンスに逐次挿入する
コード実装

#include
using namespace std;


void printArray(int *arr, int len)
{
	for (int i = 0; i < len; ++i)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}


void InsertSort(int *arr, int len)
{

	for (int i = 1; i < len; ++i)
	{

		if (arr[i] > arr[i - 1])
		{
			int temp = arr[i];
			int j = i - 1;
			/*
			4 5 8 9 1 2

			*/
			for (; j >= 0 && temp > arr[j]; j--)        
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

int main()
{
	int arr[] = { 4,5,8,9,1,2 };
	int len = sizeof(arr) / sizeof(int);//          
	printArray(arr, len);
	InsertSort(arr, len);
	printArray(arr, len);
	return 0;
}

じかんふくごうどけいさん
 
さいてきじょうたい
さいさじょうたい
時間の複雑さ
比較回数
n-1
1+2+3+4+……+n-1=(n-1)n/2
O(n)
移動回数
0
1+2+3+……+n-1=(n-1)n/2
O(n^2)
 
 
 
 
平均値をとるので時間複雑度はO(n^2)
くうかんふくざつさ
直接挿入ソートではi,j,tmpの3つの補助要素のみが用いられ,問題規模に関係なく空間複雑度はO(1)である.