int main()
{
create_num();
for(int i = 0; i < 100; i++){
cout<<arr[i]<<" ";
}
cout<<endl;

BubbleSort();
InsertSort();
SelectSort();
QuickSort();
BInsertSort();
TwoWayInsertSort();
ShellSort();
HeapSort();
MergeSort();

return 0;
}


#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int arr[100];
int m=0, n=0;
//生成随机数
void create_num()
{
//用时间做种子，每次产生的随机苏不一样
srand((unsigned)time(NULL));
for(int i = 0; i < 100; i++){
arr[i] = rand() % 1000 + 1;
}
}

//起泡排序
void BubbleSort()
{
int s[100];
//m是比较次数，n是移动次数
int i, j, tmp, m, n;
m=0, n=0;
for(i = 0; i < 100; i++)
s[i] = arr[i];
for(i = 0; i < 99; i++)
for(j = 0; j <100 - i-1; j++){
if(s[j]>s[j+1]){
tmp = s[j];
s[j] = s[j+1];
s[j+1] = tmp;
n+=3;
}
m++;
}
cout<<"BubbleSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//直接插入排序
InsertSort()
{
int s[101];
//m是比较次数，n是移动次数
int i, j, m, n;
m=0, n =0;
for(i = 1; i <= 100; i++)
s[i] = arr[i-1];
for(i = 2; i < 100; i++){
if(s[i] < s[i-1]){
s[0] = s[i];        //将待插入的记录暂存到监视哨中
s[i] = s[i-1];
n += 2;
for(j = i-2; s[0] < s[j]; --j){//从后向前寻找插入位置
s[j+1] = s[j];      //记录逐个后移，直到找到插入位置
m++;
n++;
}
m++;
s[j+1] = s[0];             //将r[0]即原r[i]，插入到正确位置
}
m++;
}
cout<<"InsertSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//简单选择排序
void SelectSort()
{
int s[100];
//m是比较次数，n是移动次数
int i, j, m, n, tmp, k;
m=0, n =0;
for(i = 0; i < 100; i++)
s[i] = arr[i];
for(i = 0; i < 99; i++){
k = i;
for(j = i; j < 99; j++){
if(s[j]<s[k])
k = j;
m++;
}
if(k != i){
tmp = s[k];
s[k] = s[i];
s[i] = tmp;
n+=3;
}
}
cout<<"SelectSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//快速排序
int partition(int r[],int first,int end)//划分
{
int i=first,j=end;//初始化待划分区间
while(i<j)
{
while(i<j&&r[i]<=r[j])//右侧扫描
{
j--;
m++;
}
if(i<j)
{
int temp=r[i];//将较小记录交换到前面
r[i]=r[j];
r[j]=temp;
n+=3;
}
while(i<j&&r[i]<=r[j])//左侧扫描
{
i++;
m++;
}
if(i<j)
{
int temp=r[i];//将较大记录交换到后面
r[i]=r[j];
r[j]=temp;
n+=3;
j--;
}
}
return i;//返回轴值记录的位置
}
void QuickSort_shixian(int r[],int first,int end)//快速排序
{
int pivot;
if(first<end)
{
pivot=partition(r,first,end);//划分，pivot是轴值在序列中的位置
QuickSort_shixian(r,first,pivot-1);//求解子问题1，对左侧子序列快排
QuickSort_shixian(r,pivot+1,end);//求解子问题2，对右侧子序列快排
}
}
void QuickSort()
{
int s[100];
for(int i = 0; i < 100; i++)
s[i] = arr[i];
QuickSort_shixian(s, 0, 99);
cout<<"QuickSort: "<<"compare "<<m<<", move "<<n<<endl;

}

//希尔排序
void ShellSort()
{
int s[100], tmp, m=0, n = 0;
for(int i = 0; i < 100; i++)
s[i] = arr[i];
for(int div=100/2; div >=1; div=div/2)//定增量div，并不断减小
{
for(int i = 0; i <= div; ++i){//分组成div组
for(int j = i; j < 100-div; j+=div)//对每组进行插入排序
for(int k = j; k < 100; k+=div){
if(s[j]>s[k]){
tmp = s[j];
s[j] = s[k];
s[k] = tmp;
n+=3;
}
m++;
}
}
}
cout<<"ShellSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//折半插入排序
void BInsertSort()
{
int i, j, low, high, t, s[101], m, n;
m = 0, n =0;
for(int i = 1; i <= 100; i++)
s[i] = arr[i-1];
for(i = 2; i <= 100; i++){
s[0] = s[i];//将待插入的记录暂存到监视哨中
low = 1; high = i-1;  //置查找区间初值
while(low <= high){
//在r[low..high]中折半查找插入的位置
t = (low + high)/2;//折半
if(s[0] < s[t])
high = t-1;//插入点在前一子表
else
low = t+1; //插入点在后一子表
m++;
}
for(j = i-1; j >= high+1; --j){
s[j+1] = s[j];  //记录后移
n++;
}
s[high+1]=s[0];//将r[0]即原r[i]，插入到正确位置
n++;
}
cout<<"BInsertSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//二路插入排序
void TwoWayInsertSort()
{
int first, last,i, m=0, n=0;
int s[101],*b = new int[101];
first = last = 0;
for(i = 0; i < 100; i++){
s[i]=arr[i];
}
b[0] = s[0];
for(int i = 1; i < 100; i++){
m++;
if(s[i]<b[first]){
first = (first - 1 + 100) % 100;
b[first] = s[i];
n++;
}
else if (s[i] >= b[last]){
last++;
b[last] = s[i];
n++;
}
else{
int low, high, mid, d;
low = first, high = last;
while(low != high){//折半查找
d = (high - low + 100) % 100;  //元素个数
mid = (low + d / 2) % 100;  //中间位置
m++;
if(s[i] < b[mid])
high = mid;
else
low = (mid + 1) % 100;
}
for(int k = last + 1; k != low; k = (k -1 + 100)%100){
b[k] = b[(k - 1 + 100) % 100];
n++;
}
b[low] = s[i];
n++;
last ++;
}
}
for(int i = 0; i < 100; i++){
s[i] = b[(i + first) % 100];
n++;
}
delete []b;
cout<<"TwoWayInsertSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//基数排序
{
int s[100],d = 3;
int *tmp = new int[100];
int *count = new int[10];//计数器
int i, j, k, m=0, n=0;
for(i = 0; i < 100; i++){
s[i]=arr[i];
}
for(i = 1; i <= d; i++){
for(j = 0; j < 10; j++)
count[j] = 0;//每次分配前清空计数器
for(j = 0; j < 100; j++){
k = (s[j] / radix) % 10;
count[k] ++;
}
for(j = 1; j < 10; j++)
count[j] = count[j-1] + count[j];
for(j = 99; j >= 0; j--){
k = (s[j] / radix) % 10;
tmp[count[k] - 1] = s[j];
n++;
count[k]--;
}
for(j = 0; j < 100; j++){
n++;
s[j] = tmp[j];
}
}
delete []tmp;
delete []count;
}

//堆排序
void MinHeapify(int *arr, int size, int element)
{
int tmp, lchild = element*2+1,rchild = lchild+1;//左右子树
while(rchild < size){//子树均在范围内
if(arr[element]<=arr[lchild]&&arr[element]<=arr[rchild])
{//如果比左右子树都小，完成整理
m+=2;
return;
}
if(arr[lchild]<=arr[rchild]){
tmp = arr[element];
arr[element] = arr[lchild];//把左面的提到上面
arr[lchild] = tmp;
element = lchild;
m+=2;
n+=3;
}
else{
tmp = arr[element];
arr[element] = arr[rchild];//把右面的提到上面
arr[rchild] = tmp;
element = rchild;
m++;
n+=3;
}
lchild = element*2+1;
rchild = lchild + 1;//重新计算子树位置
}
if(lchild<size&&arr[lchild]<arr[element])//只有左子树且子树小于自己
{
tmp = arr[lchild];
arr[lchild] = arr[element];
arr[element] = tmp;
n+=3;
}
m++;
return;
}
void HeapSort()
{
int i, j, tmp, s[100],size=100;
m=0,n=0;
for(i = 0; i < 100; i++){
s[i]=arr[i];
}
for(i = size-1; i>=0; i--){
MinHeapify(s, 100, i);
}
while(size>0){//拆除树
tmp = s[size-1]; //将根（最小）与数组最末交换
s[size-1] = s[0];
s[0] = tmp;
size--;
MinHeapify(s, size, 0);
}
cout<<"HeapSort: "<<"compare "<<m<<", move "<<n<<endl;
}

//归并排序
void merge(int* a, int lo, int mid, int hi)
{//
int i = lo, j = mid + 1,aux[100];
for(int k = lo; k <= hi; k++) {
aux[k] = a[k];
n++;
}
for(int k = lo; k <= hi; k++){
if    (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j] < aux[i]){
a[k] = aux[j++];
}
else
a[k] = aux[i++];
n++;
}
}

void sort(int* a, int lo, int hi)
{//
if(hi <= lo)
return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
m++;           //
sort(a, mid+1, hi);        //
m++;
merge(a, lo, mid, hi);    //

}

void MergeSort()
{
int s[100];
m=0,n=0;
for(int i =0; i < 100; i++)
s[i] = arr[i];
sort(s, 0, 99);
cout<<"MergeSort: "<<"compare "<<m<<", move "<<n<<endl;
}

int main()
{
create_num();
for(int i = 0; i < 100; i++){
cout<<arr[i]<<" ";
}
cout<<endl;

BubbleSort();
InsertSort();
SelectSort();
QuickSort();
BInsertSort();
TwoWayInsertSort();