1. 插入排序
=====================================================
算法思想簡單描述：
在要排序的一組數(shù)中驰徊，假設(shè)前面(n-1) [n>=2] 個(gè)數(shù)已經(jīng)是排
好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中堕阔，使得這n個(gè)數(shù)
也是排好順序的棍厂。如此反復(fù)循環(huán)，直到全部排好順序超陆。
直接插入排序是穩(wěn)定的牺弹。算法時(shí)間復(fù)雜度O(n2)--[n的平方]
一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)时呀。具體算法描述如下：
1.從第一個(gè)元素開始张漂，該元素可以認(rèn)為已經(jīng)被排序
2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素退唠，將該元素移到下一位置
4.重復(fù)步驟3鹃锈，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復(fù)步驟2~5
如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目瞧预。該算法可以認(rèn)為是插入排序的一個(gè)變種屎债，稱為二分查找排序。
使用插入排序?yàn)橐涣袛?shù)字進(jìn)行排序的過程
最差時(shí)間復(fù)雜度 O(n^2)
最優(yōu)時(shí)間復(fù)雜度 O(n)
平均時(shí)間復(fù)雜度O(n^2)
=====================================================
實(shí)例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)
{
//從第二個(gè)元素開始遍歷
for (int i = 1; i < list.Length;++i )
{
//將第i個(gè)元素賦值給一個(gè)臨時(shí)變量
int t = list[i];
//記錄第i個(gè)元素的下標(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. 希爾排序
希爾排序躯喇，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本硝枉。希爾排序是非穩(wěn)定排序算法廉丽。
====================================================
算法思想簡單描述：
在直接插入排序算法中，每次插入一個(gè)數(shù)妻味，使有序序列只增加1個(gè)節(jié)點(diǎn)正压，
并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為
增量）的數(shù)责球，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素焦履，則進(jìn)行一次比較就可能消除
多個(gè)元素交換拓劝。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)
了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組嘉裤，每組中
記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序郑临，然后再用一個(gè)較小的增量
對(duì)它進(jìn)行，在每組中再進(jìn)行排序屑宠。當(dāng)增量減到1時(shí)厢洞，整個(gè)要排序的數(shù)被分成
一組，排序完成侨把。
下面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)犀变，初次取序列的一半為增量，
以后每次減半秋柄，直到增量為1获枝。
希爾排序是不穩(wěn)定的。
原始的算法實(shí)現(xiàn)在最壞的情況下需要進(jìn)行O(n2)的比較和交換骇笔。V. Pratt的書[1] 對(duì)算法進(jìn)行了少量修改省店，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些笨触。
希爾排序通過將比較的全部元素分為幾個(gè)區(qū)域來提升插入排序的性能懦傍。這樣可以讓一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來越小的步長進(jìn)行排序芦劣，算法的最后一步就是普通的插入排序粗俱，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時(shí)插入排序較快）虚吟。
假設(shè)有一個(gè)很小的數(shù)據(jù)在一個(gè)已按升序排好序的數(shù)組的末端寸认。如果用復(fù)雜度為O(n2)的排序（冒泡排序或插入排序），可能會(huì)進(jìn)行n次的比較和交換才能將該數(shù)據(jù)移至正確位置串慰。而希爾排序會(huì)用較大的步長移動(dòng)數(shù)據(jù)偏塞，所以小數(shù)據(jù)只需進(jìn)行少數(shù)比較和交換即可到正確位置。
一個(gè)更好理解的希爾排序?qū)崿F(xiàn)：將數(shù)組列在一個(gè)表中并對(duì)列排序（用插入排序）邦鲫。重復(fù)這過程灸叼，不過每次用更長的列來進(jìn)行。最后整個(gè)表就只有一列了庆捺。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法古今，算法本身僅僅對(duì)原數(shù)組進(jìn)行排序（通過增加索引的步長，例如是用i += step_size而不是i++）滔以。
排序過程
最差時(shí)間復(fù)雜度 根據(jù)步長串行的不同而不同沧卢。O(nLog2 n)
最優(yōu)時(shí)間復(fù)雜度 O(n)
平均時(shí)間復(fù)雜度 根據(jù)步長串行的不同而不同。
====================================================
實(shí)例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ù)中醉者，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換但狭；
然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)
到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止撬即。
選擇排序是不穩(wěn)定的立磁。算法復(fù)雜度O(n2)--[n的平方]
選擇排序(Selection sort)是一種簡單直觀的排序算法。
它的工作原理如下剥槐。
首先在未排序序列中找到最谐纭（大）元素，存放到排序序列的起始位置粒竖，
然后颅崩，再從剩余未排序元素中繼續(xù)尋找最小（大）元素蕊苗，
然后放到已排序序列的末尾沿后。
以此類推，直到所有元素均排序完畢朽砰。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)尖滚。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)瞧柔。選擇排序每次交換一對(duì)元素漆弄，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換造锅。在所有的完全依靠交換去移動(dòng)元素的排序方法中撼唾，選擇排序?qū)儆诜浅：玫囊环N。
實(shí)現(xiàn)過程
最差時(shí)間復(fù)雜度 О(n)
最優(yōu)時(shí)間復(fù)雜度 О(n)
平均時(shí)間復(fù)雜度 О(n)
=====================================================
實(shí)例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)
{
//對(duì)數(shù)組list從第0個(gè)元素進(jìn)行遍歷
for (int i = 0; i < list.Length - 1; ++i)
{
//記錄第i個(gè)小標(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;
}
//兩個(gè)大小數(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. 冒泡排序
====================================================
算法思想簡單描述：
依次比較相鄰的兩個(gè)數(shù),把大的放前面,小的放后面.即首先比較第1個(gè)數(shù)和第2個(gè)數(shù),大數(shù)放前,小數(shù)放后.然后比較第2個(gè)數(shù)和第3個(gè)數(shù)......直到比較最后兩個(gè)數(shù).第一趟結(jié)束,最小的
一定沉到最后.重復(fù)上過程,仍從第1個(gè)數(shù)開始,到最后第2個(gè)數(shù).然后......
由于在排序過程中總是大數(shù)往前,小數(shù)往后,相當(dāng)氣泡上升,所以叫冒泡排序.
冒泡排序（Bubble Sort倒谷，臺(tái)灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。
它重復(fù)地走訪過要排序的數(shù)列肺素，一次比較兩個(gè)元素恨锚，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換倍靡，也就是說該數(shù)列已經(jīng)排序完成猴伶。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序?qū)個(gè)項(xiàng)目需要O(n^{2})的比較次數(shù)塌西，且可以原地排序他挎。盡管這個(gè)算法是最簡單了解和實(shí)作的排序算法之一，但它對(duì)于少數(shù)元素之外的數(shù)列排序是很沒有效率的捡需。
冒泡排序是與插入排序擁有相等的執(zhí)行時(shí)間办桨，但是兩種法在需要的交換次數(shù)卻很大地不同。在最壞的情況站辉，冒泡排序需要O(n^{2})次交換呢撞，而插入排序只要最多O(n)交換损姜。
冒泡排序的實(shí)現(xiàn)（類似下面）通常會(huì)對(duì)已經(jīng)排序好的數(shù)列拙劣地執(zhí)行（O(n^{2})），而插入排序在這個(gè)例子只需要O(n)個(gè)運(yùn)算殊霞。因此很多現(xiàn)代的算法教科書避免使用冒泡排序摧阅，而用插入排序取代之。冒泡排序如果能在內(nèi)部循環(huán)第一次執(zhí)行時(shí)绷蹲，使用一個(gè)旗標(biāo)來表示有無需要交換的可能棒卷，也有可能把最好的復(fù)雜度降低到O(n)。在這個(gè)情況祝钢，在已經(jīng)排序好的數(shù)列就無交換的需要比规。若在每次走訪數(shù)列時(shí)，把走訪順序和比較大小反過來拦英，也可以稍微地改進(jìn)效率蜒什。有時(shí)候稱為往返排序，因?yàn)樗惴〞?huì)從數(shù)列的一端到另一端之間穿梭往返龄章。
2.算法實(shí)現(xiàn)
1.比較相鄰的元素吃谣。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)做裙。
2.對(duì)每一對(duì)相鄰元素作同樣的工作岗憋，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)锚贱，最后的元素應(yīng)該會(huì)是最大的數(shù)仔戈。
3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)拧廊。
4.持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟监徘，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
3.實(shí)現(xiàn)過程
最差時(shí)間復(fù)雜度 O(n^2)
最優(yōu)時(shí)間復(fù)雜度 O(n)
平均時(shí)間復(fù)雜度O(n^2)
====================================================
實(shí)例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）是對(duì)冒泡排序的一種改進(jìn)倦春。
快速排序的基本概念是：
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分户敬，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，
然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序睁本，整個(gè)排序過程可以遞歸進(jìn)行尿庐，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
下面通過一個(gè)例子來了解快速排序的具體含義： { 23, 45, 60, 10, 17, 101,12}
第一遍排序：
由此思想呢堰，我們可以實(shí)現(xiàn)快速排序的代碼：
注意基準(zhǔn)數(shù)據(jù)永遠(yuǎn)不變抄瑟，永遠(yuǎn)是和基準(zhǔn)數(shù)據(jù)進(jìn)行比較，無論在什么位置枉疼，最后的目的就是把基準(zhǔn)數(shù)據(jù)放在中間皮假，小的放前面大的放后面鞋拟。
====================================================
實(shí)例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)
{
//對(duì)數(shù)組進(jìn)行分割惹资，取出下次分割的基準(zhǔn)標(biāo)號(hào)
int i = Func(n, left, right);
//對(duì)“基準(zhǔn)標(biāo)號(hào)“左側(cè)的一組數(shù)值進(jìn)行遞歸的切割严卖，以至于將這些數(shù)值完整的排序
QuickSortFunc(n, left, i - 1);
//對(duì)“基準(zhǔn)標(biāo)號(hào)“右側(cè)的一組數(shù)值進(jìn)行遞歸的切割，以至于將這些數(shù)值完整的排序
QuickSortFunc(n, i + 1, right);
}
}
//end 方法一
//方法二：其實(shí)我們還可以取中間的數(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 方法二
}
}
