資料結構五大排序詳解（插入排序、希爾排序、選擇排序、冒泡排序、快速排序）
- 1、排序的概念
- 2、資料結構五大排序
- 2.1 插入排序
- 2.2 希爾排序
- 2.3 選擇排序
- 2.4 冒泡排序
- 2.5 快速排序
- 2.5.1 hoare版本（左右指標法）
- 2.5.2 挖坑法
- 挖坑法之遞回實作
- 挖坑法之非遞回實作
- 2.5.3 前后指標法
1、排序的概念
1、排序的概念
- 排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，
- 穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，
- 內部排序：資料元素全部放在記憶體中的排序，
- 外部排序：資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，
2、常見的排序演算法
2、資料結構五大排序
2.1 插入排序
1、基本思想：
- 直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有記錄插入完為止，得到一個新的有序序列，
- 實際中我們玩撲克牌的時候，就用了插入排序的思想，
2、基本程序
- 假如第一個數已經排好序
- 第一個數的后一個數記為temp，將temp與第一個數進行比較，如果小于第一個數，則第一個數與temp交換位置
- 再將第三個數記為temp，temp依次向前比較，若小于前面的數，則交換位置，若大于前面的位置，則保持不動，temp指向下一個值
- 后面的數和前面的比較方法相同，直到整個序列有序為止
圖解：
代碼實作：
void InsertSort(int *arr, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;//end有序數列最后一個元素的下標
int temp = arr[end + 1];//temp待插入的元素
while (end >= 0)
{
if (temp <= arr[end])
{
arr[end + 1] = arr[end];
--end;
}
else
break;
}
arr[end + 1] = temp;
}
}
總結：
1、再待排序的元素當中，假設前n-1個元素都是已經排好序的，然后將第n個元素插入到已經排好的序列當中，使得前n個元素有序，按照此種方法將資料進行插入，直到完全有序，
2、在此排序中我們在所有資料沒有完全插入以前，并不能確定每個資料的位置，直到所有資料完全插入，
3、元素集合越接近有序，插入排序演算法的時間效率就越高
4、時間復雜度：O(N^2)
5、空間復雜度：O(1)，它是一種穩定的排序演算法
6、穩定性：穩定
2.2 希爾排序
1、基本思想
希爾排序法又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數n，把待排序檔案中所有記錄每隔n進行分組，并將距離為n的元素分為一組，然后再進行插入排序，在取一個比小的數，重復上述操作，直到n等于1為止，
2、基本步驟
- 先選定一個小于N的整數gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對每一組的元素進行直接插入排序，然后再取一個比第一個增量小的整數作為第二增量，再重復上述操作…
- 當增量的大小減到1時，就相當于整個數列被分到了一組，再進行一次直接插入排序，排序完成，
圖解
代碼實作：
void ShellSort(int *arr, int n)
{
int gap = n;
while (gap > 1)
{
//每次將gap縮小一半
gap /= 2;
for (int i = 0; i < n-gap; ++i)
{
int end = i;
int temp = arr[end + gap];
while (end >= 0)
{
if (temp < arr[end])
{
arr[end + gap] = arr[end];
end-=gap;
}
else
break;
}
arr[end+gap] = temp;
}
}
}
特性總結：
1、希爾排序是對直接插入排序的優化，
2、當gap>1時都是預排序，目的是讓陣列更接近于有序，當gap==1時，陣列已經接近于有序了，這樣就會很快，這樣整體而言，可以達到優化的效果，我們是實作后可以進行性能測驗的比對，
3、希爾排序的時間復雜度不好計算，需要進行推導，對匯出來平均時間復雜度：O(N^1.3—N ^2)
4、穩定性：不穩定
2.3 選擇排序
1、基本思想
每次從待排序的資料元素中選出最大（或最小）的一個元素，存放子序列的起始位置，知道待排序的資料元素排完，實際上，我們可以一趟選出兩個值，一個最大值一個最小值，然后將其放在序列開頭和末尾，這樣可以使選擇排序的效率快一倍，
2、基本程序
- 在元素集合array[i]–array[n-1]中選擇關鍵碼最大（小）的資料元素
- 若他不是這組元素中的最后一個元素，則將它與這組元素中的最后一個（第一個）元素交換
- 在剩余的array[i]–array[n-2]（array[i-1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
圖解：
代碼實作：（此處是先選擇最大的和最小的排在開頭和結尾可以將效率提高一倍）
void SelectSort(int *arr, int n)
{
//參與單趟排序的第一個數和最后一個數的下標
int begin = 0, end = n - 1;
while (begin < end)
{
int max = begin;//max最大值的下標
int min = begin;//min最大值的下標
for (int i = begin; i <= end; ++i)
{
if (arr[i]>arr[max])
max = i;
if (arr[i] < arr[min])
min = i;
}
swap(&arr[min], &arr[begin]);//最小值放在開頭
if (begin == max)//防止最大的數在begin位置被換走
max = min;
swap(&arr[max], &arr[end]);
++begin;
--end;
}
}
特性總結
-
直接選擇排序思路非常好理解，但是效率不是很好，實際當中很少使用
-
時間復雜度：O(N^2)
-
空間復雜度：O(1)
-
穩定性：不穩定
2.4 冒泡排序
1、基本思想：將最大的數依次向后移動，第一趟下來最大的在最左邊，
2、基本程序：
-
假設一共有M個元素需要排序，比較相鄰的元素，如果第一個比第二個大（或小），則進行交換，
-
按照既定順序，對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，第一輪比較完成以后，最后的元素應該會是整個元素列中最大（或最小）的數，
-
第N（N<M）輪比較結束后，會有N個元素已經被放置在正確的順序位置，即每輪排序的最后一個元素，針對所有的剩余的元素（M-N）重復以上的步驟，
-
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
圖解
代碼實作
void BubbleSort(int *arr, int n)
{
int end = n;
while (end)
{
int flag = 0;
for (int i = 1; i < end; ++i)
{
if (arr[i - 1]>arr[i])
{
swap(&arr[i], &arr[i - 1]);
flag = 1;
}
}
--end;
}
}
特性總結
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩定性：穩定
2.5 快速排序
快速排序是Hoare與1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素中的某元素作為基準值，按照該排序碼將待排序集合分割成兩個子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后對左右子序列重復這個程序，直到所有元素都排列在相應位置上為止，
將區間按斬訓準值劃分為左右兩半部分的常見、方式有：
- hoare版本
- 挖坑法
- 前后指標版本
2.5.1 hoare版本（左右指標法）
1、基本程序
- 先選出一個key，基本上都會選擇最左邊或者最右邊
- 再定義一個左指標begin和一個右指標end，左指標從左向右走，右指標從右向左走（需要注意的是：若選擇最左邊的資料作為key,則需要end先走，若選擇最右邊的資料作為key，則需要begin先走）
- 先選取最左邊的數作為key，在走的程序中，若end遇到小于key，則停下，begin開始走，直到begin遇到一個大于key的數時，將begin和end交換位置，end再繼續走，如此進行下去，直到begin和end最終相遇，此時將相遇點的內容與key進行交換
- key交換一次以后，key左邊的數都是小于key，key右邊的數都是大于key
- 再將key左右的數進行同樣的排序，如此反復下去，直到左右只有一個數或者左右數不存在時則排序完成，
圖解：（圖解選擇右邊作為key，左邊同理）
代碼實作：
void QuickSort(int *arr, int begin, int end)
{
//若只存在一個數，則區間不存在
if (begin >= end)
return;
int left = begin, right = end-1;
int key = begin;
while (begin < end)
{
while (arr[end] >= arr[key] && end>begin)
--end;
while (arr[begin] <= arr[key] && end > begin)
++begin;
swap(&arr[begin], &arr[end]);
}
swap(&arr[end], &arr[key]);
key = end;
QuickSort(arr, left, key - 1);
QuickSort(arr, key + 1, right);
}
2.5.2 挖坑法
挖坑法之遞回實作
基本思路：
- 首先選取一個數的位置作為坑位，一般都是最左邊的數，將坑位的數賦值給temp
- 設定兩個指標，一個左指標一個右指標，右指標向左走尋找比坑位小的數，找到后停下來，左指標向右走，尋找比坑位數大的數，找到以后停下來，然后將來將左右指標的數交換位置，最后左右指標相遇的坑位就是temp的位置
- 此時temp左邊的數都比temp小，右邊的數都比temp大
- 左右在重復上述程序，指代左右只有一個數或者不存在時為止，
圖解：
代碼實作
void QuickSort1(int *arr, int begin, int end)
{
//若只存在一個數，則區間不存在
if (begin >= end)
return;
int left = begin, right = end;
int key = arr[begin];
while (begin < end)
{
while (arr[end] >= key && end>begin)
--end;//找小
arr[begin] = arr[end];//小的放左邊的坑里
while (arr[begin] <= key && end > begin)
++begin;//找大
arr[end] = arr[begin];//大的放右邊的坑里
}
arr[begin] = key;
int keyi = begin;
QuickSort1(arr, left, keyi - 1);
QuickSort1(arr, keyi + 1, right);
}
挖坑法之非遞回實作
int PartSort(int *arr, int begin, int end)
{
int key = arr[begin];
while (begin < end)
{
while (key <= arr[end] && begin < end)
--end;
arr[begin] = arr[end];
while (key >= arr[begin] && begin < end)
++begin;
arr[end] = arr[begin];
}
arr[begin] = key;
int meeti = begin;
return meeti;
}
void QuickSort2(int *arr, int begin, int end)
{
stack<int>st;
st.push(end);
st.push(begin);
while (!st.empty())
{
int left = st.top();//左區間
st.pop();
int right = st.top();//右區間
st.pop();
int mid = PartSort(arr, left, right);
//當左區間>=mid-1則證明左區間已經排好序
if (left < mid - 1)
{
st.push(mid - 1);
st.push(left);
}
//當mid+1>=右區間則證明區間已將排好序
if (right>mid + 1)
{
st.push(right);
st.push(mid + 1);
}
}
}
2.5.3 前后指標法
基本思路
- 先選出一個key，一般是最左邊或是最右邊的，
- 指定prev指標指向待排序數列開頭，cur指標指向prev+1，
- 若cur指向的數值小于key，則prev先向后移動一位，然后交換prev和cur指標指向的內容，然后再給cur指標++；
- 若cur指向的內容大于key，則cur指標直接++，如此進行下去，直到cur到達end位置，此時將key和++prev指標指向的內容交換即可，
- 經過一次單趟排序，最終也能使得key左邊的資料全部都小于key，key右邊的資料全部都大于key，
- 然后也還是將key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個資料，或是左右序列不存在時，便停止操作
圖解
代碼實作
void QuickSort3(int *arr, int begin, int end)
{
if (begin >= end)
return;//防止區間不存在
int cur = begin, prev = begin - 1;
int key = end;
while (cur != key)
{
if (arr[cur] < arr[key] && ++prev != cur)
swap(&arr[cur], &arr[prev]);
++cur;
}
swap(&arr[++prev], &arr[key]);
key = prev;
QuickSort3(arr, begin, key - 1);
QuickSort3(arr, key + 1, end);
}
特性總結
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才會叫快速排序
- 時間復雜度：O(N*logN)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301963.html
標籤：其他
下一篇：資料結構之線性表（手繪版）