第一章 常規(guī)排序算法
- 第一章 常規(guī)排序算法
- 一、排序的基本概念
- 排序
- 內(nèi)部排序與外部排序
- 排序的穩(wěn)定性
- 二惠遏、冒泡排序
- 算法思想
- 冒泡排序圖示
- C 語言實現(xiàn)
- Java 語言實現(xiàn)
-
- 算法分析
- 1> 時間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 三舀武、簡單選擇排序
- 算法思想
- 簡單選擇排序圖示
- C 語言實現(xiàn)
- Java 語言實現(xiàn)
-
- 算法分析
- 1> 時間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 四拄养、直接插入排序
- 算法思想
- 直接插入排序圖示：
- C 語言實現(xiàn)
- Java 語言實現(xiàn)
-
- 算法分析
- 1> 時間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 五、希爾排序
- 直接插入排序的特點：
- 希爾排序算法思想：
- 希爾排序圖示
- C 語言實現(xiàn)
- Java 語言實現(xiàn)
-
- 算法分析
- 1> 時間復(fù)雜度
- 2> 空間復(fù)雜度
- 3> 算法穩(wěn)定性
- 六银舱、參考資料
- 一、排序的基本概念
一瘪匿、排序的基本概念
1. 排序
排序： 將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列寻馏。
2. 內(nèi)部排序與外部排序
內(nèi)部排序： 整個排序過程完全在內(nèi)存中進行棋弥。
外部排序： 待排序記錄數(shù)據(jù)量太大，內(nèi)存無法容納全部數(shù)據(jù)操软，排序需要借助外部存儲設(shè)備才能完成嘁锯。
3. 排序的穩(wěn)定性
排序算法的穩(wěn)定性： 如果原始序列中兩個關(guān)鍵字相等的數(shù)據(jù)在排序后仍然保持排序前的順序宪祥，我們稱這樣的排序算法是穩(wěn)定的聂薪。
二、冒泡排序
1. 算法思想
- 對 N 個元素進行冒泡排序蝗羊，需進行 N - 1 趟排序過程藏澳；
- 每趟排序，依次比較兩個相鄰元素耀找，如果前者比后者大翔悠，則交換业崖；否則，不交換蓄愁，直到將當(dāng)前最大值交換到本趟排序的最后双炕。
2. 冒泡排序圖示
3. C 語言實現(xiàn)
void BubbleSort(int r[], int n)
{
int i = 0, j = 0, tmp = 0;
// 外層循環(huán)：進行一趟排序，將當(dāng)前最大值交換到最后
for(i = 0; i < n - 1; i++)
{ // 依次比較兩個相鄰元素撮抓，如果前者比后者大妇斤，則交換
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 語言實現(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> 時間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)的迭代次數(shù)為：n(n-1)/2；
可見冒泡排序的時間復(fù)雜度為：O(n^2)
2> 空間復(fù)雜度
冒泡排序只額外申請了一個臨時空間 tmp丹拯，用于交換兩個變量站超；所以，空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
冒泡排序是 穩(wěn)定的乖酬。
我們簡單說明一下死相，
- 首先，冒泡排序每次交換的是相鄰兩個元素咬像；
- 其次施掏，只有當(dāng) a[j] > a[j + 1] 時才交換，如果 a[j] == a[j + 1] 時不進行交換预明，所以辩昆，相等的數(shù)據(jù)仍然保持原始的順序汁针。
三辉词、簡單選擇排序
1. 算法思想
- 首先敷搪，查找 N 個元素中的最小值捞镰，并將其和第一元素進行交換几迄；
- 然后，在剩下的 N - 1 個元素中找到最小值，并交換的第二個元素；
- 以此類推，共進行 N - 1 趟查找荠商，直到整個序列有序。
2. 簡單選擇排序圖示
3. C 語言實現(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 語言實現(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> 時間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)的迭代次數(shù)為：n(n-1)/2嘹裂；
可見簡單選擇排序的時間復(fù)雜度為：O(n^2)
2> 空間復(fù)雜度
簡單選擇排序只只額外申請了兩個臨時空間 tmp 和 min盯拱，一個用于交換兩個變量拼卵，一個用于記錄當(dāng)前最小值的下標(biāo)壤蚜〈细唬空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
簡單排序算法是 不穩(wěn)定的萧豆。
我們舉一個例子。對于序列：*5, 3, 8, 5, 4, 2，第一趟排序時颂斜，會交換：5 和 2；這樣拾枣，5 和 5 的順序就顛倒了沃疮。
四、直接插入排序
1. 算法思想
- 將第一個元素看做是一個只有一個元素的有序序列梅肤；
- 把第二個元素插入到有序序列中去司蔬，這樣，就構(gòu)造了包含 2 個元素的有序序列姨蝴；
- 依次把第 3,4,5... 個元素插入先前的有序序列俊啼，最終使得整個序列有序。
2. 直接插入排序圖示：
3. C 語言實現(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 語言實現(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> 時間復(fù)雜度
由以上代碼可知：內(nèi)層循環(huán)在最壞情況下的迭代次數(shù)為：n(n-1)/2左医；
平均情況下直接插入排序的時間復(fù)雜度為：O(n^2)
但是授帕，從前面的圖示我們可以看到同木，直接插入排序的比較和交換次數(shù)明顯比前述算法少很多，因此跛十，比前述算法都快彤路。
2> 空間復(fù)雜度
排序只額外申請了一個臨時空間 tmp，用于交換兩個變量芥映；所以洲尊，空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
直接插入排序算法是 穩(wěn)定的。
我們簡單說明一下奈偏，
- 首先坞嘀，直接插入排序每次移動的是相鄰兩個元素；
- 其次惊来，只有當(dāng) tmp > a[j] 時才移動姆吭，如果 tmp == a[j] 時不進行交換，所以唁盏，相等的數(shù)據(jù)仍然保持原始的順序内狸。
五、希爾排序
希爾排序(Shell Sort) 是插入排序的一種厘擂。也稱縮小增量排序昆淡，是直接插入排序算法的一種更高效的改進版本。
1. 直接插入排序的特點：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時刽严，效率高昂灵，即可以達到線性排序的效率。
- 插入排序一般來說是低效的舞萄，因為插入排序每次只能將數(shù)據(jù)移動一位眨补。
2. 希爾排序算法思想：
- 先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組倒脓。所有距離為d1的倍數(shù)的記錄放在同一個組中撑螺。先在各組內(nèi)進行直接插入排序；
- 然后崎弃，取第二個增量d2<d1重復(fù)上述的分組和排序甘晤，直至所取的增量
dt=1(dt < dt-1 < … < d2 < d1)，即所有記錄放在同一組中進行直接插入排序為止饲做。- 方法本質(zhì)上是一種分組插入方法
3. 希爾排序圖示
4. C 語言實現(xiàn)
void ShellSort(int r[], int n)
{
int i = 0, j = 0, delta = 0, tmp = 0;
// 增量從 n/2 開始线婚，每次縮小一半，直到等于 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 語言實現(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> 時間復(fù)雜度
希爾排序的時間復(fù)雜度與選中的 增量d 有關(guān)的盆均，分析希爾排序的時間復(fù)雜度比較麻煩塞弊；這里只給出結(jié)論：
- 在最好情況下，時間復(fù)雜度為：O(n^{1.3})（元素已經(jīng)排序好順序）
- 在最壞情況下，時間復(fù)雜度為：O(n^2)游沿。
- 雖然饰抒，平均情況下時間復(fù)雜度為：O(n^2)，但是奏候，較相同時間復(fù)雜度的其他算法而言，希爾排序相對是最好的唇敞。
2> 空間復(fù)雜度
希爾排序只額外申請了一個臨時空間 tmp蔗草，用于交換兩個變量〗幔空間復(fù)雜度為：O(1)
3> 算法穩(wěn)定性
希爾排序算法是 不穩(wěn)定的咒精。
我們舉一個例子。對于序列：*5, 5, 8, 3, 4, 2旷档，在 delta = 2 時模叙，*5 和 5 的順序會顛倒。根本原因是希爾排序每次移動元素時是跳躍移動的鞋屈。
