第一章 常規(guī)排序算法
- 第一章 常規(guī)排序算法
- 一、排序的基本概念
- 排序
- 內(nèi)部排序與外部排序
- 排序的穩(wěn)定性
- 二、冒泡排序
- 算法思想
- 冒泡排序圖示
- C 語(yǔ)言實(shí)現(xiàn)
- Java 語(yǔ)言實(shí)現(xiàn)
-
- 算法分析
- 1> 時(shí)間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 三、簡(jiǎn)單選擇排序
- 算法思想
- 簡(jiǎn)單選擇排序圖示
- C 語(yǔ)言實(shí)現(xiàn)
- Java 語(yǔ)言實(shí)現(xiàn)
-
- 算法分析
- 1> 時(shí)間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 四、直接插入排序
- 算法思想
- 直接插入排序圖示：
- C 語(yǔ)言實(shí)現(xiàn)
- Java 語(yǔ)言實(shí)現(xiàn)
-
- 算法分析
- 1> 時(shí)間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 五、希爾排序
- 直接插入排序的特點(diǎn)：
- 希爾排序算法思想：
- 希爾排序圖示
- C 語(yǔ)言實(shí)現(xiàn)
- Java 語(yǔ)言實(shí)現(xiàn)
-
- 算法分析
- 1> 時(shí)間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 六、參考資料
- 一、排序的基本概念
一、排序的基本概念
1. 排序
排序： 將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。
2. 內(nèi)部排序與外部排序
內(nèi)部排序： 整個(gè)排序過(guò)程完全在內(nèi)存中進(jìn)行。
外部排序： 待排序記錄數(shù)據(jù)量太大，內(nèi)存無(wú)法容納全部數(shù)據(jù)，排序需要借助外部存儲(chǔ)設(shè)備才能完成。
3. 排序的穩(wěn)定性
排序算法的穩(wěn)定性： 如果原始序列中兩個(gè)關(guān)鍵字相等的數(shù)據(jù)在排序后仍然保持排序前的順序，我們稱這樣的排序算法是穩(wěn)定的。
二、冒泡排序
1. 算法思想
- 對(duì) N 個(gè)元素進(jìn)行冒泡排序，需進(jìn)行 N - 1 趟排序過(guò)程；
- 每趟排序，依次比較兩個(gè)相鄰元素，如果前者比后者大，則交換；否則，不交換，直到將當(dāng)前最大值交換到本趟排序的最后。
2. 冒泡排序圖示
3. C 語(yǔ)言實(shí)現(xiàn)
void BubbleSort(int r[], int n)
{
int i = 0, j = 0, tmp = 0;
// 外層循環(huán)：進(jìn)行一趟排序，將當(dāng)前最大值交換到最后
for(i = 0; i < n - 1; i++)
{ // 依次比較兩個(gè)相鄰元素，如果前者比后者大，則交換
for(j = 0; j < n - 1 - i; j++)
{
if(r[j] > r[j + 1])
{
tmp = r[j];
r[j] = r[j + 1];
r[j + 1] = tmp;
}
}
}
}
4. Java 語(yǔ)言實(shí)現(xiàn)
public void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}
5. 算法分析
1> 時(shí)間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)的迭代次數(shù)為：n(n-1)/2；
可見(jiàn)冒泡排序的時(shí)間復(fù)雜度為：O(n^2)
2> 空間復(fù)雜度
冒泡排序只額外申請(qǐng)了一個(gè)臨時(shí)空間 tmp，用于交換兩個(gè)變量；所以，空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
冒泡排序是 穩(wěn)定的。
我們簡(jiǎn)單說(shuō)明一下，
- 首先，冒泡排序每次交換的是相鄰兩個(gè)元素；
- 其次，只有當(dāng) a[j] > a[j + 1] 時(shí)才交換，如果 a[j] == a[j + 1] 時(shí)不進(jìn)行交換，所以，相等的數(shù)據(jù)仍然保持原始的順序。
三、簡(jiǎn)單選擇排序
1. 算法思想
- 首先，查找 N 個(gè)元素中的最小值，并將其和第一元素進(jìn)行交換；
- 然后，在剩下的 N - 1 個(gè)元素中找到最小值，并交換的第二個(gè)元素；
- 以此類推，共進(jìn)行 N - 1 趟查找，直到整個(gè)序列有序。
2. 簡(jiǎn)單選擇排序圖示
3. C 語(yǔ)言實(shí)現(xiàn)
void SelectionSort(int r[], int n)
{
int i = 0, j = 0, min = 0, tmp = 0;
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(r[min] > r[j])
{
min = j;
}
}
if(min != i)
{
tmp = r[min];
r[min] = r[i];
r[i] = tmp;
}
}
}
4. Java 語(yǔ)言實(shí)現(xiàn)
public void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = a[i];
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
min = j;
}
}
if (min != i) {
int tmp = a[min];
a[min] = a[i];
a[i] = tmp;
}
}
}
5. 算法分析
1> 時(shí)間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)的迭代次數(shù)為：n(n-1)/2；
可見(jiàn)簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為：O(n^2)
2> 空間復(fù)雜度
簡(jiǎn)單選擇排序只只額外申請(qǐng)了兩個(gè)臨時(shí)空間 tmp 和 min，一個(gè)用于交換兩個(gè)變量，一個(gè)用于記錄當(dāng)前最小值的下標(biāo)?？臻g復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
簡(jiǎn)單排序算法是 不穩(wěn)定的。
我們舉一個(gè)例子。對(duì)于序列：*5, 3, 8, 5, 4, 2，第一趟排序時(shí)，會(huì)交換：5 和 2；這樣，5 和 5 的順序就顛倒了。
四、直接插入排序
1. 算法思想
- 將第一個(gè)元素看做是一個(gè)只有一個(gè)元素的有序序列；
- 把第二個(gè)元素插入到有序序列中去，這樣，就構(gòu)造了包含 2 個(gè)元素的有序序列；
- 依次把第 3,4,5... 個(gè)元素插入先前的有序序列，最終使得整個(gè)序列有序。
2. 直接插入排序圖示：
3. C 語(yǔ)言實(shí)現(xiàn)
void InsertSort(int r[], int n)
{
int i = 0, j = 0, tmp = 0;
printf("直接插入排序：");
for(i = 1; i < n; i++)
{
tmp = r[i];
for(j = i - 1; j >= 0 && tmp < r[j]; j--)
{
r[j + 1] = r[j];
}
r[j + 1] = tmp;
}
}
4. Java 語(yǔ)言實(shí)現(xiàn)
public void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int tmp = a[i];
int j = 0;
for (j = i - 1; j >= 0 && tmp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}
5. 算法分析
1> 時(shí)間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)在最壞情況下的迭代次數(shù)為：n(n-1)/2；
平均情況下直接插入排序的時(shí)間復(fù)雜度為：O(n^2)
但是，從前面的圖示我們可以看到，直接插入排序的比較和交換次數(shù)明顯比前述算法少很多，因此，比前述算法都快。
2> 空間復(fù)雜度
排序只額外申請(qǐng)了一個(gè)臨時(shí)空間 tmp，用于交換兩個(gè)變量；所以，空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
直接插入排序算法是 穩(wěn)定的。
我們簡(jiǎn)單說(shuō)明一下，
- 首先，直接插入排序每次移動(dòng)的是相鄰兩個(gè)元素；
- 其次，只有當(dāng) tmp > a[j] 時(shí)才移動(dòng)，如果 tmp == a[j] 時(shí)不進(jìn)行交換，所以，相等的數(shù)據(jù)仍然保持原始的順序。
五、希爾排序
希爾排序(Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。
1. 直接插入排序的特點(diǎn)：
- 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。
- 插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
2. 希爾排序算法思想：
- 先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；
- 然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量
dt=1(dt < dt-1 < … < d2 < d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?/li>- 方法本質(zhì)上是一種分組插入方法
3. 希爾排序圖示
4. C 語(yǔ)言實(shí)現(xiàn)
void ShellSort(int r[], int n)
{
int i = 0, j = 0, delta = 0, tmp = 0;
// 增量從 n/2 開(kāi)始，每次縮小一半，直到等于 1
for(delta = n / 2; delta > 0; delta /= 2)
{
for(i = delta; i < n; i++)
{
tmp = r[i];
for(j = i - delta; j >= 0 && tmp < r[j]; j -= delta)
{
r[j + delta] = r[j];
}
r[j + delta] = tmp;
}
}
}
5. Java 語(yǔ)言實(shí)現(xiàn)
public void shellSort(int[] a) {
for (int delta = a.length / 2; delta > 0; delta /= 2) {
for (int i = delta; i < a.length; i++) {
int tmp = a[i];
int j = 0;
for (j = i - delta; j >= 0 && tmp < a[j]; j -= delta) {
a[j + delta] = a[j];
}
a[j + delta] = tmp;
}
}
}
6. 算法分析
1> 時(shí)間復(fù)雜度
希爾排序的時(shí)間復(fù)雜度與選中的 增量d 有關(guān)的，分析希爾排序的時(shí)間復(fù)雜度比較麻煩；這里只給出結(jié)論：
- 在最好情況下，時(shí)間復(fù)雜度為：O(n^{1.3})（元素已經(jīng)排序好順序）
- 在最壞情況下，時(shí)間復(fù)雜度為：O(n^2)。
- 雖然，平均情況下時(shí)間復(fù)雜度為：O(n^2)，但是，較相同時(shí)間復(fù)雜度的其他算法而言，希爾排序相對(duì)是最好的。
2> 空間復(fù)雜度
希爾排序只額外申請(qǐng)了一個(gè)臨時(shí)空間 tmp，用于交換兩個(gè)變量。空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
希爾排序算法是 不穩(wěn)定的。
我們舉一個(gè)例子。對(duì)于序列：*5, 5, 8, 3, 4, 2，在 delta = 2 時(shí)，*5 和 5 的順序會(huì)顛倒。根本原因是希爾排序每次移動(dòng)元素時(shí)是跳躍移動(dòng)的。
六、參考資料
- 算法動(dòng)畫：http://jsdo.it/norahiko/oxIy/fullscreen
