在書中，各種內部排序演算法的時間復雜度分析結果只給出了演算法執行時間的階，或大概執行時間，試通過具體資料比較各種演算法的關鍵字比較次數和記錄移動次數，以取得直觀感受，
要求：
（1）撰寫程式創建一些整數檔案用于排序，創建的這些檔案可以根據需要生成不同的長度，如長度分別為20，200和2000，以正序、逆序、隨機順序的方式創建這些檔案，通過把所有這些測驗資料保存在檔案中（而不是每次在測驗程式時用亂數生成），可以使用同樣的資料去測驗不同的方法，因此會更易于比較這些方法的性能，
（2）資料表采用順序存盤結構，實作插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序等排序，并對這些演算法的實作效率進行比較和分析，
（3）排序的指標包含：運行時間，比較次數，移動次數，
//suda的同窗請勿直接copy，可參考，
原始碼：
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<ctime>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 2e4 + 5;
int Mod = 1e9 + 7;
class mysort
{
public:
mysort() {};
void sec_sort(int n,int* s);
void insert_sort(int n, int* s);
void merge(int f1, int l1, int l2,int* a);
void merge_sort(int f, int l,int* a);
void shell_sort(int n, int* a);
void sift(int k, int l, int* lst);
void heap_sort(int n,int* a);
int part(int l, int r, int* lst);
void quick_sort(int f, int l, int* a);
void init();
int* get_data(int n) { return data[n]; }
private:
int data[4][20005];//1為正序 2逆序 3隨機
};
int lst[20005], count1 = 0, count2 = 0;
void fz(int n, int* a, int* b)
{
for (int i = 1;i <= n;i++)b[i] = a[i];
count1 = 0, count2 = 0;
}
void mysort::sift(int k, int l, int* lst)
{
int i, j, t;
i = k;j = 2 * i ;
while (j <= l)
{
count1 += 2;
if (j < l && lst[j + 1] > lst[j])j++;
if (lst[i] > lst[j])break;
else
{
t = lst[i], lst[i] = lst[j], lst[j] = t;
i = j;j = i * 2 ;count2++;
}
}
}
void mysort::heap_sort(int n, int* lst)
{
int i, t;
for (int i = n / 2;i >= 1;i--)sift(i, n,lst);
for (int i = 1;i <= n;i++)
{
t = lst[1];lst[1] = lst[n - i + 1];lst[n - i + 1] = t;count2++;
sift(1, n - i,lst);
}
}
void mysort::quick_sort(int f, int l, int* a)
{
if (f >= l) return;
else
{
int p = part(f, l, a);
quick_sort(f, p - 1, a);
quick_sort(p + 1, l, a);
}
}
int mysort::part(int f, int l, int* lst)
{
int i = f, j = l, t;
while (i < j)
{
count1 += 2;
while (lst[i] <= lst[j] && i < j) { j--;count1++;}
if (i < j)
{
t = lst[i], lst[i] = lst[j], lst[i] = t;i++;
count2++;
}
while (lst[i] <= lst[j] && i < j) {i++;count1++;}
if (i < j)
{
t = lst[i], lst[i] = lst[j], lst[j] = t;j--;
count2++;
}
}
return i;
}
void mysort::shell_sort(int n, int* a)
{
fz(20000, a, lst);
int d, i, j, t, count1 = 0, count2 = 0;
clock_t b, f;
b = clock();
for (d = n / 2;d >= 1;d = d / 2)
{
for (i = d;i <= n;i++)
{
t = lst[i];count1++;
for (j = i - d;j >= 1 && t < lst[j];j -= d)
{
lst[j + d] = lst[j];count1++;count2++;
}
lst[j + d] = t;count2++;
}
}
f = clock();
cout <<"比較次數：" << count1
<< endl << "移動次數：" << count2 << "耗時：" << f - b << endl;
}
void mysort::merge_sort(int f, int l,int* a)
{
if (f == l)return;
else
{
int mid = (f + l) / 2;
merge_sort(f, mid,a);
merge_sort(mid + 1, l,a);
merge(f, mid, l,a);
}
}
int t[20005];
void mysort::merge(int f1, int l1, int l2,int* a)
{
int i = f1, j = l1 + 1, k = f1;
while (i <= l1 && j <= l2)
{
count1++;count2++;
if (a[i] <= a[j])t[k++] = a[i++];
else t[k++] = a[j++];
}
while (i <= l1) { t[k++] = a[i++];count2++; }
while (j <= l2) { t[k++] = a[j++];count2++; }
for (int i = f1;i <= l2;i++)
{
a[i] = t[i];count2++;
}
}
void mysort::init()
{
for (int i = 1;i <= 20005;i++)
{
int q=1 + rand() % 20000;
data[3][i] = q; data[1][i] = q; data[2][i] = q;
}
sort(data[1] + 1, data[1] + 20000);
sort(data[2] + 1, data[2] + 20000, greater<int>());
}
void mysort::sec_sort(int n,int* a)
{
fz(n, a, lst);
int d = 0,count1 = 0, count2 = 0;
ll count = 0;
clock_t b, f;
b = clock();
for (int i = 1;i <= n;i++)
{
d = i;
for (int j = i+1;j <= n;j++)
{
if (lst[d] < lst[j])d = j;
count1++;
}
int t = lst[i];lst[i] = lst[d];lst[d] = t;
count2 += 1;
}
f = clock();
cout << "比較次數：" << count1
<< endl << "移動次數：" << count2 << "耗時：" << f - b << endl;
}
void mysort::insert_sort(int n, int* a)
{
fz(n, a, lst);
int j, t, count1 = 0, count2 = 0;
ll count = 0;
clock_t b, f;
b = clock();
for (int i = 2;i <= n;i++)
{
t = lst[i];
count1 += 2;
for (j = i - 1;j >= 1 && t < lst[j];j--) { lst[j + 1] = lst[j]; count1++;count2++; }
if (t != lst[j+1]) { lst[j + 1] = t;count2++; }
}
f = clock();
cout << "比較次數：" << count1
<< endl << "移動次數：" << count2 << "耗時：" << f - b << endl;
}
mysort s;
clock_t b, f;
void xinit(int n)
{
count1 = 0;count2 = 0;
}
void out()
{
cout << "比較次數：" << count1
<< endl << "移動次數：" << count2 << "耗時：" << f - b << endl << endl;
}
void project()
{
s.init();
int n=1;
while(n)
{
system("cls");
cout << "輸入想要對多少個元素排序（超過3500在極端條件下快排會迭代過多爆堆疊區，退出程式,但為了比較更大資料n最多不超過2W）" << endl;
cin >> n;
system("cls");
cout << "插入排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
s.insert_sort(n, s.get_data(1));
cout <<endl<< "無序表結果：" << endl;
s.insert_sort(n, s.get_data(2));
cout << endl << "亂序表結果：" << endl;
s.insert_sort(n, s.get_data(3));
cout << endl;
cout << "選擇排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
s.sec_sort(n, s.get_data(1));
cout <<endl<< "無序表結果：" << endl;
s.sec_sort(n, s.get_data(2));
cout <<endl<< "亂序表結果：" << endl;
s.sec_sort(n, s.get_data(3));
cout << endl;
cout << "希爾排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
s.shell_sort(n, s.get_data(1));
cout <<endl<< "無序表結果：" << endl;
s.shell_sort(n, s.get_data(2));
cout <<endl<< "亂序表結果：" << endl;
s.shell_sort(n, s.get_data(3));
cout << endl;
cout << "歸并排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
fz(n, s.get_data(1), lst);b = clock();
s.merge_sort(1,n,lst);
f = clock();out();
cout << "無序表結果：" << endl;
fz(n, s.get_data(2), lst);b = clock();
s.merge_sort(1, n, lst);
f = clock();out();
cout << "亂序表結果：" << endl;
fz(n, s.get_data(3), lst);b = clock();
s.merge_sort(1, n, lst);
f = clock();out();
cout << endl;
cout << "堆排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
fz(n, s.get_data(1), lst);b = clock();
s.heap_sort(n, lst);
f = clock();out();
cout << "無序表結果：" << endl;
fz(n, s.get_data(2), lst);b = clock();
s.heap_sort(n, lst);
f = clock();out();
cout << "亂序表結果：" << endl;
fz(n, s.get_data(3), lst);b = clock();
s.heap_sort(n, lst);
f = clock();out();
cout << endl;
cout << "快速排序結果如下" << endl << endl;
cout << "有序表結果：" << endl;
fz(n, s.get_data(1), lst);b = clock();
s.quick_sort(1, n, lst);
f = clock();out();
cout << "無序表結果：" << endl;
fz(n, s.get_data(2), lst);b = clock();
s.quick_sort(1, n, lst);
f = clock();out();
cout << "亂序表結果：" << endl;
fz(n, s.get_data(3), lst);b = clock();
s.quick_sort(1, n, lst);
f = clock();out();
cout << endl;
cout << "如果想退出，輸入0否則輸入1" << endl;
cin >> n;
}
}
int main()
{
project();
return 0;
}
這估計是今年最后一篇博文了，借此機會來總結記錄一下今年的學習與生活，
在上半年的家里蹲程序中，可以說還是很愜意和開心的，學習上：周一至周五把該上的網課上了，然后課余時間提前把資料結構學了一遍，配合著資料結構的書把大一寒假看的啊哈演算法復習了，在網路攻防上也學習了更多基于kali的攻擊方法，在網易云課堂上報了聲樂課，以前連氣泡音、唇顫音怎么發都不知道，學習這方面還是挺有意思的，去新華書店將之前學的催眠復習了一遍，但是練習的機會不多沒感覺有什么進步，生活上：晚上和好友一起跑步，一起交流生活和學習中的問題（朋友選學計算機，非常強），在周末我們6個好朋友抽一天早上買食材，中午BBQ，晚上一起LOL開黑，或者是一起去騎行、爬山，現在回想起來感覺那些日子好爽，
到了暑假及下半年，當時抱著去acm集訓隊學習演算法的氛圍濃厚好去學習一段時間，結果現在上了車組好了隊，開始了acmer生涯，同時也很幸運地遇到了兩個有趣且優秀的隊友，感謝slf、szb這半年的陪伴與幫助，讓這平淡大學生活多出了不少樂趣，這下半年，主要都學習演算法去了，畢竟感覺自己本身基礎很差，要多加訓練才行，希望接下來的ICPC濟南站和太極杯能順利吧，不知不覺又到了一點，該回寢了，不過想到明天無早八，估計室友還在打元神，正好回去泡杯牛奶，睡覺，最后要說這一年有什么遺憾的話，估計是沒找到npy…汰
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239666.html
標籤：其他
上一篇：計算機圖形學——實驗五