排序算法的性能比较
寫在前面
菜雞博主最近放寒假了，打算接下來的一段時間內(nèi)回顧一下以前學(xué)過的一些知識，也是為考研做一些準(zhǔn)備吧。很菜，勿噴，希望能和大家一起學(xué)習(xí)，共同進(jìn)步！
主要目標(biāo)和具體要求
目標(biāo)
排序?qū)τ跀?shù)據(jù)處理是一項十分重要和基礎(chǔ)的工作。采用如下算法實現(xiàn)排序功能：插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等。統(tǒng)計每種排序算法的性能（以相同計算機(jī)運行程序所花費的時間為準(zhǔn)進(jìn)行對比），并將數(shù)據(jù)序列和不同算法的運行時間記錄到txt文件中。
要求
設(shè)計排序系統(tǒng)，能夠?qū)崿F(xiàn)以下功能：
(1) 利用隨機(jī)函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（50000以上）；
(2) 對這些數(shù)字進(jìn)行排序，包括遞增和遞減兩種形式；
(3) 分別采用插入、折半插入、2-路插入、希爾、冒泡、快速、選擇、錦標(biāo)賽、堆、歸并、基數(shù)等排序算法解決問題；
(4) 對不同的排序算法進(jìn)行性能比較并記錄結(jié)果。
環(huán)境
操作系統(tǒng)：Windows 11
編譯器：visual studio 2022
使用的頭文件：iostream, algorithm, ctime, cstdlib, cstring, fsteam
一些設(shè)計
1.Random函數(shù)
作用：生成范圍在l-r內(nèi)的隨機(jī)數(shù)。
首先通過srand(time(0))設(shè)置時間種子，然后通過循環(huán)和語句rand()%(r-l+1)+1生成隨機(jī)數(shù)，隨機(jī)數(shù)的范圍為1-32767。
2.save函數(shù)
作用：文件操作
首先定義flag標(biāo)記換行，然后打開文件，如果不存在文件則新建，通過time()記錄所用的時間，通過for循環(huán)輸出排序結(jié)果（其中flag換行是通過每記錄一個數(shù)據(jù)使flag自加，當(dāng)flag==100時使用endl語句換行，同時重置flag=0），在輸出完所有內(nèi)容后關(guān)閉文件。
3.直接插入排序
將第一個元素看作是一個有序序列，后面n-1個元素看作無序序列，對后面未排序序列中第一個元素在這個有序序列中進(jìn)行從后向前的掃描，找到合適的位置進(jìn)行插入，將有序序列長度+1。循環(huán)操作，知道未排序序列長度為0。當(dāng)前插入元素與有序序列中元素相等時，插入到相等元素后。
4.折半插入排序
運用二分查找，定義temp來記錄當(dāng)前待插元素在有序序列中的合適位置，對temp進(jìn)行后移，在temp位置插入待插元素。
5.2-路插入排序
2-路插入排序是對插入排序的改進(jìn)，通過在首尾同時進(jìn)行插入，使用臨時數(shù)組tmp，定義front和rear記錄tmp數(shù)組中當(dāng)前的最大值和最小值位置。如果當(dāng)前插入元素比最小的要小，更新最小值位置，并且將最小值重新賦值；如果當(dāng)前插入元素比最大的要大，更新最大值位置，并且將最大值重新賦值；如果在最大和最小之間，將比當(dāng)前插入值大的進(jìn)行后移，然后插入，同時更新最大值位置，最后將臨時數(shù)組復(fù)制到原數(shù)組中。
6.希爾排序
選擇一個增量序列\(t_1t_2 \dots t_k\)，其中\(t_i > t_j, t_k =1\)；按照增量序列個數(shù)k對序列進(jìn)行k趟排序；每趟排序根據(jù)對應(yīng)的增量，將待排序列分割成若干長度為m的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1時，整個序列作為一個表來處理，表長度即整個序列的長度。
7.快速排序
先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)；分區(qū)過程：將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊；對左右兩個區(qū)間重復(fù)第二步直到各區(qū)間只有一個數(shù)。本算法使用三數(shù)取中的方法取基準(zhǔn)值：取序列中最左邊、中間、最右邊的三個數(shù)進(jìn)行比較，以這三個數(shù)大小為中的元素作為基準(zhǔn)值。
8.選擇排序
將比當(dāng)前未排序序列的首位元素較小的數(shù)據(jù)元素交換到首位，最后每一趟比較都會將當(dāng)前最小的元素交換到為排序序列的首位。改進(jìn)后，通過定義min來確定未排序序列中的最小元素位置。
9.錦標(biāo)賽排序
樹形選擇排序，由于其特殊性質(zhì)，錦標(biāo)賽排序構(gòu)成的圖結(jié)構(gòu)是滿二叉樹。定義一個tree[]數(shù)組來儲存滿二叉樹，錄入葉子節(jié)點（需要排序的所有元素），因為二叉樹某結(jié)點的下標(biāo)為i，它的左右孩子節(jié)點下標(biāo)必為2i+1和2i+2，因此比較葉子節(jié)點的值，可以得到父節(jié)點的值（兩個葉子節(jié)點的值較小的那個），每次得到當(dāng)前最小值的時候，通過minindex在tree[]中找到最小值的地址，將其設(shè)為MAX。
10.堆排序
使用大根堆對數(shù)組進(jìn)行正向排序。
首先將當(dāng)前的無序數(shù)組構(gòu)成一個無序堆，某結(jié)點的下標(biāo)為i，它的左右孩子節(jié)點下標(biāo)必為2i+1和2i+2，然后將當(dāng)前的無序堆進(jìn)行調(diào)整至大根堆形成。接著交換首位元素（將當(dāng)前堆頂?shù)淖畲笤亟粨Q到末尾，將此元素歸位。因為交換完首位元素后堆會再次變成一個無序堆，需要對剩余元素進(jìn)行調(diào)整至重新變成大根堆。）重復(fù)操作至堆的大小為1完成堆排序。
11.歸并排序
將長度為n的序列分解成兩個長度為n/2的子序列，遞歸排序兩個連續(xù)子序列，合并兩個已經(jīng)排序的連續(xù)子序列構(gòu)成一個完整排序的序列。
12.基數(shù)排序
定義一個count[]數(shù)組（大小為10，下標(biāo)0-9）用于統(tǒng)計每一位數(shù)字出現(xiàn)的次數(shù)，一個大小為n的臨時數(shù)組tmp[]用于儲存按照當(dāng)前以為數(shù)字排序后的序列。進(jìn)行d次排序，每次分配前先清空計數(shù)器，從低位開始，統(tǒng)計每一位數(shù)字出現(xiàn)的個數(shù)記錄到count[]中，由遞推式\(start[i]=start[i-1]+count[i-1]\)得到每一位數(shù)字第一次出現(xiàn)的位置。然后將每個元素按照當(dāng)前的這一位數(shù)字放入對應(yīng)的0-9的桶中，每一次將所有元素放入對應(yīng)桶中后，根據(jù)start[]將其放到臨時數(shù)組tmp[]，再將其拷貝到原數(shù)組中。重復(fù)上述步驟，當(dāng)按照最高位放入桶中的操作完成后，再放回原數(shù)組。
13.計時
使用clock_t庫，定義start和end，將不同的排序算法寫在start和end之間，定義duration=(double)(end-start)/CLOCKS_PER_SEC來輸出需要的時間并打印。
源代碼
#include<iostream>
#include<algorithm>
#include<ctime>
#include<time.h>
#include<cstdlib>
#include<cstring>
#include<fstream>
using namespace std;
#define random(x) rand() % (x)
void save(int a[], string str, double time)
{
int flag = 0;//標(biāo)記換行
fstream f;
f.open("data.txt", ios::out | ios::app);
f << str << "所用的時間:" << time << "s" << endl;
for (int i = 0; i < 50000; i++)
{
flag++;
f << a[i] << "-";
if (flag == 100)
{
f << endl;
flag = 0;
}
}
f << endl << endl;
f.close();
}
//生成范圍在l~r的隨機(jī)數(shù)
void Random(int* a, int n, int l, int r)
{
srand(time(0));//設(shè)置時間種子
for (int i = 0; i < n; i++)
{
a[i] = rand() % (r - l + 1) + 1;//生成隨機(jī)數(shù)
}
}
//打印（測試用）
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
//直接插入排序（正向）
void InsertSort_up(int a[], int n)
{
int temp, i, j;
for (i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
temp = a[i];
a[i] = a[i - 1];
for (j = i - 2; j >= 0 && a[j] > temp; --j)
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
}
//直接插入排序（逆向）
void InsertSort_down(int a[], int n)
{
int temp, i, j;
for (int i = 0; i < n - 1; i++)
{
int end = i + 1;
int temp = a[end];
if (a[end] > a[i])
{
while (end > 0 && temp > a[end - 1])
{
a[end] = a[end - 1];
end--;
}
}
a[end] = temp;
}
}
//折半插入排序（正向）
void BinaryInsertionSort_up(int a[], int left, int right)
{
int i, j;
int mid, temp;
i = left, j = right;
mid = a[(left + right) >> 1];
do
{
while (a[i] < mid && (i < right))
i++;
while (a[j] > mid && (j > left))
j--;
if (i <= j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
} while (i <= j);
if (left < j)
BinaryInsertionSort_up(a, left, j);
if (right > i)
BinaryInsertionSort_up(a, i, right);
}
//折半插入排序（逆向）
void BinaryInsertionSort_down(int a[], int n)
{
BinaryInsertionSort_up(a, 0, n - 1);
reverse(&a[0], &a[50001]);
}
//2-路插入排序（正向）
void TwoInsertSort_up(int a[], int n)
{
int* tmp = new int[n]; //臨時數(shù)組
int front = 0, rear = 0; //記錄當(dāng)前tmp數(shù)組中最大值和最小值的位置
tmp[0] = a[0]; //初始化tmp
for (int i = 1; i < n; i++)
{
int key = a[i];
//如果當(dāng)前插入的元素比最小的元素更小
if (key < tmp[front])
{
front = (front - 1 + n) % n;
tmp[front] = key;
}
//如果當(dāng)前插入元素比最大元素更大
else if (key > tmp[rear])
{
rear = (rear + 1 + n) % n;
tmp[rear] = key;
}
//如果在當(dāng)前最小和最大之間
else
{
int k = (rear + n) % n;
//將比當(dāng)前插入值key大的進(jìn)行后移
while (tmp[(k + n) % n] > key)
{
tmp[(k + 1 + n) % n] = tmp[(k + n) % n];
k = (k - 1 + n) % n;
}
tmp[(k + 1 + n) % n] = key; //當(dāng)前插入值放到合適位置
rear = (rear + 1 + n) % n; //更新最大值位置(有序序列長度+1)
}
}
//復(fù)制臨時數(shù)組到原數(shù)組中
for (int k = 0; k < n; k++)
a[k] = tmp[(front + k) % n];
delete[] tmp;
}
//2-路插入排序（逆向）
void TwoInsertSort_down(int a[], int n)
{
int* tmp = new int[n]; //臨時數(shù)組
int front = 0, rear = 0; //記錄當(dāng)前tmp數(shù)組中最大值和最小值的位置
tmp[0] = a[0]; //初始化tmp
for (int i = 1; i < n; i++)
{
int key = a[i];
//如果當(dāng)前插入的元素比最小的元素更小
if (key < tmp[front])
{
front = (front - 1 + n) % n;
tmp[front] = key;
}
//如果當(dāng)前插入元素比最大元素更大
else if (key > tmp[rear])
{
rear = (rear + 1 + n) % n;
tmp[rear] = key;
}
//如果在當(dāng)前最小和最大之間
else
{
int k = (rear + n) % n;
//將比當(dāng)前插入值key大的進(jìn)行后移
while (tmp[(k + n) % n] > key)
{
tmp[(k + 1 + n) % n] = tmp[(k + n) % n];
k = (k - 1 + n) % n;
}
tmp[(k + 1 + n) % n] = key; //當(dāng)前插入值放到合適位置
rear = (rear + 1 + n) % n; //更新最大值位置(有序序列長度+1)
}
}
//復(fù)制臨時數(shù)組到原數(shù)組中
for (int k = 0; k < n; k++)
a[k] = tmp[(front + k) % n];
reverse(&a[0], &a[50001]);//倒序
delete[] tmp;
}
//希爾排序（正向）
void ShellSort_up(int a[], int n)
{
int temp = n;//初始化增量
while (temp > 1)//最后一次增量為1
{
temp = temp / 3 + 1;
for (int i = temp; i < n; i++)
{
int key = a[i];//當(dāng)前需要插入的數(shù)
int j = i - temp;
while (j >= 0 && a[j] > key)
{
a[j + temp] = a[j];
j -= temp;
}
a[j + temp] = key;
}
}
}
//希爾排序（逆向）
void ShellSort_down(int a[], int n)
{
int temp = n;//初始化增量
while (temp > 1)//最后一次增量為1
{
temp = temp / 3 + 1;
for (int i = temp; i < n; i++)
{
int key = a[i];//當(dāng)前需要插入的數(shù)
int j = i - temp;
while (j >= 0 && a[j] > key)
{
a[j + temp] = a[j];
j -= temp;
}
a[j + temp] = key;
}
}
reverse(&a[0], &a[50001]);
}
//快速排序（正向）
int GetMid(int a[], int left, int right)
{
int mid = (left + right) >> 1;
if (a[left] < a[mid])
if (a[mid] < a[right])
return mid;
else
if (a[left] < a[right])
return right;
else
return left;
else
if (a[mid] > a[right])
return right;
else
return left;
}
int PartitionBetter(int a[], int left, int right)
{
int pos = GetMid(a, left, right);
swap(a[pos], a[left]);
int i = left;
int j = right;
int key = a[left];
while (i != j)
{
while (i < j && a[j] >= key)
j--;
while (i < j && a[i] <= key)
i++;
swap(a[i], a[j]);
}
swap(a[i], a[left]);
return i;
}
void QuickSort_up(int a[], int left, int right)
{
if (left >= right)
return;
int i = PartitionBetter(a, left, right);
QuickSort_up(a, left, i - 1);
QuickSort_up(a, i + 1, right);
}
//快速排序（逆向）
void QuickSort_down(int a[], int n)
{
QuickSort_up(a, 0, n - 1);
reverse(&a[0], &a[50001]);
}
//選擇排序（正向）
void SelectSort_up(int a[], int n)
{
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (a[min] > a[j])
min = j;
}
swap(a[i], a[min]);
}
}
//選擇排序（逆向）
void SelectSort_down(int a[], int n)
{
SelectSort_up(a, n);
reverse(&a[0], &a[50001]);
}
//錦標(biāo)賽排序（正向）
void TreeSelectSort_up(int a[], int n)
{
int sum = n * 2 - 1;//滿二叉樹節(jié)點總數(shù)
int* tree = new int[sum];
//輸入葉子節(jié)點
for (int i = n - 1, j = 0; i >= 0; i--, j++)
tree[sum - j - 1] = a[i];
//非葉子節(jié)點
for (int i = sum - n - 1; i >= 0; i--)
tree[i] = tree[2 * i + 1] < tree[2 * i + 2] ? tree[2 * i + 1] : tree[2 * i + 2];
int k = 0;
int minindex = -1;
while (k < n)
{
int min = tree[0];
a[k++] = min;
minindex = sum - 1;
//從最后葉子節(jié)點開始找到最小值的位置，將其設(shè)置為MAXIUM
while (tree[minindex] != min)
minindex--;
tree[minindex] = INT_MAX;
//若該節(jié)點有父節(jié)點，將其兄弟結(jié)點提升為父節(jié)點
while (minindex > 0)
{
if (minindex % 2 == 1)
{
tree[(minindex - 1) / 2] = tree[minindex] < tree[minindex + 1] ? tree[minindex] : tree[minindex + 1];
minindex = (minindex - 1) / 2;
}
else
{
tree[minindex / 2 - 1] = tree[minindex] < tree[minindex - 1] ? tree[minindex] : tree[minindex - 1];
minindex = minindex / 2 - 1;
}
}
}
delete[] tree;
}
//錦標(biāo)賽排序（逆向）
void TreeSelectSort_down(int a[], int n)
{
TreeSelectSort_up(a, n);
reverse(&a[0], &a[50001]);
}
//堆排序（正向）
void Heapify(int a[], int i, int n)
{
int left = 2 * i + 1, right = 2 * i + 2;//二叉樹當(dāng)前節(jié)點的左右節(jié)點
int max = i;//默認(rèn)i為最大值
if (left < n && a[left]>a[max])
max = left;
if (right <n && a[right]>a[max])
max = right;
if (max != i)
{
//調(diào)整最大值到非葉子節(jié)點處
swap(a[i], a[max]);
//互換后，子節(jié)點變化，若子節(jié)點有其子節(jié)點仍需調(diào)整，遞歸
Heapify(a, max, n);
}
}
void HeapSort_up(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)//構(gòu)建大根堆
Heapify(a, i, n);
while (n > 1)
{
swap(a[0], a[n - 1]);//交換首位數(shù)據(jù)，尾部最大
Heapify(a, 0, --n);//重置大根堆
}
}
//堆排序（逆向）
void HeapSort_down(int a[], int n)
{
HeapSort_up(a, n);
reverse(&a[0], &a[50001]);
}
//歸并排序（正向）
void Merge(int a[], int left, int mid, int right)
{
int* temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
if (a[i] < a[j])
{
temp[k] = a[i];
i++;
}
else
{
temp[k] = a[j];
j++;
}
k++;
}
while (i <= mid)
{
temp[k] = a[i];
i++;
k++;
}
while (j <= right)
{
temp[k] = a[j];
j++;
k++;
}
i = left;
for (int tempK = 0; ((tempK < k) && (i <= right)); tempK++)
{
a[i] = temp[tempK];
i++;
}
delete[] temp;
temp = NULL;
}
void MergeSort_up(int a[], int left, int right)
{
if (left < right)
{
int mid = (left + right) >> 1;
MergeSort_up(a, left, mid);
MergeSort_up(a, mid + 1, right);
Merge(a, left, mid, right);
}
}
//歸并排序（逆向）
void MergeSort_down(int a[], int n)
{
MergeSort_up(a, 0, 50000);
reverse(&a[0], &a[50001]);
}
//基數(shù)排序（正向）
//求數(shù)據(jù)的最大位數(shù), 決定排序次數(shù)
int maxbit(int a[], int n)
{
int d = 1; //保存最大的位數(shù)
int p = 10;
for (int i = 0; i < n; ++i)
{
while (a[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void RadixSort_up(int a[], int n) //基數(shù)排序
{
int d = maxbit(a, n);
int tmp[50001];
int count[10]; //計數(shù)器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++) //進(jìn)行d次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計數(shù)器
for (j = 0; j < n; j++)
{
k = (a[j] / radix) % 10; //統(tǒng)計每個桶中的記錄數(shù)
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
for (j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
{
k = (a[j] / radix) % 10;
tmp[count[k] - 1] = a[j];
count[k]--;
}
for (j = 0; j < n; j++) //將臨時數(shù)組的內(nèi)容復(fù)制到a中
a[j] = tmp[j];
radix = radix * 10;
}
}
//基數(shù)排序（逆向）
void RadixSort_down(int a[], int n)
{
RadixSort_up(a, n);
reverse(&a[0], &a[50001]);
}
int main()
{
srand(time(0));
clock_t start1, end1;
clock_t start2, end2;
clock_t start3, end3;
clock_t start4, end4;
clock_t start5, end5;
clock_t start6, end6;
clock_t start7, end7;
clock_t start8, end8;
clock_t start9, end9;
clock_t start10, end10;
clock_t start11, end11;
clock_t start12, end12;
clock_t start13, end13;
clock_t start14, end14;
clock_t start15, end15;
clock_t start16, end16;
clock_t start17, end17;
clock_t start18, end18;
clock_t start19, end19;
clock_t start20, end20;
double duration;
int a[50001];
int n = 50001;//數(shù)組元素的個數(shù)，即隨機(jī)數(shù)的個數(shù)
Random(a, n, 1, 32767);
start9 = clock();
QuickSort_up(a, 0, n - 1);
end9 = clock();
duration = (double)(end9 - start9) / CLOCKS_PER_SEC;
save(a, "快速排序（正向）", duration);
cout << "快速排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start10 = clock();
QuickSort_down(a, n);
end10 = clock();
duration = (double)(end10 - start10) / CLOCKS_PER_SEC;
save(a, "快速排序（反向）", duration);
cout << "快速排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start1 = clock();
InsertSort_up(a, n);
end1 = clock();
duration = (double)(end1 - start1) / CLOCKS_PER_SEC;
save(a, "直接插入排序（正向）", duration);
cout << "直接插入排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start2 = clock();
InsertSort_down(a, n);
end2 = clock();
duration = (double)(end2 - start2) / CLOCKS_PER_SEC;
save(a, "直接插入排序（反向）", duration);
cout << "直接插入排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start3 = clock();
BinaryInsertionSort_up(a, 0, n - 1);
end3 = clock();
duration = (double)(end3 - start3) / CLOCKS_PER_SEC;
save(a, "折半插入排序（正向）", duration);
cout << "折半插入排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start4 = clock();
BinaryInsertionSort_down(a, n);
end4 = clock();
save(a, "折半插入排序（反向）", duration);
cout << "折半插入排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start5 = clock();
TwoInsertSort_up(a, n);
end5 = clock();
duration = (double)(end5 - start5) / CLOCKS_PER_SEC;
save(a, "2-路插入排序（正向）", duration);
cout << "2-路插入排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start6 = clock();
TwoInsertSort_down(a, n);
end6 = clock();
duration = (double)(end6 - start6) / CLOCKS_PER_SEC;
save(a, "2-路插入排序（反向）", duration);
cout << "2-路插入排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start7 = clock();
ShellSort_up(a, n);
end7 = clock();
duration = (double)(end7 - start7) / CLOCKS_PER_SEC;
save(a, "希爾排序（正向）", duration);
cout << "希爾排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start8 = clock();
ShellSort_down(a, n);
end8 = clock();
duration = (double)(end8 - start8) / CLOCKS_PER_SEC;
save(a, "希爾排序（反向）", duration);
cout << "希爾排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start11 = clock();
SelectSort_up(a, n);
end11 = clock();
duration = (double)(end11 - start11) / CLOCKS_PER_SEC;
save(a, "選擇排序（正向）", duration);
cout << "選擇排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start12 = clock();
SelectSort_down(a, n);
end12 = clock();
duration = (double)(end12 - start12) / CLOCKS_PER_SEC;
save(a, "選擇排序（反向）", duration);
cout << "選擇排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start13 = clock();
TreeSelectSort_up(a, n);
end13 = clock();
duration = (double)(end13 - start13) / CLOCKS_PER_SEC;
save(a, "錦標(biāo)賽排序（正向）", duration);
cout << "錦標(biāo)賽排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start14 = clock();
TreeSelectSort_down(a, n);
end14 = clock();
duration = (double)(end14 - start14) / CLOCKS_PER_SEC;
save(a, "錦標(biāo)賽排序（反向）", duration);
cout << "錦標(biāo)賽排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start15 = clock();
HeapSort_up(a, n);
end15 = clock();
duration = (double)(end15 - start15) / CLOCKS_PER_SEC;
save(a, "堆排序（正向）", duration);
cout << "堆排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start16 = clock();
HeapSort_down(a, n);
end16 = clock();
duration = (double)(end16 - start16) / CLOCKS_PER_SEC;
save(a, "堆排序（反向）", duration);
cout << "堆排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start17 = clock();
MergeSort_up(a, 0, 50000);
end17 = clock();
duration = (double)(end17 - start17) / CLOCKS_PER_SEC;
save(a, "歸并排序（正向）", duration);
cout << "歸并排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start18 = clock();
MergeSort_down(a, 50001);
end18 = clock();
duration = (double)(end18 - start18) / CLOCKS_PER_SEC;
save(a, "歸并排序（反向）", duration);
cout << "歸并排序（反向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start19 = clock();
RadixSort_up(a, n);
end19 = clock();
duration = (double)(end19 - start19) / CLOCKS_PER_SEC;
save(a, "基數(shù)排序（正向）", duration);
cout << "基數(shù)排序（正向）：" << duration << "seconds" << endl;
Random(a, n, 1, 32767);
start20 = clock();
RadixSort_down(a, n);
end20 = clock();
duration = (double)(end20 - start20) / CLOCKS_PER_SEC;
save(a, "基數(shù)排序（反向）", duration);
cout << "基數(shù)排序（反向）：" << duration << "seconds" << endl;
return 0;
}
運行結(jié)果
總結(jié)
- 上一篇： 文心一言 VS 讯飞星火 VS chat
- 下一篇： spring--集成RocketMQ