排序
文章目錄
- 排序
- 排序的概念
- 直接插入排序
- 希爾排序
- 選擇排序
- 堆排序
- 冒泡排序
- 快速排序
- 1.hoare版本
- 2.挖坑法
- 前后指標法
- 快排的非遞回方法（回圈）
- 時間復雜度優化問題
- 歸并排序
- 遞回法
- 非遞回法
- 計數排序
- 總結
排序的概念
- 排序 ：所謂排序就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作
- 排序的穩定性： 排序前后兩個相等的數相對位置不變，則演算法穩定，
穩定性是一種人為刻意為之的行為，任何一個穩定的排序方法都可以寫成不穩定的，穩定性的意義在于確定值相等的值的輸入順序，有一定參考作用，
同時 還有兩個比較基礎的概念：
- 內部排序： 資料元素全部放在記憶體中的排序
- 外部排序： 資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序
直接插入排序
插入排序的思想十分的簡單：
把待排序的元素插入到一個 有序序列 的 正確的位置，直到所有的記錄插入完全為止，得到一個新的有序序列，
其實我們在玩撲克牌的時候就是這個思想
為了能更好的理解插入排序，我們從他的一次回圈看起：（以升序為例）
-
假設陣列a為一個前（end+1）個數有序陣列，我們要把第end+1個數插入陣列中
-
回圈的基本思路是： 如果a[end]比temp（待插入的數）要小，就說明還要繼續往下尋找，這是執行
a[end+1]=a[end]，并將end- -，回圈的條件時end >=0
-
直到找到比 temp要小的數 或者 end==0 時還沒有找到，這時就要跳出回圈執行：
a[end+1]=temp
注意： 這里如果end==0時還沒有找到的時候，出回圈的時候end為-1，但是a[end+1]實際上還是第一個元素
-
這是直接插入排序的一次單次回圈，實際上我們發現直接插入排序一個重要的前提是要有一個有序的陣列，
在排序的最開始 我們可以認定第一個數為一個大小為1的有序陣列，來啟動上述介紹的單次回圈，回圈結束我們就得到了一個前兩個元素有序的陣列 …直到前n-1個元素（陣列大小為n）有序，將最后一個元素插入，這是最后一次回圈， 所以我們還要在上面單次回圈的基礎上在加一個回圈來完成排序
代碼
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int temp = a[i + 1];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = temp;
}
}
總結
- 時間復雜度：
O(N^2) - 空間復雜：
O(1) - 穩定性：穩定
希爾排序
希爾排序實際上是在插入排序的基礎上做出了一些改進，希爾排序又叫縮小增量法，
其基本思想是：
將陣列按一定間隔分成若干個組，對每個組里面的元素進行直接選擇排序，然后縮小間隔，在對重新分的組挨個進行選擇排序…直到最后間隔為1（實際上直接插入排序是間隔為1的希爾排序）
- 我們以一個陣列為例進行希爾排序：
- 然后就要對陣列進行分組排序，第一次我們把間隔gap設為5
- 然后我們要不斷縮小間隔，在進行重新分組并排序，這次我們把間隔調成2
- 最后一次我們把間隔gap調成1
我們從中可以發現一些規律：
- 希爾排序是對直接插入排序的一種優化
- 隨著gap的不斷減小，陣列越來越趨于有序，其實gap>1時都是預排序，目的是讓陣列更有序，gap==1時，陣列已近接近有序，這樣最后一次排序就很快，達到優化的效果，
- 希爾排序的時間復雜度不好去計算，因為gap的取值方法很多，導致很難去計算，
代碼
void ShellSort(int* a, int n)
{
int gap = n ;
while (gap > 1)
{
gap = gap / 3 + 1; //注意這里是以三倍的速度縮小gap，這里+1是因為要保證最后一次gap為1
for (int i = 0; i < n -gap; i++)
{
int end = i;
int temp = a[i + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = temp;
}
}
}
總結
- 時間復雜度：
O(N^1.25)這是通過大量實驗得到的經驗公式 - 空間復雜：
O(1) - 穩定性：不穩定
選擇排序
基本思路：
每次遍歷整個陣列從陣列中選擇出最大的數（或最小的數），最放到陣列的末尾（或陣列的首尾），直到全部待排序的資料元素排完
我們以一個陣列為例：
- 在begin和end之間（包括begin和end）中找到max和min，并讓min和begin、max和end交換
注意：這里交換的先后順序，到后面會有些區別！
- 按上述步驟不斷重復
- 最后一次交換比較有代表意義，是一個容易犯的錯誤，如果先讓begin和min交換再讓max和end交換會產生一個問題：那就是max和begin重合的時候，如果begin先和min交換，那么max的值會被交換到min上，這時就需要end和min交換
代碼：
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int min = begin;
int max = end;
for (int i = begin+1; i < end;i++)
{
if (a[i] > a[max])
max = i;
if (a[i] < a[min])
min = i;
}
swap(&a[begin], &a[min]);
if (begin != max)
swap(&a[end], &a[max]);
else
swap(&a[end], &a[min]);
begin++;
end--;
}
}
總結：
- 時間復雜度：
O(N^2) - 空間復雜：
O(1) - 穩定性：不穩定
堆排序
可以參考一下以前的博客：資料結構：堆 的詳解
代碼：
void AjustDown(int* a, int n, int parents)
{
int child = 2 * parents + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
child++;
if (a[child] > a[parents])
swap(&a[child], &a[parents]);
parents = child;
child = 2 * parents + 1;
}
}
void HeapSort(int* a, int n)
{
for (int i = n/2-1 ; i >= 0; i--)
{
AjustDown(a,n,i);
}
for (int i = n-1; i >0 ; i--)
{
swap(&a[0], &a[i]);
AjustDown(a, i, 0);
}
}
總結：
- 時間復雜度：
O(N*logN) - 空間復雜：
O(1) - 穩定性：不穩定
冒泡排序
基本思想： 就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，在視覺上的效果像：較大鍵值的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動，
- 我們以冒泡排序的一次遍歷為例：
遍歷的規則是：兩兩進行比較，如果前者大于后者就交換，否則就繼續往下走，這里要注意一下a[j]的范圍是閉區間[0,n-2]，也就是n-1次比較，
看完一次回圈大家或許就理解了冒泡排序名字的由來，最大的數像氣泡一樣向上移動，在往下思考這次遍歷過后，實際上最后一個已經是有序的了，所以還要進行n-1次這樣的遍歷，所以時間復雜的是O((n-1)+(n-2)+(n-3)+(n-4).....+0)=O(n^2)
代碼
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int k = 0;
for (int j = 0; j < n - 1 - i; j++) //每一次遍歷結束，下一次要遍歷的個數都會減少一個
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
k = 1;
}
}
if (k == 0)
break;
}
}
- 這里特意設計了以個變數K，來面對 陣列已經是有序的情況 ，如果陣列有序的話，就不會進行任何一次交換，所以這時k的值就不會被修改，這樣檢測到未修改，就可以直接跳出回圈了，
總結：
- 時間復雜度：
O(N^2)最好情況是：O(N) - 空間復雜：
O(1) - 穩定性：穩定
快速排序
快排的思路：
任取待排序元素序列中的某元素作為基準值，按照該基準值將排序分成兩個子序列，左子序列的元素均小于基準值，右子序列的元素均大于基準值，，然后在左、右子序列重復上述程序，直到所有元素都有序為止
下面介紹快排的三個版本：
1.hoare版本
思路：
- 首先從頭部或者尾部選出一個值做key（基準值），這里取頭部元素a[0]
- 右邊先找（這個很重要！！！！），從陣列尾部開始尋找比key小的值，找到后停止，
- 左邊去找，從陣列首部開始尋找比key大的值，找到后與右邊的進行交換
- 重復上述步驟直到左邊與右邊相遇為止，這時把key與相遇位置的值進行交換，完成排序！
看完這個思路之后，我們直到整體思路就是，從左邊找比基準值大的與右邊找到的比基準值小的進行交換，但是在這里要思考清楚一個問題：
既然最后一步是將相遇的值與key的值交換，也就是說明左右相遇時指向的值一定比key小，這是為什么？
我們從兩個情況去考慮：
- 首先是左邊移動與右邊相遇，這毋庸置疑右邊本來就是找比key小的值，所以相遇時指的值一定比key小
- 其次時右邊移動與左邊相遇，這種情況也分兩種情況，一種就是左邊從來就沒移動過，還指向key值，這是key值與自己交換，第二種是左邊移動過一次或多次，雖然左邊是找比key大的值，但不要忘了在右找左之前，會交換左右的值，交換過后左邊就是比key小的值，相遇時也就是比key小的值
我們以第一次回圈為例：
這里我們就實作了把陣列分成了兩個子序列（左子序列的元素均小于基準值，右子序列的元素均大于基準值），然后我們把這兩個子序列看成一個新的序列，對其指向執行相同的程式，并一直遞回下去，直到 傳進去的陣列的 大小為 0 （沒有左子序列 或 右子序列 也就是key比該序列的所有元素都要大或小） 或 1（沒有執行程式的必要），實際上執行的思路入下圖所示
代碼
void QuickSort1(int* a, int n) //hoare版本
{
if (n == 1 || n == 0)
return;
int key = 0;
int left = 0; //這里必須從0開始，如果從1開始，當陣列只有兩個的時候代碼會出現問題
int right = n - 1;
while (left < right) //這里必須是小于號保證出回圈left一定等于right
{
while (left<right && a[right] > a[key])
right--;
while (left<right && a[left] <= a[key]) //注意這里的大于等于號 因為key在左邊，為了讓key往左走必須大于等于
left++;
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
key = left;
QuickSort1(a, key);
QuickSort1(a + key + 1, n - key - 1);
}
2.挖坑法
思路：
- 首先從頭部或者尾部選出一個值做key（基準值），把key的值拷貝給臨時變數temp，并把陣列第一個元素當作第一個“坑”
- 右邊先找（這個很重要！！！！），從陣列尾部開始尋找比key小的值，然后填上面挖的“坑”，
- 左邊去找，從陣列首部開始尋找比key大的值，找到后填上面挖的“坑”
- 重復上述步驟直到左邊與右邊相遇為止，這時把temp與相遇位置的“坑”填上，完成排序！
我們以一次回圈作為基礎：
- 首先我們選擇首元素作為第一個坑
- 然后右邊找小，填到左邊的坑里
- 然后是左邊找大，填到右邊的坑里，后面重復上述步驟
-最后一步左右重合，將temp中的值填入坑內
代碼
void QuickSort2(int* a, int n) //快排——挖坑法
{
if (n == 1 || n == 0)
return;
int key = 0;
int left = 0;
int right = n - 1;
int temp = a[key];
while (left < right)
{
while (left<right && a[right]>temp)
right--;
a[left] = a[right]; //填左邊的坑
while (left<right && a[left]<= temp)
left++;
a[right] = a[left]; //填右邊的坑
}
a[left] = temp; //最后左右相遇時，填坑
key = left;
QuickSort2(a, key);
QuickSort2(a + key + 1, n - key - 1);
}
前后指標法
基本思路： 設定兩個指標（prev，cur），還是在陣列的頭或尾找一個基準值，prev指向第一個元素，cur指向第二個元素，然后cur開始遍歷陣列，找到比基準值小的值就與prev下一個元素交換，直到cur遍歷完陣列，
我們以一次回圈作為基礎：
- 首先我們選擇首元素作為第一個坑
如果沒有遇到比基準值小的數cur就直接往后走，找到比基準值小的數就開始交換，
其實我們還可以把陣列的最后一個數設為基準值，這時程式也要相應的做出一點改變
這時prev的其實位置就必須時陣列第一個數的前一個位置，也就是下表為-1的位置，cur起始位置時陣列的 首元素，其他的步驟與上面的一樣，
代碼
void QuickSort3(int* a, int n) //快排——雙指標法
{
if (n == 1 || n == 0)
return;
int key = 0;
int prev = 0;
int cur = 1;
while (cur < n)
{
if (a[cur] < a[key])
swap(&a[++prev], &a[cur]);
cur++;
}
swap(&a[prev], &a[key]);
key = prev;
QuickSort3(a, key);
QuickSort3(a + key + 1, n - key - 1);
}
快排的非遞回方法（回圈）
把遞回轉換成非遞回有兩種方法：
- 直接轉換成 回圈
- 把遞回問題轉換成 堆疊 + 回圈
因為遞回是把大事化成若干個小問題去解決，回圈正好是反過來人為的從小問題開始解決，但是有時候遞回在把大問題化成小問題的時候，小問題是建立在大問題的基礎上的，不解決大問題就無法得到小問題，所以用回圈就無法從小問題開始解決，這時就要用到堆疊的結構，堆疊的結構正好將這種情況完美解決，從 入堆疊時的大->小 ，到 出堆疊進入回圈時的 小->大
本體思路：
- 首先把陣列的左右邊界先入堆疊
- 然后進入回圈，取出堆疊里第一個區間的左右邊界，并讓左右邊界出堆疊，對齊做單趟排序，這時就的到了key和兩個左右子序列，把左右子序列的左右邊界分別入堆疊，
- 重復上述步驟，直到堆疊為空
注意：
這里要注意入堆疊和出堆疊時的左右邊界的順序，左邊界先入堆疊，右邊界后入堆疊，取堆疊頂元素時就要先取右邊界并出堆疊，再取左邊界
代碼
int Partsort(int* a, int left,int right) //單趟排序
{
int key = left;
int temp =Choose_Key(a,left,right);
swap(&a[temp], &a[left]);
while (left < right)
{
while (left<right && a[right] >= a[key])
right--;
while (left<right && a[left] <= a[key])
left++;
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
return left;
}
void QuickSortNonR(int* a, int n) //快排的非遞回寫法
{
Stack ps;
StackInit(&ps);
StackPush(&ps, 0); // 入左邊界
StackPush(&ps, n - 1); // 入右邊界
while (!StackEmpty(&ps))
{
int end = StackTop(&ps); //右邊界先出堆疊 一定要和上面入堆疊的順序相反！！！！
StackPop(&ps);
int begin = StackTop(&ps); //左邊界出堆疊
StackPop(&ps);
int keyi = Partsort(a, begin, end);
if (keyi + 1 < end) //判斷是否要繼續遞回
{
StackPush(&ps, keyi + 1); // 右子序列的 左邊界入堆疊
StackPush(&ps, end); // 右子序列的 右邊界入堆疊
}
if (begin < keyi-1)
{
StackPush(&ps, begin); //右子序列的 左邊界入堆疊
StackPush(&ps, keyi - 1); // 右子序列的 右邊界入堆疊
}
}
StackDestroy(&ps);
}
時間復雜度優化問題
快排的時間復雜度最快的時候可以達到O(N*logN) ,但是當陣列為有序的時候 或 有大面積重復的時候，時間復雜度會飆升到O(N^2)
為了解決這種情況，首先要了解為什么會出現這種情況？
最主要的原因是 key每次都取到了整個陣列的 最小值或最大值 ，使二叉樹變成單邊樹，這時我們只需要對key選取的值稍加處理就可以了，我們采用三數取中 即選取陣列 左 、 中 、 右 大小在中間的數，與key所在的位置交換，
代碼
int Choose_Key(int *a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[mid] > a[left])
return left;
else
{
if (a[right] > a[mid])
return right;
else
return mid;
}
}
else
{
if (a[mid] > a[right])
return right;
else
{
if (a[left] > a[mid])
return left;
else
return mid;
}
}
}
void QuickSort2(int* a, int n) //以快排——挖坑法為例
{
if (n == 1 || n == 0)
return;
int key = 0;
int t = Choose_Key(a, 0, n - 1); // 選出中間元素的下標
swap(&a[key], &a[t]); //與key所在位置的元素交換
int left = 0;
int right = n - 1;
int temp = a[key];
while (left < right)
{
while (left<right && a[right]>temp)
right--;
a[left] = a[right];
while (left<right && a[left]<= temp)
left++;
a[right] = a[left];
}
a[left] = temp;
key = left;
QuickSort2(a, key);
QuickSort2(a + key + 1, n - key - 1);
}
總結：
- 時間復雜度：
O(N*logN)最壞的情況：O(N^2) - 空間復雜：
O(logN) - 穩定性：不穩定
歸并排序
基本思想
歸并排序（MERGE_SORT) 是建立在歸并操作上的一種有效的排序演算法，該演算法采用分治法的一個典型用例，將已有序的子序列合并，得到完全有序的序列；即使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，
遞回法
如上圖所示，單趟排序的程序是一個很經典的問題，創建一個額外的陣列，將兩個順序的子序列排序，我們只要定義兩個個指標，分別指向 待排序的兩個序列，對指標所指的內容進行比較，如果滿足條件就進入新陣列，重復上述步驟直至所有元素都拷貝到新陣列，
單趟排序思路了解之后，我們直到單趟排序需要兩個有序的序列，所以就用遞回將陣列不斷劃分，當序列只有一個元素的時候我們認為他就是大小為1的有序序列，進行單趟排序，然后把排完序的子序列在進行合并的程序，
void _MergeSort(int* a, int left,int right,int *temp)
{
int mid = (left + right) / 2;
if (left >= right)
return;
_MergeSort(a, left, mid,temp);
_MergeSort(a, mid + 1, right,temp);
int cur1 = left, end1 = mid;
int cur2 = mid + 1, end2 = right;
int cur3 = left;
while (cur1 <= end1 && cur2 <= end2)
{
if (a[cur1] <= a[cur2])
{
temp[cur3] = a[cur1];
cur3++;
cur1++;
}
else
{
temp[cur3] = a[cur2];
cur3++;
cur2++;
}
}
while (cur1 <= end1)
{
temp[cur3] = a[cur1];
cur3++;
cur1++;
}
while (cur2 <= end2)
{
temp[cur3] = a[cur2];
cur3++;
cur2++;
}
for (int i = 0; i <= right; i++)
{
a[i] = temp[i];
}
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(n * sizeof(int));
_MergeSort(a, 0, n - 1, temp);
}
非遞回法
非遞回的思路是
- 我們首先把陣列 兩個一組 分組，組內對半分成兩個子序列（序列大小為1），按照單趟排序排序
- 我們首先把陣列 四個一組 分組，組內對半分成兩個子序列（序列大小為2），按照單趟排序排序
… - 直到陣列 小于等于 分組大小（這時最后一次），組內對半分成兩個子序列（序列大小為2），按照單趟排序排序
注意：
這里的難點是分組的邊界問題
- 當第二個序列完全就不存在時，我們這時對end2進行修改，使其小于begin2，下面的單趟排序，由于受begin2 < end2的限制，會跳過一切與第二個序列有關的步驟，只留下對第一個序列的操作，對end1進行修改使其不會越界，
- 當第二個序列部分存在時，只需要修改end2，使其不會越界即可，
void fun(int cur1,int end1,int cur2,int end2,int cur3,int *temp,int *a)
{
while (cur1 <= end1 && cur2 <= end2)
{
if (a[cur1] <= a[cur2])
{
temp[cur3] = a[cur1];
cur3++;
cur1++;
}
else
{
temp[cur3] = a[cur2];
cur3++;
cur2++;
}
}
while (cur1 <= end1)
{
temp[cur3] = a[cur1];
cur3++;
cur1++;
}
while (cur2 <= end2)
{
temp[cur3] = a[cur2];
cur3++;
cur2++;
}
for (int i = 0; i <= end2; i++)
{
a[i] = temp[i];
}
}
void MergeSortNonR(int* a, int n)
{
int* p = (int*)malloc(n * sizeof(int));
int index = 2;
while ((n*2) / index)
{
int times = n / index;
if (n % index != 0)
times++;
for (int i = 0; i < times; i++)
{
int cur1 = i * index, end1 = cur1+ index/2 -1;
if (end1 > n - 1)
end1 = n - 1;
int cur2 = cur1 + index / 2;
int end2 = cur2 + index/2 - 1;
if (end2 > n - 1)
end2 = n - 1;
int cur3 = cur1;
fun(cur1, end1, cur2, end2, cur3, p, a);
}
index *= 2;
}
free(p);
}
總結：
- 時間復雜度：
O(N*logN) - 空間復雜：
O(N) - 穩定性：穩定
計數排序
思想：
- 統計相同元素出現次數
- 根據統計的結果將序列回收到原來的序列中
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++) //找出最大最小值確定開辟陣列的范圍
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* p = (int*)calloc(range, sizeof(int));
for (int i = 0; i < n; i++)
{
p[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (p[i])
{
a[j++] = i + min;
p[i]--;
}
}
}
總結：
- 時間復雜度：
O(max(N,最大值與最小值之間元素的個數)) - 空間復雜：
O(范圍) - 穩定性：穩定
總結
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(N^2) | O(N) | O(N^2) | O(1) | 穩定 |
| 簡單選擇排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不穩定 |
| 直接插入排序 | O(N^2) | O(N) | O(N^2) | O(1) | 穩定 |
| 希爾排序 | 大概O(N^1.2) | 不確定 | O(N^2) | O(1) | 不穩定 |
| 堆排序 | O(N*logN) | O(N*logN) | O(N*logN) | O(1) | 不穩定 |
| 歸并排序 | O(N*logN) | O(N*logN) | O(N*logN) | O(n) | 穩定 |
| 快速排序 | O(N*logN) | O(N*logN) | O(N^2) | O(1) | 不穩定 |
| 計數排序 | O(max(N,最大值與最小值之間元素的個數)) | - | - | O(范圍) | 穩定 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303031.html
標籤：java