当前位置 博文首页 > asbbv的博客：排序算法的实现及性能测试及比较
在书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过具体数据比较各种算法的关键字比较次数和记录移动次数，以取得直观感受。
要求：
（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,
