插入排序法(Insertion Sort)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

插入排序法(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 = 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 = 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 sorted = new List (array.Length); for (int i = 0; i = 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 = 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 sorted = new ArrayList (array.length); for (int i = 0; i = 0 && sorted.get(index) > n) --index; sorted.add(index + 1, n); } for (int i = 0;i

In-place

public class InPlace { public static void Sort(int[] array) { int n, j; for (int i = 1; i = 0 && array[j] > n; --j) array[j + 1] = array[j]; array[j + 1] = n; } } }

C++

額外空間版本

ExtraSpace.h

#ifndef EXTRASPACE_H #define EXTRASPACE_H

#include

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 sorted; for (int i = 0; i ::iterator iterator = sorted.begin(); // 因程式特性改由前往後比對 while (iterator != sorted.end() && *iterator ::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 = 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

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

插入排序法(Insertion Sort)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

文章搜尋

文章精選