八种排序算法

/************************************************************************* 
        > Copyright (c)2014  stay hungry,stay foolish !!!  
        > File Name: sort.cpp 
        > Author: kanty 
        > Mail: [email protected]  
        > Created Time: 2014年03月23日 星期日 10时14分20秒 
        > Question Description:  
 ************************************************************************/  
  
#include<iostream>  
using namespace std;  
  
void bubble_sort(int *a,int m)  
{  
    int i,j,temp;  
    for(i=0;i<m-1;i++)//确定比较趟数  
    for(j=0;j<m-1-i;j++)//两两比较  
    if(a[j]>a[j+1])//小的上浮，大的下沉  
    {  
        temp=a[j];  
        a[j]=a[j+1];  
        a[j+1]=temp;  
    }  
}  
void bubble_sort1(int *a,int m)  
{  
    int i,j,temp;  
     bool flag=true;  
     for(i=0;i<m-1&& flag;i++)  
     {  
      flag=false;  
      for(j=0;j<m-1-i;j++)  
      if(a[j]>a[j+1])  
       {//如果本趟不发生交换，说明该序列已经是有序序列了  
        //flag一直为false就不再进行循环了，已经是有序了  
         temp=a[j];  
          a[j]=a[j+1];  
        a[j+1]=temp;  
        flag=true;  
     }  
   }  
}  
void select_sort(int *a,int m)  
{  
    int i,j,k,temp;  
    for(i=0;i<m-1;i++)//比较趟数  
    {  
        k=i;//保存下标  
        for(j=i+1;j<m;j++)  
        if(a[k]>a[j])//将i之后的元素与i对应的元素进行比较，  
        //如果后面的元素小于i对应的元素，则交换下标  
        k=j;  
        if(k!=i)//如果下标不相等就交换对应的元素  
        {  
            temp=a[k];  
            a[k]=a[i];  
            a[i]=temp;  
        }  
    }  
}  
  
int division(int *a,int left,int right)  
{  
    int base=a[left];//定基准  
    while(left<right)  
    {  
        while(left<right && base<a[right])//将最右边的元素与基准进行比较  
        right--;  
        a[left]=a[right];  
        while(left<right && base>a[left])//将最左边的元素与基准进行比较  
        left++;  
        a[right]=a[left];  
    }  
    a[left]=base;  
    return left;//返回中间的基准下标  
}  
void quick_sort(int *a,int left,int right)  
{  
    if(left<right)  
    {  
        int mid=division(a,left,right);//先进行分割  
        quick_sort(a,left,mid-1);//左递归排序  
        quick_sort(a,mid+1,right);//右递归排序  
    }  
}  
  
void insert_sort(int *a,int m)  
{//此为直接插入排序算法  
  int i,j,temp;  
    for(i=1;i<m;i++)  
    {  
        temp=a[i];  
        for(j=i-1;j>=0&&temp<a[j];j--)//循环并进行判断，如果后面的元素小于前边的元素，元素依次向右移位  
        a[j+1]=a[j];  
        a[j+1]=temp;  
    }  
}  
  
void shell_sort(int *a,int m)  
{  
    int i,j,temp,gap;  
    for(gap=m/2;gap>0;gap/=2)//进行间隔递增  
    {  
        for(i=gap;i<m;i++)//从gap开始向后循环  
        {  
            temp=a[i];  
            for(j=i-gap;j>=0&&temp<a[j];j-=gap)//和直接插入排序一样，只是间隔变大而已  
            a[j+gap]=a[j];  
            a[j+gap]=temp;  
        }  
    }  
}  
void b_sort(int *a,int m)  
{//此法是折半排序  
    int i,j,low,mid,high,temp;  
    for(i=1;i<m;i++)  
    {  
        temp=a[i];  
        low=0;  
        high=i-1;  
        while(low<=high)  
        {  
            mid=(low+high)/2;//折半  
            if(temp<a[mid])//判断要插入的位置范围，并缩小插入的位置  
            high=mid-1;  
            else  
            low=mid+1;  
        }  
        for(j=i;j>low;j--)//注意最小为low，有低位向高位移动  
        a[j]=a[j-1];  
        a[low]=temp;  
    }  
}  
  
void merge_step(int *a,int *b,int start,int mid,int end)  
{  
    int i,j,k,temp;  
    i=start;  
    j=mid+1;//将待排序数组分为前后两部分  
    k=0;  
    while(i<=mid && j<=end)//判断前后两部分是否到达边界  
    {  
        if(a[i]<a[j])//比较前后两部分的元素的大小  
        b[k++]=a[i++];//将小的赋值给数组b，并依次后移下标  
        else  
        b[k++]=a[j++];  
    }  
    while(i<=mid)//对于未到达边界的直接赋值给b数组  
    b[k++]=a[i++];  
    while(j<=end)  
    b[k++]=a[j++];  
    for(i=0;i<k;i++)  
    a[start+i]=b[i];//将b数组中排好序的元素重新赋值给a，注意加上start，start为起始边界  
}  
void merge(int *a,int *b,int start,int end)  
{  
    if(start<end)  
    {  
        int mid=(start+end)/2;//折半  
        merge(a,b,start,mid);//左递归依次分割更小的部分  
        merge(a,b,mid+1,end);//右递归依次分割更小的部分  
        merge_step(a,b,start,mid,end);//调用排序算法，分别进行排序  
    }  
}  
void merge_sort(int *a,int m)  
{  
    int *b=new int[m*sizeof(int)];//开辟一个数组空间  
    merge(a,b,0,m-1);//排序算法调用  
    delete [] b;//释放开辟的空间  
    b=0;  
}  
  
void heap_adjust_down(int *a,int start,int end)  
{  
    int i,temp;  
    i=2*start+1;//左孩子节点的下标  
    temp=a[start];//保存首元素  
    while(i<=end)//判断堆是否到达结尾  
    {  
        if(i+1<=end && a[i+1]>a[i])//找出左右孩子中最大一个  
            i++;  
        if(a[i]<=temp)//如果为最大堆顺序就无需调整  
            break;  
        //最大的子节点上移，替换掉父节点  
        a[start]=a[i];  
        start=i;  
        i=2*start+1;  
    }  
    a[start]=temp;//将根节点插入到对应的位置  
}  
  
void heap_sort(int *a,int m)  
{  
    int i,temp;  
    for(i=(m-1)/2;i>=0;i--)  
    //第一个非叶子节点的下标(m-1)/2  
    //首先将数组建成最大二叉堆  
        heap_adjust_down(a,i,m-1);//进行堆排序  
    for(i=m-1;i>0;i--)  
    {//首先将堆顶元素与最后一个元素进行交换  
     //可以始终是数组的最后的一个元素保存为最大元素  
     //当交换后最后一个元素就保存为最大值  
     //对余下的元素重新进行最大堆排序，通过排序将最大值放在数组第一个元素中  
        temp=a[i];  
        a[i]=a[0];  
        a[0]=temp;  
        heap_adjust_down(a,0,i-1);  
    }  
}  
void choose_sort(int *array,int n)  
{  
    cout<<"             please look at the sort algorithm:  "<<endl<<endl;  
    cout<<"*************************     sort      ************************"<<endl;  
    cout<<"***************   1   冒泡排序 bubble_sort     ****************"<<endl;  
    cout<<"***************   2   选择排序 select_sort     ****************"<<endl;  
    cout<<"***************   3   快速排序 quick_sort      ****************"<<endl;  
    cout<<"***************   4   直接插入排序 insert_sort ****************"<<endl;  
    cout<<"***************   5   希尔排序  shell_sort     ****************"<<endl;  
    cout<<"***************   6   折半排序  b_sort         ****************"<<endl;  
    cout<<"***************   7   归并排序  merge_sort     ****************"<<endl;  
    cout<<"***************   8   堆排序    heap_sort      ****************"<<endl;  
    cout<<"***************   9   冒泡排序 bubble_sort1     ****************"<<endl;  
    cout<<"***************   10 退出选择     ****************"<<endl;    
    cout<<"************************************************************"<<endl<<endl;  
 int k;   
cout<<"please input the number of sort algorithm: ";   
cin>>k;   
switch(k)   
{   
case 1 : bubble_sort(array,n);break;   
case 2 : select_sort(array,n);break;  
case 3 : quick_sort(array,0,n-1);break;   
case 4 : insert_sort(array,n);break;   
case 5 : shell_sort(array,n);break;   
case 6 : b_sort(array,n);break;   
case 7 : merge_sort(array,n);break;   
case 8 : heap_sort(array,n);break;     
case 9 : bubble_sort1(array,n);break;  
case 10 : break;   
default : break;   
}   
}  
int main()  
{   
int n;   
cout<<"please input a number of n : ";   
cin>>n;   
int *array=new int[n*sizeof(int)];   
cout<<endl<<"please input a array :"<<endl;   
for(int i=0;i<n;i++)  
 cin>>array[i];  
 cout<<endl<<" before sorted "<<endl;  
 for(int i=0;i<n;i++)  
 cout<<array[i]<<" ";   
cout<<endl<<endl;   
choose_sort(array,n);//进行排序算法的选择   
cout<<endl<<" after sorted "<<endl;  
 for(int i=0;i<n;i++)   
cout<<array[i]<<" ";   
delete [] array;   
array=0;   
return 0;  
}