算法周記（一）直接插入排序 @ 互聯網

文章出處

算法在計算機科學領域中占有舉足輕重的地位，一套算法設計的好壞直接決定了一項工程的成敗。在大學教育中老師就教導我們要數據結構 + 算法（現在還需要加上體系結構吧），但是這兩門基礎課我卻從沒有學好過：）我打算來個周記，每周仔細研究一個算法，然后分別用C#、Java、Matlab實現，供感興趣的朋友一起學習、研究。除了常見的算法分類之外，我會格外關注數值算法，因為我對數學有著濃厚的興趣。由于我C++學的不好，故不提供C++算法實現，具體C++的資料很多，感興趣的朋友可以多查找下。

示例代碼下載

測試環境：

Windows Server 2008 R2 DataCenter

C#：Visual Studio 2010 Ultimate RC（.NET Framework 4.0 RC x64）

Java：Eclipse SDK 3.5.1 x64（JDK 1.6 Update 18 x64）

Matlab：Matlab R2009b x64

PS(Visual Studio 2010正式版即將發布，到時會更新；Matlab R2010a已經發布，正在測試，近期也會更新)

直接插入排序

基本思想：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的記錄中的適當位置，直到全部記錄插入完成為止。

直接插入排序是把一個序列分為兩部分，第一部分是排好序的，數學上叫做"有序區"，然后從第二個部分中（"無序區"）將第一個記錄插入到有序區中，使得插入后有序區仍然有序。然后重復上述操作，每次無序區均減少一個記錄，直至其中記錄數為零。

復雜度：時間復雜度為O(N^2)，空間復雜度為O(1)。

可以看出，N^2還是很大的，當N較大時，不宜采用直接插入排序。推薦記錄的數目是N<20。

C#語言描述：

代碼

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace InsertSort
{
    class InsertSortDemo
    {
        private static int[] fxInsertSort(int[] arr)
        {
            int i, j, arrTmp;
            for (i = 1; i < arr.Length; i++)
            {
                j = i;
                arrTmp = arr[i];
                while (j > 0 && arr[j - 1] > arrTmp)
                {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = arrTmp;
            }
            return arr;
        }

        static void Main(string[] args)
        {
            int[] arr = InsertSortDemo.fxInsertSort(new int[] { 1, 4, 2, 6, 5 });
            foreach (int i in arr)
            {
                Console.Write(i + ",");
            }
            Console.ReadLine();
        }
    }
}

Java語言描述：

代碼

package brooks.cnblogs.arithmetic.sort;

public class InsertSortDemo {

    /**
     * @param args
     */
    private static int[] fxInsertSort(int[] arr) {
        int i, j, arrTmp;
        for (i = 1; i < arr.length; i++) {
            j = i;
            arrTmp = arr[i];
            while (j > 0 && arr[j - 1] > arrTmp) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = arrTmp;
        }
        return arr;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = InsertSortDemo.fxInsertSort(new int[] { 1, 4, 2, 6, 5 });

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}

Matlab語言描述：

代碼

% 定義數組
arr = [1 4 2 6 5];
% Matlab中數組索引從1開始
for i = 2:length(arr)
    j = i;
    arrTmp = arr(i);
    while j > 1 && (arr(j - 1) > arrTmp)
        arr(j) = arr(j - 1);
        j = j - 1;
    end
    arr(j) = arrTmp;
end
% 輸出排序后結果
disp(arr);