InsertionSort->逆序->歸并排序等

前言

    InsersionSort是一種很簡單直覺的排序方法。它本身的過程類似于我們我們玩撲克牌的時候一張張的從後面往前的調整順序。而歸并排序是另外一種典型思想的應用，divide and conquer。從表面上看起來，他們兩者的聯系也就在于都是排序的方法而已。如果這個時候我們把它們和常用的一個數學概念逆序聯系起來，會發現他們之間有一些比較有意思的東西。

InsertionSort介紹

    插入排序的過程非常簡單，用通俗的語言來描述的話，則是如下的一個過程：

    1. 從第二個元素開始向前比較，一直到最後一個元素。

    2. 在比較的過程中，如果前面的元素比目前元素大，則将前面的元素往後面移動一位。這樣直到一個元素，将目标元素放置進去。

    因為整體過程比較簡單，這裡我們不作詳細的描述。

    一個參考的實作代碼如下：

public static void sort(int[] a)
{
	for(int i = 1; i < a.length; i++)
	{
		int key = a[i];
		int j = i - 1;
		while(j >= 0 && a[j] > key)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;
	}
}
           

    這裡的一個比較元素和放置的方式是将目前需要參加比較的元素放到一個key元素裡，然後每次比較的時候直接将前面大的元素覆寫後面的元素。這樣直到循環外面的時候将key放置進去。還有一種實作的方式就是每次發現前面元素比較大的時候就直接和前面元素交換位置。這兩者實作的最終結果是一樣的。

    總的來說，這個排序方法的實作沒什麼特殊的。我們這裡的介紹相當于先埋下一個伏筆。

逆序的概念

    我們現在來看看逆序的概念。一般來說，如果我們有這麼一個數組a[n]。在這個數組裡，則一般元素排列的位置i, j表示它們所在的索引位置。如果對于i < j這兩個元素，a[i] > a[j]，則表示它們兩個構成一個逆序。

    我們來看一個例子，比如說我們有數組{2, 3, 8, 6, 1}。 對于第一個元素2來說，排在它後面的元素而且比它還小的就和它構成了一個逆序。比如2和1。3和1, 8 和6以及1都構成逆序關系。這樣，我們就很自然的會引申出一個問題，如果我們需要計算一個數組裡所有逆序的關系，有什麼好的辦法嗎？

統計法

    第一個我們所能想到的方法就是前面按照定義所說明的過程。既然我們每個逆序都是一個前面元素比後面元素大，那麼我們就從數組的開頭每個元素向後比較，如果比目前元素小，就算累加一個逆序。這樣我們可以得到一個很簡單的方法：

public static int inversion(int[] a) {
    int count = 0;
    for(int i = 0; i < a.length - 1; i++) {
        for(int j = i + 1; j < a.length; j++) {
            if(a[i] > a[j])
                count++;
        }
    }
    return count;
}
           

    從算法的時間複雜度來說，它的複雜度達到了o(n^2)。

    除了這個方法外，我們還有其他的辦法嗎？我們再看看另外一個思路。

Insersion sort

    現在我們再來回顧前面insersion sort的過程。每次一個元素都要和前面進行比較，如果前面的元素比目前元素大，他們就要交換位置。而前面的元素比目前元素，這不正說明他們構成了一個逆序嗎？而我們交換他們的位置就消除了一個逆序。如此看來我們排序的過程就是一個消除逆序的過程。而且我們再來看，我們這個元素和前面的元素比較，他們交換位置之後并不會影響到數組後面的元素和前面元素的逆序關系。是以，我們隻要把insersion sort裡交換的次數統計出來就知道有多少個逆序了。按照這種思路，我們得到另外一種實作代碼：

public static int inversion(int[] a)
{
        int count = 0;
	for(int i = 1; i < a.length; i++)
	{
		int key = a[i];
		int j = i - 1;
		while(j >= 0 && a[j] > key)
		{
			a[j + 1] = a[j];
			j--;
                        count++;
		}
		a[j + 1] = key;
	}
       return count;
}
           

     從前面對insersion sort的讨論知道，它的時間複雜度也是o(n^2)。看來這裡隻是展現了一種思路，但是算法性能上并沒有什麼改進。那麼，我們還有沒有更好的改進呢？

歸并排序

    歸并排序的過程主要是一種分治的思想。它首先将數組分解成兩個部分，然後分别對每個部分進行排序。通過這麼一個不斷遞歸細分的過程達到排序的效果。一個典型的過程如下圖：

    這裡隻是展示了整體的排序過程。可是他們和逆序有什麼關系呢？考慮到前面我們提到過，排序就是消除逆序的過程。如果每個獨立的過程對逆序的計算不影響全局的話，我們可以有一個法子來處理。我們知道，在歸并排序裡，消除這些逆序的過程就在于merge這個步驟。而merge這裡是要合并兩個排好序的數組。在前面的示例裡我們可以看到一個這樣的場景，比如說當我們要歸并數組[2, 4, 5, 7]和[1, 2, 3, 6]時。一旦前面的某個元素比後面元素大，則從該元素起到該子數組裡所有的元素都和後面的元素構成逆序。而如果我們把後面的元素放入到合并後的數組中時，這些逆序都被消除了。注意到的是，這裡消除的是若幹個逆序而不止一個。比如說前面2, 4, 5, 7和後面數組裡的1就構成了4個逆序，如果把1放到貴并的結果數組中，這些逆序就消除了。

    是以，有了這些讨論之後，我們就知道該怎麼來計算逆序了。隻要在每次歸并的時候看後面和前面元素的比較，如果後面的元素比前面元素小，則增加前面數組所有剩下元素的個數作為增加的逆序數。一個根據歸并排序的修改版逆序統計方法就出來了：

public static void mergeSort(int[] array, int start, int end)
{
	if(start < end)
	{
		int middle = start + (end - start) / 2;
		mergeSort(array, start, middle);
		mergeSort(array, middle + 1, end);
		merge(array, start, middle, end);
	}
}

public static void merge(int[] a, int start, int middle, int end)
{
	int[] array = new int[end - start + 1];
	int i = 0, j = start, k = middle + 1;
	while(j <= middle && k <= end)
	{
		if(a[j] <= a[k])
			array[i++] = a[j++];
		else
		{
			count += middle - j + 1;
			array[i++] = a[k++];
		}
	}
	while(j <= middle)
		array[i++] = a[j++];
	while(k <= end)
		array[i++] = a[k++];
	for(i = 0; i < array.length; i++)
		a[start + i] = array[i];
}
           

    要注意到的一點就是，這裡幾乎和歸并排序的代碼一樣，就是在裡面增加了一行： count += middle - j + 1; 這裡的count我們可以在具體實作的程式裡定義成一個全局的靜态變量。後面隻需要取這個變量就可以了。

    我們從歸并排序的特性說明可以知道，該算法的時間複雜度為O(nlgn)。

總結

    求逆序和排序算法有着比較緊密的聯系。我們排序就是一個消除逆序的過程。對于這個話題在一年前的時候就已經想讨論一番了。因為除了前面的這幾種方法以外還有一種比較巧妙的辦法。可惜一直沒有時間去體會也沒有參透。等以後有時間的時候再好好的補充總結一下。

參考材料

Introduction to algorithms

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees