排序算法
- 插入排序
- 折半插入排序
- 希尔排序
- 冒泡排序
- 快速排序
- 简单选择排序
- 堆排序
- 归并排序(未完成)
- 基数排序(未完成)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+7;
int dt[MAXN], MOD = 1e9+7;
typedef struct
{
int key;
char *otherinfo;
}ElemType;
ElemType S[MAXN];
typedef struct
{
ElemType *r;
int length;
}SqList;
void InsertSort(SqList &L)//插入排序
{
int i,j;
for(i = 2; i <= L.length; ++i)
{
if(L.r[i].key<L.r[i-1].key)
{
L.r[0] = L.r[i];
L.r[i] = L.r[i-1];
for(j = i-1; L.r[0].key < L.r[j].key; --j)
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0];
}
}
}
void BInsertSort(SqList &L)//折半插入排序
{
int i, j, low, hight, mid;
for(i = 2; i <= L.length; ++i)
{
L.r[0] = L.r[i];
low = 1; hight = i-1;
while(low <= hight)
{
mid = (low+hight)/2;
if(L.r[0].key < L.r[mid].key) hight = mid - 1;
else low = mid + 1;
}
for(j = i - 1; j >= hight+1; --j)
L.r[j+1] = L.r[j];
L.r[hight+1] = L.r[0];
}
}
void ShellInsert(SqList &L, int dk)
{
int i,j;
for(i = dk + 1; i <= L.length; ++i)
{
if(L.r[i].key < L.r[i - dk].key)
{
L.r[0] = L.r[i];
for(j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
L.r[j + dk] = L.r[j];
L.r[j + dk] = L.r[0];
}
}
}
void ShellSort(SqList &L, int t)//希尔排序
{
int k;
for(k = t; k > 0; k = k/2)
ShellInsert(L, k);
// puts("ss");
}
void BubbleSort(SqList &L)//冒泡排序
{
int j, m = L.length - 1, flag = 1;
while((m > 0) && flag)
{
flag = 0;
for(j = 1; j <= m; ++j)
if(L.r[j].key > L.r[j+1].key)
{
flag = 1;
ElemType t = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = t;
}
--m;
}
}
int Partition(SqList &L,int low, int hight)
{
L.r[0] = L.r[low];
int pivotkey = L.r[low].key;
while(low < hight)
{
while(low < hight && L.r[hight].key >= pivotkey) --hight;
L.r[low] = L.r[hight];
while(low < hight && L.r[low].key <= pivotkey) ++low;
L.r[hight] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void QSort(SqList &L, int low, int hight)
{
if(low < hight)
{
int pivotloc = Partition(L, low, hight);
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, hight);
}
}
void QuickSort(SqList &L)//快速排序
{
QSort(L,1,L.length);
}
void SelectSort(SqList &L)//简单选择排序
{
for(int i = 1; i < L.length; ++i)
{
int k = i;
for(int j = i + 1; j <= L.length; ++j)
if(L.r[j].key < L.r[k].key)
k = j;
if(k != i)
{
ElemType t = L.r[i];
L.r[i] = L.r[k];
L.r[k] = t;
}
}
}
void HeapAdjust(SqList &L, int s,int m)//调整为大根堆
{
ElemType rc = L.r[s];
for(int j = 2 * s; j <= m; j *= 2)
{
if(j < m && L.r[j].key < L.r[j+1].key) ++j;
if(rc.key >= L.r[j].key) break;
L.r[s] = L.r[j];
s = j;
}
L.r[s] = rc;
}
void CreatHeap(SqList &L)//建初堆
{
int n = L.length;
for(int i = n/2; i > 0; --i)
HeapAdjust(L,i,n);
}
void HeapSort(SqList &L)//堆排序
{
CreatHeap(L);
for(int i = L.length; i > 1; --i)
{
ElemType x =L.r[1];
L.r[1] = L.r[i];
L.r[i] = x;
HeapAdjust(L,1,i-1);
}
}
void Merge(ElemType R[], ElemType T[], int low, int mid, int high)
{
int i = low, j = mid + 1, k = high;
while(i <= mid && j <= high)
{
if(R[i].key <= R[j].key) T[k++] = R[i++];
else T[k++] = R[j++];
}
while(i <= mid) T[k++] = R[i++];
while(j <= high) T[k++] = R[j++];
}
void MSort(ElemType R[], ElemType T[], int low, int high)
{
if(low == high) T[low] = R[low];
else
{
int mid = (low + high)/2;
MSort(R, S, low, mid );
MSort(R, S, mid+1, high);
Merge(S, T, low, mid, high);
}
}
void MergeSort(SqList &L)
{
MSort(L.r, L.r, 1, L.length);
}
void menu()
{
cout<< " 1.插入排序\n"\
" 2.折半插入排序\n"\
" 3.希尔排序\n"\
" 4.冒泡排序\n"\
" 5.快速排序\n"\
" 6.简单选择排序\n"\
" 7.堆排序\n"\
" 8.归并排序(未完成)\n"\
" 9.基数排序(未完成)\n"\
" 0.退出\n"<<endl;
}
int main()
{
clock_t s,e;
s = clock();
/*正式程序*/
ios::sync_with_stdio(0);
SqList L;
L.r = new ElemType[MAXN];
int choose;
int x = (int)1000;
cout<<"请选择："<<endl;
menu();
cin>>choose;
while(choose)
{
cout<<"请输入随机生成的数据个数：";
cin>>x;
MOD = x*10+7;
srand(time(NULL));
L.length = x;
for(int i=1; i <= L.length; ++i)
L.r[i].key = (rand()*rand()-rand()*2 + MOD )%MOD;
cout<<"数据生成完毕，请问是InsertSort否要查看：Y/N"<<endl;
char ch;
cin>>ch;
if(ch == 'Y' || ch == 'y')
{
cout<<"数据如下所示；"<<endl;
for(int i = 1; i <= L.length; ++i)
cout<<L.r[i].key<<" ";
cout<<endl<<endl;
}
cout<<"排序之后数据为："<<endl;
s = clock();
switch (choose)
{
case 1:InsertSort(L);break;
case 2:BInsertSort(L);break;
case 3:ShellSort(L, L.length);break;
case 4:BubbleSort(L);break;
case 5:QuickSort(L); break;
case 6:SelectSort(L);break;
case 7:HeapSort(L); break;
case 8: break;
case 9: break;
}
for(int i = 1; i <= L.length; ++i)
cout<<L.r[i].key<<" ";
e = clock();
/**输出程序运行时间*****/
cout<<endl;
cout<<"程序运行时间："<<e - s<<"(ms)"<<endl<<endl;
cout<<"****************************************************"<<endl;
cout<<"请选择："<<endl;
menu();
cin>>choose;
}
return 0;
}