【DAY 22】Algorithm - Insertion sort 插入排序法

前面我们提过了 Bubble sort，这次我们要来从题目来看另一种排序的演算法 —— Insertion Sort。

题目
使用下面这个函数将数列由小排到大

void insertionSort (const int sorted[], int sorted[], int len);

输入输出格式

Sol.
首先，先将资料分成已排序、未排序两部分。在未排序的部分中，从第一笔资料开始跟已排序的相互比较，并插到适当的位置。这个情况由於是由小排到大，因此我们会从右至左比较。

[演算法] 插入排序法(Insertion Sort)
Comparison Sort: Insertion Sort(插入排序法)
这两篇文章都有做一个详尽的介绍，第一篇包含计算时间复杂度，有兴趣的人可以参考！

Pseudocode

insertionSort：
	int temp = 0;
	int j = 0;
	// 每一个要处理的值就存为temp，并与已处理的部分做比较
	for i in range 0 ~ len
		temp = sorted[i];
		j = i - 1;
		// 判断能否插入数值
		while (i 不是第 0 个数 且 temp < sorted[j]) 
            // 向右移
        	sorted[j + 1] = sorted[j];
			j--;
Main function：
	cin >> len;
	int* sorted = new int[len];
	输入 sorted 所需存的资料

以上就是粗略的 insertion sort 啦！