//选择排序
#include <iostream>
#include <stdio.h>
#include <malloc.h>
//--------------------------------------------------------------------
//从大到小排序 冒泡排序
void sort_bubble_down(int* a,int len)
{
int temp = 0;
int i = 0;
int j = 0;
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(a[i]<a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
//从小到大排序 冒泡排序
void sort_bubble_up(int* a,int len)
{
int temp = 0;
int i = 0;
int j = 0;
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(a[i]>a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
//--------------------------------------------------------------------
//从小到大排序 选择排序
void sort_select_up(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
for(i=0;i<len;i++)
{
k = i;
for(j=i+1;j<len;j++)
{
if(a[k]>a[j])
{
k = j;
}
}
if(i!=k)
{
a[i] = a[i]+a[k];
a[k] = a[i]-a[k];
a[i] = a[i]-a[k];
}
}
}
//从大到小排序 选择排序
void sort_select_down(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
for(i=0;i<len;i++)
{
k = i;
for(j=i+1;j<len;j++)
{
if(a[k]<a[j])
{
k = j;
}
}
if(i!=k)
{
a[i] = a[i]+a[k];
a[k] = a[i]-a[k];
a[i] = a[i]-a[k];
}
}
}
//--------------------------------------------------------------------
//从小到大排序 插入排序
void sort_insert_up(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
for(i=1;i<len;i++)
{
k = i;
temp = a[k];
for(j=i-1;j>=0;j--)
{
if(a[j]>temp)
{
a[j+1] = a[j];
k = j; //记下移动的位置
}
}
a[k] = temp;//插入
}
}
//从大到小排序 插入排序
void sort_insert_down(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
for(i=1;i<len;i++)
{
k = i;
temp = a[k];
for(j=i-1;j>=0;j--)
{
if(a[j]<temp)
{
a[j+1] = a[j];
k = j; //记下移动的位置
}
}
a[k] = temp;//插入
}
}
//------------------------------------希尔排序--------------------------------
void sort_shell_up(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
int gap = len;
do
{
gap = gap/3 + 1;
for(i=gap;i<len;i=i+gap)
{
k = i;
temp = a[k];
for(j=i-gap;j>=0;j=j-gap)
{
if(a[j]>temp)
{
a[j+gap] = a[j];
k = j;
}
}
a[k] = temp;
}
}while(gap > 1);
}
void sort_shell_down(int* a,int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
int gap = len; //当gap = 1时，就是插入排序
do
{
gap = gap/3 + 1; //这里的gap没有固定的用法，但gap一定要收敛于1
for(i=gap;i<len;i=i+gap)
{
k = i;
temp = a[k];
for(j=i-gap;j>=0;j=j-gap)
{
if(a[j]<temp)
{
a[j+gap] = a[j];
k = j;
}
}
a[k] = temp;
}
}while(gap > 1);
}
//-------------------------------------快速排序--------------------------------
void swap(int* a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int partition_up(int* a,int low,int high)
{
int pv = a[low];
while(low<high)
{
while((low<high)&&(a[high]>=pv))
{
high--;
}
swap(a,low,high);
while((low<high)&&(a[low]<=pv))
{
low++;
}
swap(a,low,high);
}
return low;
}
void QSort_up(int* a,int low,int high)
{
if(low<high)
{
int pv = partition_up(a,low,high);
QSort_up(a,low,pv-1);
QSort_up(a,pv+1,high);
}
}
void sort_quick_up(int* a,int len)
{
QSort_up(a,0,len-1);
}
//-----------
int partition_down(int* a,int low,int high)
{
int pv = a[low];
while(low<high)
{
while((low<high)&&(a[high]<=pv))
{
high--;
}
swap(a,low,high);
while((low<high)&&(a[low]>=pv))
{
low++;
}
swap(a,low,high);
}
return low;
}
void QSort_down(int* a,int low,int high)
{
if(low<high)
{
int pv = partition_down(a,low,high);
QSort_down(a,low,pv-1);
QSort_down(a,pv+1,high);
}
}
void sort_quick_down(int* a,int len)
{
QSort_down(a,0,len-1);
}
//-----------------------------归并排序--------------------------------
void Merge_up(int* src,int* des,int low,int mid,int high)
{
int i = low;
int j = mid+1;
int k = low;
while((i<=mid)&&(j<=high))
{
if(src[i] < src[j])
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while(i<=mid)
{
des[k++] = src[i++];
}
while(j<=high)
{
des[k++] = src[j++];
}
}
void MSort_up(int* src,int* des,int low,int high,int max)
{
int mid = 0;
int* space = (int*)malloc(sizeof(int)*max);
if(low==high)
{
des[low] = src[low];
}
else
{
mid = (low+high) / 2;
if(space!=NULL)
{
MSort_up(src,space,low,mid,max);
MSort_up(src,space,mid+1,high,max);
Merge_up(space,des,low,mid,high);
}
free(space);
}
}
void sort_merge_up(int* a,int len)
{
MSort_up(a,a,0,len-1,len);
}
//----
void Merge_down(int* src,int* des,int low,int mid,int high)
{
int i = low;
int j = mid+1;
int k = low;
while((i<=mid)&&(j<=high))
{
if(src[i] > src[j])
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while(i<=mid)
{
des[k++] = src[i++];
}
while(j<=high)
{
des[k++] = src[j++];
}
}
void MSort_down(int* src,int* des,int low,int high,int max)
{
int mid = 0;
int* space = (int*)malloc(sizeof(int)*max);
if(low==high)
{
des[low] = src[low];
}
else
{
mid = (low+high) / 2;
if(space!=NULL)
{
MSort_down(src,space,low,mid,max);
MSort_down(src,space,mid+1,high,max);
Merge_down(space,des,low,mid,high);
}
free(space);
}
}
void sort_merge_down(int* a,int len)
{
MSort_down(a,a,0,len-1,len);
}
//---------------------------------------------------------------------
int main(int argc, char *argv[])
{
int array[10000] = {0};
int index = 0;
int i = 0;
printf("please input 10000 number!\n");
while((scanf("%d",&array[index]) != EOF)&&(getchar()!='\n'))
{
index++;
}
printf("index = %d\n",index);
for(i=0;i<=index;i++)
{
printf("%dth : %d\n",i,array[i]);
}
printf("down...\n");
sort_merge_down(array,index+1);
for(i=0;i<=index;i++)
{
printf("%dth : %d\n",i,array[i]);
}
printf("up...\n");
sort_merge_up(array,index+1);
for(i=0;i<=index;i++)
{
printf("%dth : %d\n",i,array[i]);
}
return 0;
}
