一、冒泡排序
概念： 冒泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算
法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
冒泡排序對n個項目需要O(n^2)的比較次數，且可以原地排序。盡管這個算法是最簡單了
解和實作的排序算法之一，但它對於少數元素之外的數列排序是很沒有效率的。
運作流程：
1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元
素應該會是最大的數。
3、針對所有的元素重復以上的步驟，除了最後一個。
4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較
時間復雜度：沒有旗標的冒泡排序為O(n^2)、有旗標的為O(n)
助記碼：
i∈[0,N-1) //循環N-1遍
j∈[0,N-1-i) //每遍循環要處理的無序部分
if( j <= j+1) //比較相鄰兩元素大小
swap(j,j+1) //兩兩排序（升序/降序）
示例代碼：
#include
#define ARRAY_LEN(a) sizeof(a)/sizeof(a[0])
int swap(int *a, int *b)
{
if (*a == *b) /*{{{*/
{
return 0;
}
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
return 0;/*}}}*/
}
int bubble_sort(int *p, int len)
{
int i = 0;/*{{{*/
int j = 0;
int flag = 0;
for (i = 0; i < len-1; i++)
{
flag = 0;
for (j = 0; j < len-i-1; j++)
{
if (p[j] < p[j+1])
{
flag = 1;
swap(&p[j], &p[j+1]);
}
}
if (0 == flag)
{
break;
}
}
return 0;/*}}}*/
}
二、選擇排序
概念： (Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中
找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小
（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
運作流程：
1、比較相鄰的元素。如果第一個比第二個大，就將記錄標記為較大（或者較小）的。
2、將記錄與所有的元素進行比較，得到最終的位置標記。
3、比較記錄標記是否與開始位置是否相等，若不等交換對應的元素。
4、重復上次的過程，知道開始位置只向最後一個元素為止。
時間復雜度：雖然選擇排序的時間復雜度為O(n^2)階，但是交換次數比冒泡排序少多（最多n-1次，
最少0次）了，由於交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。
助記碼：
i∈[0,N-1) //循環N-1遍
min/max = i //記錄開始標記
j∈[i+1,len) //遍循環比較後面的所有元素
min/max = j
if(min != i) //比較記錄標記是否與開始位置是否相等
swap(i,min) //兩兩排序（升序/降序）
示例代碼：
int select_sort(int *p, int len)
{
int i = 0;/*{{{*/
int j = 0;
int max = 0;
for (i = 0; i < len-1; i++)
{
max = i;
for (j = i+1; j < len; j++)
{
if (p[max] <= p[j])
{
max = j;
}
}
if (max != i)
{
swap(&p[i], &p[max]);
}
}
return 0;/*}}}*/
}
三、插入排序
概念:（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序
序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
運作流程:
1、從第一個元素開始，該元素可以認為已經被排序
2、取出下一個元素，在已經排序的元素序列中從後向前掃描
3、如果該元素（已排序）大於新元素，將該元素移到下一位置
4、重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
5、將新元素插入到該位置後
6、重復步驟2~5
時間復雜度:O(n^2)階
助記碼：
i∈[1,N) //循環N-1遍
tmp = a[i] //保存要插入的數據
j∈[0, i-1](desc) && a[j] < tmp //查找需要插入的位置
a[j+1] = a[j]; //移動到下一位置
a[j+1] = tmp; //插入
示例代碼：
int insert_sort(int *p, int len)
{
int i = 0;/*{{{*/
int j = 0;
int tmp = 0;
for (i = 1; i < len; i++)
{
tmp = p[i];
for (j = i-1; j >= 0 && p[j] < tmp; j--)
{
p[j+1] = p[j];
}
p[j+1] = tmp;
}
return 0;/*}}}*/
}
四、快速排序
概念:（Quick Sort）是對冒泡排序的一種改進。通過一趟排序將要排序的數據分割成獨立的兩部分，
其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行
快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
運作流程:
1、從數列中挑出一個元素，稱為 "基準"（pivot），
2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的
後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱
為分區（partition）操作。
3、遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
時間復雜度：最差時間復雜度O(n^2),最優時間復雜度O(nlogn)
助記碼: 略
示例代碼：
int quick_sort(int *p, int start, int end)
{
int i = 0;/*{{{*/
int j = 0;
if (start < end)
{
i = start;
j = end+1;
while (1)
{
do
{
i++;
} while (p[i] <= p[start] && i != end);
do
{
j--;
} while (p[j] >= p[start] && j != start);
if (i < j)
{
swap(&p[i], &p[j]);
}
else
{
break;
}
}
swap(&p[start], &p[j]);
quick_sort(p, start, j-1);
quick_sort(p, j+1, end);
}
return 0;/*}}}*/
}
留言列表
