(一)文講到了選擇排序、插入排序和希爾排序等基本排序問題层宫。但人們并不滿足于這幾類排序杨伙，提出了一些排序算法。
一萌腿、歸并排序
歸并排序的思路如下：
- 先將一個(gè)數(shù)組分為兩個(gè)子數(shù)組限匣，
- 再對(duì)這兩個(gè)子數(shù)組分別進(jìn)行排序（可用前文將到的基本排序方法）
- 再將這兩個(gè)子數(shù)組進(jìn)行歸并。
所以毁菱，個(gè)人理解的歸并排序是指第2步的排序完成后米死，對(duì)這兩個(gè)有序的子數(shù)組進(jìn)行歸并為一個(gè)數(shù)組的方法。
1贮庞、原地歸并的抽象方法
原地歸并的抽象方法是指重新建立一個(gè)與數(shù)組大小相符的內(nèi)存空間峦筒，然后將兩個(gè)子有序數(shù)組中的元素從小到大放入這個(gè)數(shù)組當(dāng)中。
#include <iostream>
#include <vector>
using namespace std;
vector<int> SORT(int arr[], int Size);
int main()
{
int SIZE;
cout << "輸入數(shù)組大小: ";
cin >> SIZE;
int *arr = new int[SIZE];
vector<int> Result(SIZE);
for (int i = 0; i < SIZE; i++)
{
cin >> arr[i];
}
cout << "數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
Result = SORT(arr, SIZE);
cout << "排序后數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << Result[j] << " ";
}
cout << endl;
delete[] arr;
system("pause");
return 0;
}
vector<int> SORT(int arr[], int Size)
{
vector<int> result(Size);
int mid = Size / 2;
int i = 0;
int j = mid;
vector<int> temp(Size);
for (int k = 0; k < Size; k++)
{
if (i >= mid)
{
temp[k] = arr[j];
j++;
}
else if (j >= Size)
{
temp[k] = arr[i];
i++;
}
else if (arr[i] > arr[j])
{
temp[k] = arr[j];
j++;
}
else
{
temp[k] = arr[i];
i++;
}
}
for (int i = 0; i < Size; i++)
{
result[i] = temp[i];
}
return result;
}
2窗慎、自頂向下的歸并排序
當(dāng)然物喷， 如果將前面的原地歸并的方法卤材，加上遞歸的思想后，就可以用于各種數(shù)組的排序中了峦失。遞歸的思想在歸并排序中顯得十分重要扇丛。
基本的思路如下：
- 需要寫出原地歸并的抽象方法merge()，
- 再通過遞歸的思想尉辑，寫出SORT()函數(shù)帆精。
#include <iostream>
#include <vector>
const int SIZE = 16;
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
int main()
{
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++)
{
cin >> arr[i];
}
cout << "數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
SORT(arr, 0, SIZE-1);
// merge(arr, 2, 2, 3);
cout << "排序后數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
delete[] arr;
system("pause");
return 0;
}
void SORT(int *arr, int begin, int end)
{
if (begin >= end)
return;
int middle = begin + (end - begin) / 2;
SORT(arr, begin, middle); // 遞歸的思想
SORT(arr, middle+1, end); // 遞歸的思想
merge(arr, begin, middle, end);
}
void merge(int arr[], int begin, int middle, int end) // 原地歸并抽象方法
{
int i = begin;
int j = middle+1;
vector<int> temp(SIZE);
for (int m = begin; m <= end; m++)
temp[m] = arr[m];
for (int k = begin; k <= end; k++)
{
if (i > middle)
{
arr[k] = temp[j];
j++;
}
else if (j > end)
{
arr[k] = temp[i];
i++;
}
else if (temp[i] > temp[j])
{
arr[k] = temp[j];
j++;
}
else
{
arr[k] = temp[i];
i++;
}
}
}
歸并排序可用于處理數(shù)百萬甚至更大規(guī)模的數(shù)組。
分析：由上述所說隧魄，歸并排序使用的是遞歸的思想進(jìn)行排序卓练。如果在小規(guī)模的數(shù)組中頻繁使用歸并排序，將會(huì)影響算法的性能堤器。所以昆庇，我們可以在對(duì)小規(guī)模數(shù)組進(jìn)行簡(jiǎn)單的基礎(chǔ)排序，如插入排序闸溃，就可以降低算法的運(yùn)行時(shí)間整吆。插入排序?qū)σ恍┍容^小型的數(shù)組，有較好的排序效果辉川，這體現(xiàn)在排序時(shí)間上表蝙。
據(jù)書上所說，使用插入排序處理小規(guī)模的子數(shù)組(比如長(zhǎng)度小于15)一般可以將歸并排序的運(yùn)行時(shí)間縮短10%~15%
如何來讓子數(shù)組自動(dòng)地在我們規(guī)定的長(zhǎng)度上進(jìn)行插入排序呢乓旗？其實(shí)一開始我也沒有想明白這個(gè)問題府蛇。但后來書上一詞提醒了我——“改進(jìn)”。所以屿愚，我們需要在前面的遞歸歸并排序的基礎(chǔ)上汇跨，改進(jìn)算法，縮短歸并排序的時(shí)間妆距。
首先穷遂，我想到的第一個(gè)想法就是減少遞歸的次數(shù)。減少遞歸次數(shù)娱据，就需要在一下代碼段中修改蚪黑，修改跳出遞歸函數(shù)的條件！
void SORT(int *arr, int begin, int end)
{
if (begin >= end) //需修改遞歸結(jié)束的條件中剩，以盡早結(jié)束遞歸
return;
int middle = begin + (end - begin) / 2;
SORT(arr, begin, middle);
SORT(arr, middle+1, end);
merge(arr, begin, middle, end);
}
因此忌穿，可以將子數(shù)組的長(zhǎng)度設(shè)定為4，之前的(begin>=end)條件可以改寫為((end-begin) > 4-1)结啼，再在條件判斷體中加入插入排序算法掠剑，即可完成改進(jìn)。
#include <iostream>
#include <vector>
const int SIZE = 16;
const int SpiltSize = 4; //子數(shù)組的長(zhǎng)度
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
void InsertSort(int *arr, int begin, int end);
int main()
{
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++)
{
cin >> arr[i];
}
cout << "數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
SORT(arr, 0, SIZE-1);
cout << "排序后數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
delete[] arr;
system("pause");
return 0;
}
void SORT(int *arr, int begin, int end)
{
if (end - begin > (SIZE / SpiltSize) - 1)
{
InsertSort(arr, begin, end);
return;
}
int middle = begin + (end - begin) / 2;
SORT(arr, begin, middle);
SORT(arr, middle+1, end);
merge(arr, begin, middle, end);
}
void merge(int arr[], int begin, int middle, int end)
{
int i = begin;
int j = middle+1;
vector<int> temp(SIZE);
for (int m = begin; m <= end; m++)
temp[m] = arr[m];
for (int k = begin; k <= end; k++)
{
if (i > middle)
{
arr[k] = temp[j];
j++;
}
else if (j > end)
{
arr[k] = temp[i];
i++;
}
else if (temp[i] > temp[j])
{
arr[k] = temp[j];
j++;
}
else
{
arr[k] = temp[i];
i++;
}
}
}
void InsertSort(int *arr, int begin, int end)
{
int Length = (end - begin) + 1;
int temp;
for (int i = 0; i < Length; i++)
{
for (int j = i; j > 0; j--)
{
if (arr[j - 1] > arr[j])
{
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
else
{
continue;
}
}
}
}
3郊愧、自底向上的歸并排序
自底向上的歸并排序思路與自頂向上相反澡腾，即先從大小為2的兩個(gè)子數(shù)組進(jìn)行二二歸并沸伏，再?gòu)拇笮?的兩個(gè)子數(shù)組進(jìn)行四四歸并，以此類推动分。自底向上的代碼量明顯減少，而且無需用到自頂向上的遞歸红选，僅有一個(gè)循環(huán)嵌套即可完成排序澜公。
#include <iostream>
#include <vector>
const int SIZE = 20;
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
int min(int a, int b);
int main()
{
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++)
{
cin >> arr[i];
}
cout << "數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
// InsertSort(arr,0,SIZE-1);
SORT(arr, 0, SIZE-1);
// merge(arr, 0, 0, 1);
cout << "排序后數(shù)組為：";
for (int j = 0; j < SIZE; j++)
{
cout << arr[j] << " ";
}
cout << endl;
delete[] arr;
system("pause");
return 0;
}
void SORT(int *arr, int begin, int end)
{
for (int Rate = 1; Rate < SIZE; Rate += Rate)
{
for (int lo = 0; lo < SIZE - Rate; lo += 2 * Rate)
{
merge(arr, lo, lo + Rate - 1, min(SIZE - 1, lo + 2 * Rate - 1));
}
}
}
void merge(int arr[], int begin, int middle, int end)
{
int i = begin;
int j = middle+1;
vector<int> temp(SIZE);
for (int m = begin; m <= end; m++)
temp[m] = arr[m];
for (int k = begin; k <= end; k++)
{
if (i > middle)
{
arr[k] = temp[j];
j++;
}
else if (j > end)
{
arr[k] = temp[i];
i++;
}
else if (temp[i] > temp[j])
{
arr[k] = temp[j];
j++;
}
else
{
arr[k] = temp[i];
i++;
}
}
}
void InsertSort(int *arr, int begin, int end)
{
int Length = (end - begin) + 1;
int temp;
for (int i = 0; i < Length; i++)
{
for (int j = i; j > 0; j--)
{
if (arr[j - 1] > arr[j])
{
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
else
{
continue;
}
}
}
}
int min(int a, int b)
{
return a > b ? b : a;
}
自底向上的歸并排序比較適合用鏈表組織的數(shù)組。這種方法只需要重新組織鏈表鏈接就能將鏈表原地排序喇肋，并且它無需創(chuàng)建任何新的鏈表節(jié)點(diǎn)坟乾。
這些算法還能在一些小問題上進(jìn)行優(yōu)化。例如蝶防，對(duì)已經(jīng)排序的兩個(gè)子數(shù)組進(jìn)行歸并時(shí)甚侣，可以判斷第一個(gè)子數(shù)組的末位數(shù)A1[end]與第二個(gè)子數(shù)組的首位A2[0]的大小關(guān)系，若A1[end]小于A2[0]间学，則兩子數(shù)組合成的數(shù)組已經(jīng)為有序數(shù)組了殷费，無需再進(jìn)行歸并排序，這樣就可以進(jìn)一步節(jié)省排序的時(shí)間低葫。
