插入排序法(Insertion Sort)
简介
插入排序法(Insertion Sort)是排序演算法的一种,他是一种简单容易理解的排序演算法,其概念是利用另一个数列来存放已排序部分,逐一取出未排序数列中元素,从已排序数列由后往前找到适当的位置插入。运算流程如下:
- 从未排序数列取出一元素。
- 由后往前和已排序数列元素比较,直到遇到不大于自己的元素并插入此元素之后;若都没有则插入在最前面。
- 重复以上动作直到未排序数列全部处理完成。
流程示意图:
然而实作上通常不使用额外的数列来储存已排序的部分,而使用原地(In-place)的方式来完成,数列的左半部表示已排序部分,右半部表示未排序部分,不另外使用数列。在与已排序的部分比较时,利用指派(Assign)的方式将元素往右位移,来达到插入的效果,因为位移的关系需要有另一个变数来暂存最右边的数值。运算流程如下:
- 将未排序的部分最左边元素储存到暂存变数。
- 由后往前和已排序部分元素比较,若比自己大则将该元素往右边位移。
- 重复2的动作直到遇到不大于自己的元素,将暂存变数写入在该元素之后;若都没有则写入在最前面。
- 重复以上动作直到未排序部分全部处理完成。
流程示意图:
分析
最佳时间复杂度:O(n)
平均时间复杂度:O(n^2)
最差时间复杂度:O(n^2)
空间复杂度:O(1)
Stable sort:是
虚拟码
额外空间版本
function sort(list) var sorted = [] for i = 0;i < list.length;++i var n = list[i] var j = sorted.length - 1 while j >= 0 && sorted[j] > n --j end while n 插入至 sorted[j] 之后 end for list = sorted end function
In-place
function sort(list) for i = 1;i < list.length;++i var n = list[i]; // 比n大的往右移 for j = i - 1;j >= 0 && list[j] > n;--j list[j + 1] = list[j]; end for list[j + 1] = n; end for end function
语法
C#
额外空间版本
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace InsertionSort { class ExtraSpace { public static void Sort(int[] array) { List<int> sorted = new List<int>(array.Length); for (int i = 0; i < array.Length; ++i) { int n = array[i]; int index = sorted.Count - 1; while (index >= 0 && sorted[index] > n) --index; sorted.Insert(index + 1, n); } sorted.ToArray().CopyTo(array, 0); } } }
In-place
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace InsertionSort { class InPlace { public static void Sort(int[] array) { int n, j; for (int i = 1; i < array.Length; ++i) { n = array[i]; for (j = i - 1; j >= 0 && array[j] > n; --j) array[j + 1] = array[j]; array[j + 1] = n; } } } }
Java
额外空间版本
import java.util.List; import java.util.ArrayList; public class ExtraSpace { public static void Sort(int[] array) { List<Integer> sorted = new ArrayList<Integer>(array.length); for (int i = 0; i < array.length; ++i) { int n = array[i]; int index = sorted.size() - 1; while (index >= 0 && sorted.get(index) > n) --index; sorted.add(index + 1, n); } for (int i = 0;i < array.length;++i) array[i] = sorted.get(i); } }
In-place
public class InPlace { public static void Sort(int[] array) { int n, j; for (int i = 1; i < array.length; ++i) { n = array[i]; for (j = i - 1; j >= 0 && array[j] > n; --j) array[j + 1] = array[j]; array[j + 1] = n; } } }
C++
额外空间版本
ExtraSpace.h
#ifndef EXTRASPACE_H #define EXTRASPACE_H #include <list> using namespace std; class ExtraSpace { public: static void Sort(int* array, int length); protected: private: }; #endif // EXTRASPACE_H
ExtraSpace.cpp
#include "ExtraSpace.h" void ExtraSpace::Sort(int* array, int length) { list<int> sorted; for (int i = 0; i < length; ++i) { int n = array[i]; list<int>::iterator iterator = sorted.begin(); // 因程式特性改由前往后比对 while (iterator != sorted.end() && *iterator <= n) ++iterator; sorted.insert(iterator, n); } int i = 0; for (list<int>::iterator iterator = sorted.begin(); iterator != sorted.end() ;++iterator, ++i) array[i] = *iterator; }
In-place
InPlace.h
#ifndef INPLACE_H #define INPLACE_H class InPlace { public: static void Sort(int* array, int length); protected: private: }; #endif // INPLACE_H
InPlace.cpp
#include "InPlace.h" void InPlace::Sort(int* array, int length) { int n, j; for (int i = 1; i < length; ++i) { n = array[i]; for (j = i - 1; j >= 0 && array[j] > n; --j) array[j + 1] = array[j]; array[j + 1] = n; } }
随机产生20000笔资料实测
C# InPlace: 880ms ExtraSpace: 810ms Java InPlace: 115ms ExtraSpace: 319ms C++ InPlace: 840ms ExtraSpace: 2070ms
下载