冒泡排序、選擇排序和插入排序

一、冒泡排序

依次比較相鄰的兩個數，将小數放在前面，大數放在後面。即首先比較第1個和第2個數，将小數放前，大數放後。然後比較第2個數和第3個數，将小數放前，大數放後，如此繼續，直至比較最後兩個數，将小數放前，大數放後。重複以上過程，直至最終完成排序。

冒泡排序是穩定的。算法時間複雜度是O(n ^2)。

程式實作示例

将數組從小到大排列

public void BubbleSort(int[] array)

{

　　int length = array.Length;

　　for (int i = 0; i <= length - 1; i++)

　　{

　　for (int j = length - 1; j > i; j--)

　　if (array[j] < array[j - 1] )

　　int temp = array[j];

　　array[j] = array[j - 1];

　　array[j - 1] = temp;

}

二、 選擇排序

每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。 選擇排序是不穩定的排序方法。

選擇排序是不穩定的。算法複雜度是O(n ^2 )。

public void ChoiceSort (int [] array)

int min;

for(int i=0;i< array.Length-1;i++)

min=i;

for(int j=i+1;j< array.Length;j++)

if(list[j]<list[min])

min=j;

int t=list[min];

list[min]=list[i];

list[i]=t;

三、 插入排序

每次從無序表中取出第一個元素，把它插入到有序表的合适位置，使有序表仍然有序。

直接插入排序是穩定的。算法時間複雜度是O(n ^2)

public void InsertSort (int [] array)

for(int i=1;i< array.Length;i++)

int temp = array [i];//從無序表中取出的數，放在temp裡面

// j>0&&temp< array [j-1]為每一輪排序停止的條件

　　 for(int j=i;j>0&&temp< array [j-1];j--)

　　 {

　　 array[j]= array[j-1];

　　 }

　　 array[j]=temp;

ps:

1） 穩定的：如果存在多個具有相同排序碼的記錄，經過排序後，這些記錄的相對次序仍然保持不變，則這種排序算法稱為穩定的。

插入排序、冒泡排序、歸并排序、配置設定排序（桶式、基數）都是穩定的排序算法。

2）不穩定的：否則稱為不穩定的。

直接選擇排序、堆排序、shell排序、快速排序都是不穩定的排序算法。

本文轉自linzheng 51CTO部落格，原文連結:http://blog.51cto.com/linzheng/1081853