1. 插入排序
=====================================================
算法思想簡單描述：
在要排序的一組數(shù)中，假設(shè)前面(n-1) [n>=2] 個數(shù)已經(jīng)是排
好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)
也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。
直接插入排序是穩(wěn)定的。算法時間復(fù)雜度O(n2)--[n的平方]
一般來說，插入排序都采用in-place在數(shù)組上實現(xiàn)。具體算法描述如下：
1.從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復(fù)步驟2~5
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個變種，稱為二分查找排序。
使用插入排序為一列數(shù)字進行排序的過程
最差時間復(fù)雜度 O(n^2)
最優(yōu)時間復(fù)雜度 O(n)
平均時間復(fù)雜度O(n^2)
=====================================================
實例1：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InsertionSorter
{
public class InsertionSorter
{
public void Sort(int[] list)
{
//從第二個元素開始遍歷
for (int i = 1; i < list.Length;++i )
{
//將第i個元素賦值給一個臨時變量
int t = list[i];
//記錄第i個元素的下標(biāo)
int j = i;
//比較若list[j-1]>list[j]，小標(biāo)j -1; 并執(zhí)行交換。
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
//不管list[j-1]>list[j]，或list[j-1]<=list[j],都執(zhí)行下面語句；
list[j] = t;
}
}
}
class Program
{
static void Main(string[] args)
{
int[] iArray = new int[] { 1,5,3,6,10,55};
InsertionSorter ii = new InsertionSorter();
ii.Sort(iArray);
for (int m = 0; m <= iArray.Length-1; m++)
Console.WriteLine("{0}",iArray[m]);
Console.ReadLine();
}
}
}
2. 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。
====================================================
算法思想簡單描述：
在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加1個節(jié)點，
并且對插入下一個數(shù)沒有提供任何幫助。如果比較相隔較遠距離（稱為
增量）的數(shù)，使得數(shù)移動時能跨過多個元素，則進行一次比較就可能消除
多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現(xiàn)
了這一思想。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中
記錄的下標(biāo)相差d.對每組中全部元素進行排序，然后再用一個較小的增量
對它進行，在每組中再進行排序。當(dāng)增量減到1時，整個要排序的數(shù)被分成
一組，排序完成。
下面的函數(shù)是一個希爾排序算法的一個實現(xiàn)，初次取序列的一半為增量，
以后每次減半，直到增量為1。
希爾排序是不穩(wěn)定的。
原始的算法實現(xiàn)在最壞的情況下需要進行O(n2)的比較和交換。V. Pratt的書[1] 對算法進行了少量修改，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些。
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。
假設(shè)有一個很小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端。如果用復(fù)雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數(shù)據(jù)移至正確位置。而希爾排序會用較大的步長移動數(shù)據(jù)，所以小數(shù)據(jù)只需進行少數(shù)比較和交換即可到正確位置。
一個更好理解的希爾排序?qū)崿F(xiàn)：將數(shù)組列在一個表中并對列排序（用插入排序）。重復(fù)這過程，不過每次用更長的列來進行。最后整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身僅僅對原數(shù)組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
排序過程
最差時間復(fù)雜度 根據(jù)步長串行的不同而不同。O(nLog2 n)
最優(yōu)時間復(fù)雜度 O(n)
平均時間復(fù)雜度 根據(jù)步長串行的不同而不同。
====================================================
實例2：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ShellSorter
{
/// <summary>
/// 希爾排序
/// </summary>
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
class Program
{
static void Main(string[] args)
{
int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
ShellSorter ii = new ShellSorter();
ii.Sort(iArray);
for (int m = 0; m <= iArray.Length - 1; m++)
Console.WriteLine("{0}", iArray[m]);
Console.ReadLine();
}
}
}
3. 選擇排序
====================================================
算法思想簡單描述：
在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；
然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)
到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。
選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)--[n的平方]
選擇排序(Selection sort)是一種簡單直觀的排序算法。
它的工作原理如下。
首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，
然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，
然后放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
實現(xiàn)過程
最差時間復(fù)雜度 О(n)
最優(yōu)時間復(fù)雜度 О(n)
平均時間復(fù)雜度 О(n)
=====================================================
實例3：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace SelectionSorter
{
public class SelectionSorter
{
private int min;
public void Sort(int[] list)
{
//對數(shù)組list從第0個元素進行遍歷
for (int i = 0; i < list.Length - 1; ++i)
{
//記錄第i個小標(biāo)
min = i;
//j=i+1;比較list[i]和list[i+1]，如果list[i+1]<list[i],記錄新的min=j;
for (int j = i + 1; j < list.Length; ++j)
{
if (list[j] < list[min])
min = j;
}
//兩個大小數(shù)交換
int t = list [min];
list[min] = list[i];
list[i] = t;
}
}
}
class Program
{
static void Main(string[] args)
{
int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
SelectionSorter ii = new SelectionSorter();
ii.Sort(iArray);
for (int m = 0; m <= iArray.Length - 1; m++)
Console.WriteLine("{0}", iArray[m]);
Console.ReadLine();
}
}
}
4. 冒泡排序
====================================================
算法思想簡單描述：
依次比較相鄰的兩個數(shù),把大的放前面,小的放后面.即首先比較第1個數(shù)和第2個數(shù),大數(shù)放前,小數(shù)放后.然后比較第2個數(shù)和第3個數(shù)......直到比較最后兩個數(shù).第一趟結(jié)束,最小的
一定沉到最后.重復(fù)上過程,仍從第1個數(shù)開始,到最后第2個數(shù).然后......
由于在排序過程中總是大數(shù)往前,小數(shù)往后,相當(dāng)氣泡上升,所以叫冒泡排序.
冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序?qū)個項目需要O(n^{2})的比較次數(shù)，且可以原地排序。盡管這個算法是最簡單了解和實作的排序算法之一，但它對于少數(shù)元素之外的數(shù)列排序是很沒有效率的。
冒泡排序是與插入排序擁有相等的執(zhí)行時間，但是兩種法在需要的交換次數(shù)卻很大地不同。在最壞的情況，冒泡排序需要O(n^{2})次交換，而插入排序只要最多O(n)交換。
冒泡排序的實現(xiàn)（類似下面）通常會對已經(jīng)排序好的數(shù)列拙劣地執(zhí)行（O(n^{2})），而插入排序在這個例子只需要O(n)個運算。因此很多現(xiàn)代的算法教科書避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在內(nèi)部循環(huán)第一次執(zhí)行時，使用一個旗標(biāo)來表示有無需要交換的可能，也有可能把最好的復(fù)雜度降低到O(n)。在這個情況，在已經(jīng)排序好的數(shù)列就無交換的需要。若在每次走訪數(shù)列時，把走訪順序和比較大小反過來，也可以稍微地改進效率。有時候稱為往返排序，因為算法會從數(shù)列的一端到另一端之間穿梭往返。
2.算法實現(xiàn)
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3.針對所有的元素重復(fù)以上的步驟，除了最后一個。
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
3.實現(xiàn)過程
最差時間復(fù)雜度 O(n^2)
最優(yōu)時間復(fù)雜度 O(n)
平均時間復(fù)雜度O(n^2)
====================================================
實例4：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Bubblesort
{
/// <summary>
/// 冒泡排序
/// </summary>
public class bubblesort
{
public void BubbleSort(int[] R)
{
int i, j, temp; //交換標(biāo)志
bool exchange;
for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序
{
exchange = false; //本趟排序開始前，交換標(biāo)志應(yīng)為假
for (j = R.Length - 2; j >= i; j--)
{
if (R[j + 1] < R[j]) //交換條件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //發(fā)生了交換，故將交換標(biāo)志置為真
}
}
if (!exchange) //本趟排序未發(fā)生交換，提前終止算法
{
break;
}
}
}
}
class Program
{
static void Main(string[] args)
{
int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
bubblesort ii = new bubblesort();
ii.BubbleSort(iArray);
for (int m = 0; m <= iArray.Length - 1; m++)
Console.WriteLine("{0}", iArray[m]);
Console.ReadLine();
}
}
}
5. 快速排序
====================================================
算法思想簡單描述：
快速排序（Quicksort）是對冒泡排序的一種改進。
快速排序的基本概念是：
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，
然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
下面通過一個例子來了解快速排序的具體含義： { 23, 45, 60, 10, 17, 101,12}
第一遍排序：
由此思想，我們可以實現(xiàn)快速排序的代碼：
注意基準(zhǔn)數(shù)據(jù)永遠不變，永遠是和基準(zhǔn)數(shù)據(jù)進行比較，無論在什么位置，最后的目的就是把基準(zhǔn)數(shù)據(jù)放在中間，小的放前面大的放后面。
====================================================
實例5：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QuickSorter
{
class Program
{
static void Main(string[] args)
{
int[] n = { 23, 45, 60, 10, 17, 101,12};
QuickSort qs = new QuickSort();
qs.QuickSortFunc(n, 0, n.Length - 1);
for (int i = 0; i < n.Length; i++)
{
Console.WriteLine(n[i]);
}
Console.ReadLine();
}
}
class QuickSort
{
//方法一：
private int Func(int[] n, int left, int right)
{
int baseNum = n[left]; // 基準(zhǔn)數(shù)據(jù)
int i = left;
int j = right;
while (true)
{
if (n[i] < baseNum && i < j)
{
i++;
}
else if (n[i] > baseNum && i < j)
{
int number = n[i];
n[i] = n[j];
n[j] = number;
j--;
}
else if (n[j] < baseNum && i < j)
{
int number = n[i];
n[i] = n[j];
n[j] = number;
i++;
}
else if (n[j] > baseNum && i < j)
{
j--;
}
else if (i == j)
{
n[i] = baseNum;
break;
}
}
return i;
}
public void QuickSortFunc(int[] n, int left, int right)
{
//左下標(biāo)一定小于右下標(biāo)，否則就超越了
if (left < right)
{
//對數(shù)組進行分割，取出下次分割的基準(zhǔn)標(biāo)號
int i = Func(n, left, right);
//對“基準(zhǔn)標(biāo)號“左側(cè)的一組數(shù)值進行遞歸的切割，以至于將這些數(shù)值完整的排序
QuickSortFunc(n, left, i - 1);
//對“基準(zhǔn)標(biāo)號“右側(cè)的一組數(shù)值進行遞歸的切割，以至于將這些數(shù)值完整的排序
QuickSortFunc(n, i + 1, right);
}
}
//end 方法一
//方法二：其實我們還可以取中間的數(shù)作為基準(zhǔn)，具體示例如下：
private void Sort(int[] numbers, int left, int right)
{
//左邊索引小于右邊，則還未排序完成
if (left < right)
{
//取中間的元素作為比較基準(zhǔn)，小于他的往左邊移，大于他的往右邊移
int middle = numbers[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle && i < right) ;
while (numbers[--j] > middle && j > 0) ;
if (i >= j)
break;
Swap(numbers, i, j);
}
Sort(numbers, left, i - 1);
Sort(numbers, j + 1, right);
for (int k = 0; k < numbers.Length; k++)
{
Console.WriteLine(numbers[k]);
}
Console.ReadLine();
}
}
private void Swap(int[] numbers, int i, int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}
//end 方法二
}
}
