目錄
?一、冒泡排序
1、冒泡排序思想
2、冒泡排序算法的性能分析
二、選擇排序
1、選擇排序思想
2、選擇排序算法的性能分析?
?三、直接插入排序
1、直接插入排序思想
2、直接插入排序算法的性能分析
四、希爾排序
1、希爾排序思想
2、希爾排序算法的性能分析
五、堆排序
六、快速排序
1、hoare劃分法
2、挖坑法?
3、前后指針法?
快速排序優(yōu)化?
快速排序的非遞歸實現(xiàn)?
七、歸并排序
1、歸并排序遞歸實現(xiàn)
2、歸并排序非遞歸實現(xiàn)?
一、冒泡排序
1、冒泡排序思想
冒泡排序的基本思想是通過相鄰元素之間的比較和交換來逐步將最大（或最小）的元素移到右邊（或左邊）。具體來說，冒泡排序的步驟如下：
- 從數(shù)組的第一個元素開始，依次比較相鄰的兩個元素。如果前面的元素大于后面的元素，則交換它們的位置，以使較大的元素向右移動。
- 繼續(xù)向數(shù)組的下一個相鄰元素進行比較和交換，直到最后一個元素，此時最大的元素已經(jīng)移到了數(shù)組的最右側(cè)。
- 重復(fù)以上步驟，但這次只需要比較和交換前 n-1 個元素，因為最大的元素已經(jīng)在正確的位置上。
- 重復(fù)進行 n-1 輪比較和交換，直到所有元素都按照從小到大（或從大到小）的順序排列。
2、冒泡排序算法的性能分析
- 最好的情況下，當(dāng)輸入數(shù)組已經(jīng)是有序的，冒泡排序只需進行一輪比較，時間復(fù)雜度為 O(n)。
- 最壞的情況下，當(dāng)輸入數(shù)組是逆序的，冒泡排序需要進行 n-1 輪比較和交換，時間復(fù)雜度為 O(n^2)。
- 平均情況下，冒泡排序的時間復(fù)雜度為 O(n^2)。
- 冒泡排序是一種穩(wěn)定排序算法，不會改變相等元素的相對順序。
- 冒泡排序是一種原地排序算法，不需要額外的空間。
1、普通版本：
// 定義一個交換函數(shù)，用于交換兩個整數(shù)的值
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// 冒泡排序函數(shù)，對數(shù)組進行排序
void BubbleSort(int* a, int n)
{
int i, j;
// 外層循環(huán)控制排序的輪數(shù)
for (i = 0; i < n - 1; i++)
{
// 內(nèi)層循環(huán)進行相鄰元素的比較和交換
for (j = 0; j < n - i - 1; j++)
{
// 如果前一個元素大于后一個元素，則交換它們的位置
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
}
}
}
}2、優(yōu)化版本 ：
思想：在優(yōu)化版本的冒泡排序算法中，通過添加一個標(biāo)記變量flag，可以在一輪排序過程中標(biāo)記是否有進行過交換操作，如果某一輪排序中沒有進行過任何交換，說明數(shù)組已經(jīng)有序，可以提前結(jié)束排序。
// 定義一個交換函數(shù)，用于交換兩個整數(shù)的值
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// 冒泡排序函數(shù)，對數(shù)組進行排序
void BubbleSortPro(int* a, int n)
{
int i, j, flag = 0;
// flag用于標(biāo)記是否有交換發(fā)生，初始值為0
// 外層循環(huán)控制排序的輪數(shù)
for (i = 0; i < n - 1; i++)
{
flag = 0; // 在每一輪開始時，將flag重置為0
// 內(nèi)層循環(huán)進行相鄰元素的比較和交換
for (j = 0; j < n - i - 1; j++)
{
// 如果前一個元素大于后一個元素，則交換它們的位置，并將flag設(shè)置為1
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = 1;
}
}
// 如果在一輪排序中沒有進行過任何交換，說明數(shù)組已經(jīng)有序，可以提前結(jié)束排序
if (flag == 0)
{
break;
}
}
}二、選擇排序
1、選擇排序思想
選擇排序的基本思想可以概括為以下幾個步驟：
- 遍歷待排序的數(shù)組，將數(shù)組中的第一個元素視為當(dāng)前最小值。
- 在剩余的未排序部分中，依次查找比當(dāng)前最小值更小的元素。
- 如果找到了比當(dāng)前最小值更小的元素，則將其標(biāo)記為新的最小值。
- 遍歷完未排序部分，將新的最小值與當(dāng)前最小值交換位置。
- 如此循環(huán)，直到所有元素都被排序。
通過每次從剩余未排序部分選擇最小的元素，并將其放在已排序部分的末尾，逐步構(gòu)建有序序列。
2、選擇排序算法的性能分析?
- 選擇排序的時間復(fù)雜度為O(n^2)，其中n是待排序數(shù)組的元素個數(shù)。這是因為在每一輪遍歷中，需要比較剩余未排序部分的所有元素，最壞情況下要進行n-1次比較。總共需要進行n-1輪遍歷，因此時間復(fù)雜度為O(n^2)。
- 選擇排序是一種不穩(wěn)定的排序算法。當(dāng)待排序數(shù)組中存在相同元素時，選擇排序可能會改變相同元素的相對順序。具體來說，在選擇過程中，如果當(dāng)前的最小元素與其他相同元素交換位置，可能會改變它們的相對順序。
- 選擇排序是一種原地排序算法，即排序過程中不需要額外的空間。它只需要一個額外的變量來記錄最?。ɑ蜃畲螅┰氐奈恢?，通過交換元素位置來實現(xiàn)排序，所以空間復(fù)雜度為O(1)。
綜上所述，選擇排序的時間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(1)，并且是一種不穩(wěn)定的排序算法。
?
1、普通版本：
void swap(int* a,int* b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void SelctSort(int* a, int n)
{
int i, j, key;
// 遍歷數(shù)組，i表示已排序部分的末尾元素的索引
for (i = 0; i < n - 1; i++)
{
key = i; // 將當(dāng)前位置視為最小值的索引
// 在未排序部分中查找最小值
for (j = i + 1; j < n; j++)
{
if (a[key] > a[j])
{
key = j; // 更新最小值的索引
}
}
// 如果最小值不是當(dāng)前位置的元素，則交換位置
if (key != i)
{
swap(&a[i], &a[key]);
}
}
}?2、優(yōu)化版本
?優(yōu)化版本的思想是在選擇排序的基礎(chǔ)上，同時追蹤并找出未排序部分的最大值和最小值，并將它們分別放置在已排序部分的末尾和開頭。通過這種方式，可以減少交換的次數(shù)，從而提高排序的效率。
void swap(int* a,int* b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void SelctSortPro(int* a, int n)
{
int i, j;
int begin = 0, end = n - 1;
int maxi = end, mini = begin;
// 在每一次循環(huán)中，將未排序部分的最大值和最小值分別放置在已排序部分的末尾和開頭
while (begin < end)
{
i = begin;
j = end;
maxi = end;
mini = begin;
// 在未排序部分中查找最大值和最小值
while (i <= end)
{
if (a[maxi] < a[i])
{
maxi = i; // 更新最大值的索引
}
if (a[mini] > a[i])
{
mini = i; // 更新最小值的索引
}
i++;
}
// 將最小值放置在已排序部分的開頭
swap(&a[begin], &a[mini]);
// 如果最大值所在位置等于begin，更新最大值所在位置為mini
if (maxi == begin)
{
maxi = mini;
}
// 將最大值放置在已排序部分的末尾
swap(&a[end], &a[maxi]);
// 更新已排序部分和未排序部分的起始和結(jié)束位置
begin++;
end--;
}
}?三、直接插入排序
1、直接插入排序思想
直接插入排序是一種簡單直觀的排序算法，其思想是通過構(gòu)建已排序部分和未排序部分，將待排序元素按照大小逐個插入到已排序部分的正確位置中，完成排序。
具體步驟如下：
- 將待排序序列的第一個元素看作已排序部分。
- 從待排序序列中依次取出元素，從已排序部分的末尾開始，向前比較。
- 如果當(dāng)前取出的元素大于已排序部分的某個元素，則將該元素插入到該位置后面，即將該位置以及其后面的元素都向后移動一位。
- 如果當(dāng)前取出的元素小于或等于已排序部分的某個元素，則將該元素插入到該位置前面的位置。
- 重復(fù)步驟2-4，直到待排序部分中的所有元素都被插入到已排序部分中
2、直接插入排序算法的性能分析
時空復(fù)雜度:
- 時間復(fù)雜度：直接插入排序的平均時間復(fù)雜度為O(n^2)，最好情況下的時間復(fù)雜度為O(n)，最壞情況下的時間復(fù)雜度為O(n^2)。
- 空間復(fù)雜度：直接插入排序的空間復(fù)雜度為O(1)，它是一種原地排序算法，不需要額外的空間。
穩(wěn)定性：
直接插入排序是穩(wěn)定的，即相等元素的相對次序在排序前后保持不變。當(dāng)比較相等元素時，由于只有當(dāng)前元素小于等于已排序部分的某個元素時才插入，因此相等元素的相對次序不會發(fā)生改變。
需要注意的是，盡管直接插入排序在最壞情況下的時間復(fù)雜度較高，但對于小規(guī)?；蚧居行虻男蛄?，直接插入排序的性能較為優(yōu)秀。
void InsertSort(int* a, int n)
{
int i, j, temp;
for (i = 0; i < n - 1; i++)
{
temp = a[i + 1]; // 將當(dāng)前待插入的元素暫存到變量temp中
j = i; // j用于記錄已排序部分的最后一個元素的索引
while (j >= 0)
{
if (temp < a[j])
{
a[j + 1] = a[j]; // 如果temp比已排序部分的元素小，將該元素后移一位
}
else
{
break; // 如果temp不小于已排序部分的元素，跳出循環(huán)
}
j--; // 繼續(xù)向前比較
}
a[j + 1] = temp; // 將暫存的元素插入到正確位置
}
}四、希爾排序
1、希爾排序思想
希爾排序是基于插入排序的一種改進算法，也稱為縮小增量排序。它通過將待排序序列按照一定間隔分成多個子序列，并對每個子序列進行插入排序的方式來逐步減小間隔，最終使整個序列有序。
具體步驟如下：
- 選擇一個增量序列，通常是除以2逐步縮小得到的序列。
- 根據(jù)增量序列將待排序序列分成多個子序列。
- 對每個子序列進行插入排序，即將子序列中的元素按照插入排序的方式進行排序。
- 逐步縮小增量，重復(fù)步驟2和步驟3，直到增量為1。
- 最后進行一次增量為1的插入排序，完成整個序列的排序。
希爾排序的思想是利用了插入排序?qū)居行虻男蛄行阅茌^好的特點，通過提前部分排序減少了逆序?qū)Φ臄?shù)量，從而提高了排序效率。
2、希爾排序算法的性能分析
時空復(fù)雜度:
- 時間復(fù)雜度：希爾排序的時間復(fù)雜度與增量序列的選擇有關(guān)，平均時間復(fù)雜度為O(nlogn)，最好情況下的時間復(fù)雜度為O(nlog^2n)，最壞情況下的時間復(fù)雜度為O(n^2)。
- 空間復(fù)雜度：希爾排序的空間復(fù)雜度為O(1)，它是一種原地排序算法，不需要額外的空間。
穩(wěn)定性：
希爾排序是不穩(wěn)定的，因為在每個子序列中進行插入排序時，相等元素的相對次序可能會發(fā)生改變。
void ShellSort(int* a, int n)
{
int gap = n; // 設(shè)置初始的增量gap為序列長度
int temp, i, j;
while (gap > 1)
{
gap = gap / 2; // 縮小增量
for (i = 0; i < n - gap; i++)
{
temp = a[i + gap]; // 將當(dāng)前待插入的元素暫存到變量temp中
j = i;
while (j >= 0)
{
if (temp < a[j])
{
a[j + gap] = a[j]; // 如果temp比已排序部分的元素小，將該元素后移gap位
j -= gap; // 向前移動gap位
}
else
{
break; // 如果temp不小于已排序部分的元素，跳出循環(huán)
}
}
a[j + gap] = temp; // 將暫存的元素插入到正確位置
}
}
}五、堆排序
堆排序是一種基于二叉堆（heap）數(shù)據(jù)結(jié)構(gòu)的排序算法。它的思想可以概括為以下幾個步驟：
-
構(gòu)建堆：將待排序的數(shù)組視為一個完全二叉樹，并將其轉(zhuǎn)化為一個堆。這可通過從最后一個非葉子節(jié)點開始，逐個向上調(diào)整每個節(jié)點來完成。調(diào)整操作會使得當(dāng)前節(jié)點和其子樹滿足堆的性質(zhì)，即父節(jié)點的值大于等于（或小于等于）其子節(jié)點的值。這樣就構(gòu)建了一個最大堆（或最小堆）。
-
排序：經(jīng)過構(gòu)建堆操作后，堆頂元素是最大（或最?。┑脑?。我們可以將堆頂元素與堆中最后一個元素交換位置，然后將堆的大小減小 1。這樣，最大（或最小）的元素會被放置到正確的位置（即最后一個位置）。接著，我們對堆頂元素進行向下調(diào)整，使得堆再次滿足堆的性質(zhì)。重復(fù)以上步驟，直到堆中只剩下一個元素。
-
返回有序序列：當(dāng)堆中只剩下一個元素時，所有的元素都已經(jīng)交換并放置到了正確的位置。此時，我們就得到了一個有序的序列。
堆排序的時間復(fù)雜度為 O(nlogn)，其中 n 是數(shù)組的大小。它是一種原址排序算法，因為它只需要用到原始數(shù)組，不需要使用額外的空間。同時，堆排序也是一種穩(wěn)定的排序算法。
代碼及注釋：?
void AdjustDown(int* a, int parent, int n)
{
// 計算左子節(jié)點的索引
int child = parent * 2 + 1;
// 當(dāng)左子節(jié)點在數(shù)組范圍內(nèi)時進行循環(huán)
while (child < n)
{
// 如果右子節(jié)點存在且比左子節(jié)點大，則選擇右子節(jié)點作為與父節(jié)點進行比較的子節(jié)點
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
// 如果父節(jié)點小于子節(jié)點，則交換它們的值
if (a[parent] < a[child])
{
swap(&a[parent], &a[child]);
// 更新父節(jié)點和子節(jié)點的索引
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 從最后一個非葉子節(jié)點開始，依次調(diào)用 AdjustDown 函數(shù)，構(gòu)建最大堆
int i = 0;
int end = n / 2 - 1;
for (i = end; i >= 0; i--)
{
AdjustDown(a, i, n);
}
// 交換堆頂元素與最后一個元素，并向下調(diào)整堆
for (i = 0; i < n; i++)
{
swap(&a[0], &a[n - i - 1]);
AdjustDown(a, 0, n - i - 1);
}
}六、快速排序
快速排序使用分治的思想來進行排序，其基本過程如下：
- 從待排序數(shù)組中選擇一個元素作為樞軸（pivot）。
- 將數(shù)組分割成兩個子數(shù)組，使得左側(cè)子數(shù)組的元素都小于等于樞軸，右側(cè)子數(shù)組的元素都大于等于樞軸。這個分割的過程稱為劃分（partition）。
- 對左右子數(shù)組分別遞歸地進行快速排序。
- 遞歸結(jié)束的條件是子數(shù)組只有一個元素或者為空。
時空復(fù)雜度：?
- 平均時間復(fù)雜度：O(nlogn)
- 當(dāng)數(shù)組有序時，最壞時間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(logn)
1、hoare劃分法
void QuickSortHoare(int* a, int begin, int end)
{
// begin為首元素下標(biāo)，end為尾元素下標(biāo)
if (begin >= end)
{
return; // 遞歸結(jié)束條件：子數(shù)組只有一個元素或為空，不需要排序
}
int left = begin; // 左指針
int right = end; // 右指針
int key = begin; // 選擇第一個元素作為基準(zhǔn)元素
while (left < right)
{
// 從右側(cè)開始，找到第一個比基準(zhǔn)元素小的元素
while (a[right] >= a[key] && right > left)
{
right--;
}
// 從左側(cè)開始，找到第一個比基準(zhǔn)元素大的元素
while (a[left] <= a[key] && right > left)
{
left++;
}
// 如果左指針小于右指針，交換左右指針對應(yīng)的元素
if (left < right)
{
swap(&a[left], &a[right]);
}
}
// 將基準(zhǔn)元素放到正確的位置上
swap(&a[key], &a[left]);
// 對基準(zhǔn)元素左側(cè)和右側(cè)的子數(shù)組進行遞歸調(diào)用
QuickSortHoare(a, begin, left - 1);
QuickSortHoare(a, left + 1, end);
}
2、挖坑法
挖坑法是一種簡潔的快速排序?qū)崿F(xiàn)方式，它通過交替移動兩個指針，將元素一個個填入坑位的方式來進行劃分。與Hoare劃分法相比，挖坑法在劃分的過程中不需要頻繁地交換元素，因此實現(xiàn)上會更為簡單。
?
void QuickSortLomuto(int* a, int begin, int end)
{
if (begin >= end)
{
return; // 遞歸結(jié)束條件：子數(shù)組只有一個元素或為空，不需要排序
}
int curi = begin; // 當(dāng)前坑位的索引
int temp = a[begin]; // 樞軸元素的值
int left = begin; // 左指針
int right = end; // 右指針
while (left < right)
{
// 從右側(cè)開始，找到第一個比樞軸小的元素的索引
while (a[right] >= temp && left < right)
{
right--;
}
a[curi] = a[right]; // 將右指針指向的元素填入當(dāng)前坑位
curi = right; // 更新當(dāng)前坑位的索引
// 從左側(cè)開始，找到第一個比樞軸大的元素的索引
while (a[left] <= temp && left < right)
{
left++;
}
a[curi] = a[left]; // 將左指針指向的元素填入當(dāng)前坑位
curi = left; // 更新當(dāng)前坑位的索引
}
a[curi] = temp; // 將樞軸元素填入最后一個坑位，確保樞軸元素的位置被確定
// 對樞軸左側(cè)和右側(cè)的子數(shù)組進行遞歸調(diào)用
QuickSortLomuto(a, begin, left - 1);
QuickSortLomuto(a, left + 1, end);
}3、前后指針法?
void QuickSortPB(int* a, int begin, int end)
{
if(begin > end)
{
return; // 遞歸結(jié)束條件：子數(shù)組為空，不需要排序
}
int prev = begin; // prev指針指向樞軸元素的位置
int cur = prev + 1; // cur指針指向待比較元素的位置
int key = begin; // 樞軸元素的位置
// 遍歷數(shù)組，將小于等于樞軸元素的元素放在prev指針的后面
while(cur <= end)
{
if(a[cur] <= a[key])
{
prev++;
if(cur != prev)
{
swap(&a[prev], &a[cur]); // 交換prev指針和cur指針指向的元素
}
}
cur++;
}
swap(&a[begin], &a[prev]); // 將樞軸元素放到prev指針的位置
// 對樞軸左側(cè)和右側(cè)的子數(shù)組進行遞歸調(diào)用
QuickSortPB(a, begin, prev-1);
QuickSortPB(a, prev+1, end);
}快速排序優(yōu)化?
"三數(shù)取中"的方法是從待排序數(shù)組中隨機選擇三個元素，然后取這三個元素的中間值作為樞軸元素。具體步驟如下：
- 選擇開始位置?
begin、結(jié)束位置?end?和中間位置?mid，計算?mid = (begin + end) / 2。 - 比較?
a[begin]、a[mid]?和?a[end]?的大小，確定其中的中間值。 - 將選出的中間值與?
a[begin]?進行交換，將中間值放在數(shù)組開始的位置，作為樞軸元素。 - 進行正常的快速排序算法。
通過使用"三數(shù)取中"的方法選擇樞軸元素，可以盡量避免了最壞情況的發(fā)生。最壞的情況是樞軸元素選擇的不好，導(dǎo)致每次劃分只將數(shù)組分成一個很小的部分和一個很大的部分，使得快速排序的時間復(fù)雜度退化為O(n^2)。而"三數(shù)取中"的方法通過選擇一個近似于中位數(shù)的元素作為樞軸，能夠更平衡地劃分?jǐn)?shù)組，減少這種最壞情況的發(fā)生，從而提高快速排序的效率。
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2; // 計算中間位置
// begin midi end 三個數(shù)選中位數(shù)
if (a[begin] < a[midi]) // 如果begin位置的值小于midi位置的值
{
if (a[midi] < a[end]) // 如果midi位置的值小于end位置的值
return midi; // 返回midi位置
else if (a[begin] > a[end]) // 如果begin位置的值大于end位置的值
return begin; // 返回begin位置
else
return end; // 返回end位置
}
else
{
if (a[midi] > a[end]) // 如果midi位置的值大于end位置的值
return midi; // 返回midi位置
else if (a[begin] < a[end]) // 如果begin位置的值小于end位置的值
return begin; // 返回begin位置
else
return end; // 返回end位置
}
}
int QuickSortHoare(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end); // 找到中間位置的索引
Swap(&a[midi], &a[begin]); // 交換中間位置的值和起始位置的值
int left = begin, right = end; // 設(shè)置左右指針
int keyi = begin; // 設(shè)置基準(zhǔn)值索引
while (left < right)
{
// 右邊找小
while (left < right && a[right] >= a[keyi]) // 從右邊開始找小于基準(zhǔn)值的數(shù)
{
--right;
}
// 左邊找大
while (left < right && a[left] <= a[keyi]) // 從左邊開始找大于基準(zhǔn)值的數(shù)
{
++left;
}
Swap(&a[left], &a[right]); // 交換左右指針?biāo)肝恢玫闹? }
Swap(&a[left], &a[keyi]); // 將基準(zhǔn)值放到中間位置
return left; // 返回中間位置的索引
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return; // 如果起始位置大于等于終止位置，則返回
int keyi = QuickSortHoare(a, begin, end); // 使用快速排序的Hoare分區(qū)函數(shù)找到基準(zhǔn)值的索引
QuickSort(a, begin, keyi - 1); // 對基準(zhǔn)值左邊的數(shù)組進行快速排序
QuickSort(a, keyi+1, end); // 對基準(zhǔn)值右邊的數(shù)組進行快速排序
}快速排序的非遞歸實現(xiàn)?
快速排序的非遞歸實現(xiàn)使用了棧來模擬遞歸的過程，這樣可以避免使用系統(tǒng)棧導(dǎo)致的遞歸調(diào)用過深的問題。
非遞歸實現(xiàn)的思想如下：
-
創(chuàng)建一個棧，用于存儲待處理子數(shù)組的邊界。初始時，將整個數(shù)組的開始位置和結(jié)束位置入棧。
-
進行循環(huán)，直到棧為空。循環(huán)的目的是處理棧中的每個子數(shù)組。
-
彈出棧頂?shù)淖訑?shù)組邊界，得到開始位置和結(jié)束位置。
-
在子數(shù)組中選擇樞軸元素，并使用 Hoare 劃分方式將子數(shù)組劃分成兩個部分。將劃分點的下標(biāo)入棧，保證后續(xù)對其進行排序。
-
根據(jù)劃分點的下標(biāo)更新子數(shù)組邊界，將左側(cè)子數(shù)組的開始位置和結(jié)束位置入棧，再將右側(cè)子數(shù)組的開始位置和結(jié)束位置入棧。注意保證先處理左側(cè)子數(shù)組，再處理右側(cè)子數(shù)組。
-
重復(fù)步驟 3 到步驟 5，直到棧為空，即所有子數(shù)組都被處理完畢。
通過上述步驟，可以將遞歸的快速排序算法轉(zhuǎn)化為非遞歸的實現(xiàn)。該實現(xiàn)使用棧來保存待處理的子數(shù)組邊界，以模擬遞歸過程。每次處理子數(shù)組時，選擇一個樞軸元素進行劃分，并將劃分點的下標(biāo)入棧。然后根據(jù)劃分點將子數(shù)組分成兩部分，分別將左側(cè)和右側(cè)的子數(shù)組邊界入棧。這樣可以確保先處理左側(cè)子數(shù)組，再處理右側(cè)子數(shù)組，達到快速排序的效果。
typedef int StackDataType;
typedef struct StackNode
{
StackDataType data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
StackNode* q;
int size;
}Stack;
void StackInit(Stack* s)
{
StackNode* head=(StackNode*)malloc(sizeof(StackNode));
head->next=NULL;
s->q=head;
s->size=0;
}
void StackPush(Stack* s,StackDataType x)
{
StackNode* newnode=(StackNode*)malloc(sizeof(StackNode));
newnode->data=x;
newnode->next=s->q->next;
s->q->next=newnode;
s->size++;
}
int StackEmpty(Stack* s)
{
if(s->q->next==NULL)
{
return 1;
}
return 0;
}
StackDataType StackTop(Stack* s)
{
if(!StackEmpty(s))
{
return s->q->next->data;
}
else
{
return -1;
}
}
void StackPop(Stack* s)
{
if(!StackEmpty(s))
{
StackNode* temp=s->q->next;
s->q->next=s->q->next->next;
free(temp);
s->size--;
}
}
int get_keyi(int *a, int begin, int end)
{
int left = begin;
int right = end;
int key = begin;
while (left < right)
{
// 從右側(cè)開始，找到第一個小于 key 的元素
while (a[right] >= a[key] && left < right)
{
right--;
}
// 從左側(cè)開始，找到第一個大于 key 的元素
while (a[left] <= a[key] && left < right)
{
left++;
}
// 交換找到的兩個元素
swap(&a[right], &a[left]);
}
// 將基準(zhǔn)值放到中間位置
swap(&a[key], &a[left]);
return left; // 返回中間位置的索引
}
void QuickSortNR(int* a, int begin, int end)
{
Stack s;
StackInit(&s);
// 入棧起始和結(jié)束位置
StackPush(&s, end);
StackPush(&s, begin);
int left, mid, right;
// 當(dāng)棧不為空時，循環(huán)執(zhí)行
while (!StackEmpty(&s))
{
left = StackTop(&s);
StackPop(&s);
right = StackTop(&s);
StackPop(&s);
// 如果左邊界小于右邊界，進行劃分
if (left < right)
{
mid = get_keyi(a, left, right);
}
// 將左邊未排序的部分入棧
if (left < mid - 1)
{
StackPush(&s, mid - 1);
StackPush(&s, left);
}
// 將右邊未排序的部分入棧
if (right > mid + 1)
{
StackPush(&s, right);
StackPush(&s, mid + 1);
}
}
}七、歸并排序
1、歸并排序遞歸實現(xiàn)
歸并排序是一種經(jīng)典的排序算法，它使用了分治法的思想。下面是歸并排序的算法思想：
- 遞歸地將數(shù)組劃分成較小的子數(shù)組，直到每個子數(shù)組的長度為1或者0。
- 將相鄰的子數(shù)組合并，形成更大的已排序的數(shù)組，直到最終得到一個完全排序的數(shù)組。
歸并排序的過程可以分為三個步驟：拆分（Divide）、合并（Merge）和排序（Sort）。
- 拆分：將待排序的數(shù)組不斷地劃分為兩個子數(shù)組，直到每個子數(shù)組的長度為1或者0。
- 合并：將相鄰的子數(shù)組合并為一個較大的已排序數(shù)組，通過比較兩個子數(shù)組的首元素，按照從小到大的順序逐個將元素放入一個輔助數(shù)組。
- 排序：重復(fù)進行合并的過程，直到最終得到完全排序的數(shù)組。
歸并排序的時間復(fù)雜度為O(nlogn)，其中n是待排序數(shù)組的長度。空間復(fù)雜度為O(n)，主要是由于需要使用一個大小與原始數(shù)組相同的輔助數(shù)組來存儲合并的結(jié)果。
歸并排序是一種穩(wěn)定的排序算法，即相等元素的相對順序在排序前后保持不變。在合并的過程中，如果遇到兩個相等的元素，我們會先將來自前一個子數(shù)組的元素放入輔助數(shù)組，這樣可以確保相等元素的相對順序不會改變。
// 歸并排序具體功能實現(xiàn)函數(shù)
void MergeSortFun(int* a, int* temp, int begin, int end)
{
// 如果數(shù)組大小為1或者空，直接返回上一層
if (begin >= end)
{
return;
}
// 劃分?jǐn)?shù)組，遞歸調(diào)用 MergeSortFun 對左右子數(shù)組進行排序
int mid = (begin + end) / 2;
MergeSortFun(a, temp, begin, mid);
MergeSortFun(a, temp, mid + 1, end);
// 合并兩個有序子數(shù)組
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
// 依次比較兩個子數(shù)組的元素，將較小的元素放入輔助數(shù)組 temp 中
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
// 將剩余的元素放入輔助數(shù)組 temp 中
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
// 將輔助數(shù)組 temp 中的元素拷貝回原數(shù)組
for (i = begin; i <= end; i++)
{
a[i] = temp[i];
}
}
// 歸并排序入口函數(shù)
void MergeSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
// 創(chuàng)建大小為 n 的輔助數(shù)組 temp
int* temp = (int*)malloc(sizeof(int) * n);
// 調(diào)用 MergeSortFun 對數(shù)組 a 進行歸并排序
MergeSortFun(a, temp, begin, end);
// 釋放輔助數(shù)組 temp 的內(nèi)存空間
free(temp);
}2、歸并排序非遞歸實現(xiàn)?
歸并排序可以使用非遞歸的方式實現(xiàn)，其算法思想如下：
- 將待排序的數(shù)組劃分為多個大小為1的子數(shù)組。
- 分別對這些子數(shù)組進行兩兩合并，形成新的有序子數(shù)組。
- 不斷重復(fù)步驟2，直到得到一個有序的數(shù)組。
具體的非遞歸實現(xiàn)過程如下：
- 首先，定義一個大小為n的輔助數(shù)組temp用于存儲合并后的有序子數(shù)組。
- 設(shè)置一個變量gap初始值為1，表示每次合并的兩個子數(shù)組的大小。
- 進行多輪合并，直到gap大于等于n。
- 在每一輪合并中，將數(shù)組分為多個大小為gap的子數(shù)組，將相鄰的兩個子數(shù)組合并為一個有序子數(shù)組。合并時，使用雙指針i和j分別指向兩個子數(shù)組的起始位置，比較兩個子數(shù)組對應(yīng)位置上的元素大小，較小的元素放入temp數(shù)組中，同時移動指針，直到一個子數(shù)組遍歷完成。將未遍歷完的子數(shù)組中剩余的元素直接放入temp數(shù)組中。
- 更新gap的值為2倍，繼續(xù)下一輪合并。
- 最后一輪合并時，gap可能大于n，因此需要額外的判斷和處理。
- 將temp數(shù)組中的元素拷貝回原數(shù)組中。
通過不斷調(diào)整gap的大小，將待排序數(shù)組進行分組和合并操作，直到得到一個完全有序的數(shù)組。非遞歸實現(xiàn)的歸并排序避免了遞歸帶來的額外開銷，提高了算法的效率。、文章來源：http://www.zghlxwxcb.cn/news/detail-829485.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-829485.html
void mergesortnr(int* a, int* temp, int begin, int mid, int end)
{
// 定義指針和索引
int head1 = begin;
int tail1 = mid;
int head2 = mid + 1;
int tail2 = end;
int i = begin;
// 合并兩個有序子數(shù)組
// [head1,tail1] 和 [head2,tail2] 歸并
while (head1 <= tail1 && head2 <= tail2)
{
// 比較兩個子數(shù)組對應(yīng)位置上的元素大小，較小的元素放入temp數(shù)組中
if (a[head1] < a[head2])
{
temp[i++] = a[head1++];
}
else
{
temp[i++] = a[head2++];
}
}
// 將第一個子數(shù)組中剩余的元素放入temp數(shù)組中
while (head1 <= tail1)
{
temp[i++] = a[head1++];
}
// 將第二個子數(shù)組中剩余的元素放入temp數(shù)組中
while (head2 <= tail2)
{
temp[i++] = a[head2++];
}
// 將temp數(shù)組中的元素拷貝回原數(shù)組中
memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSortNR(int *a, int n)
{
// 創(chuàng)建輔助數(shù)組
int* temp = (int*)malloc(sizeof(int) * n);
int gap = 1;
// 不斷調(diào)整gap的大小，分組合并
for (gap = 1; gap < n; gap *= 2)
{
// 對每一組進行合并
for (int i = 0; i < n - gap; i += 2 * gap)
{
// 計算子數(shù)組的起始索引、中間索引和結(jié)束索引
int begin = i;、
/*如果i + 2 * gap - 1大于等于數(shù)組長度n，說明當(dāng)前的子數(shù)組已經(jīng)超出了數(shù)組的范圍，此時將結(jié)束索引end賦值為n - 1，即最后一個元素的索引。
如果i + 2 * gap - 1小于數(shù)組長度n，說明當(dāng)前的子數(shù)組還在數(shù)組的范圍內(nèi)，此時將結(jié)束索引end賦值為i + 2 * gap - 1。*/
int end = i + 2 * gap - 1 >= n ? n - 1 : i + 2 * gap - 1;
int mid = i + gap - 1;
// 調(diào)用mergesortnr函數(shù)合并子數(shù)組
mergesortnr(a, temp, begin, mid, end);
}
}
}到了這里，關(guān)于排序算法大全：冒泡排序【含優(yōu)化】，選擇排序【含優(yōu)化】，直接插入排序，希爾排序，堆排序，快速排序【含3種實現(xiàn)版本及非遞歸實現(xiàn)】，歸并排序【含非遞歸實現(xiàn)】。詳細圖解，文字解釋，代碼實現(xiàn)，性能分析。的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
