程序员考试涉及的排序算法

今年的程序员就快开考咯.总结下几个常用的排序方法.都是通过自己的理解来写的代码.有些地方可能不那么精练,但我想精练的代码并不一定适合学习算法....(小鸟的理解).

1. #include "stdio.h" 
   /*
   1直接插入排序
   2冒泡排序
   3选择排序
   4希尔排序
   5快速排序
   6堆排序
   7归并排序
   */
   void Insert_Sort(int data[],int n)
   {
       int i,j,temp;
       for(i=1;i<n;i++)//从数组的第二个元素开始排序 
       {
           temp=data[i];//保存当前要排序的元素 
           for(j=i-1;temp<data[j]&&j>-1;j--)//向后检索，表达式temp<data[j]升序,temp>data[j]降序.j>-1避免数组的第一个元素不参与排序 
               data[j+1]=data[j];//前移数组元素 
           data[j+1]=temp;//将被排序的数组元素放到正确位置 
       }
   
   }
   
   void Bubble_Sort(int data[],int n)
   {
       int temp,i,j;
       for(i=0;i<n-1;i++)
       {
       
           for(j=i+1;j<n;j++)
           {
               if(data[i]>data[j])//保证数组按升序排列,要降序排列的话data[i]<data[j] 
               {
                   temp=data[j];
                   data[j]=data[i];
                   data[i]=temp;
               }
           }
       }
   
   }
   
   void Select_Sort(int data[],int n)
   {
       int i,j,k,temp;
       for(i=0;i<n-1;i++)
       {
           k=i;
           for(j=i+1;j<n;j++)
           {
               if(data[k]>data[j])//这里是按升序排列的，要降序排列的话改小于号 
               {
                   k=j;
               }
           }
           if(k!=i)
           {
               temp=data[i];
               data[i]=data[k];
               data[k]=temp;
           }
       }
   
   
   }
   
   void Shell_Sort(int data[],int n)
   {
       int space[3]={5,2,1},k,i=0,temp,j;//对排序的分组数组space[]赋值 
       while(space[i]>0){//按space数组中的元素来分割待排序的数组 
           //k=space[i]; 
           for(k=space[i];k<n;++k)//分组 
           {
               if(data[k-space[i]]<data[k])//比较，这里改变符号和下面的代码改变符号，可以改变算法的排序方式 
               {
                   temp=data[k];
                   for(j=k-space[i];j>=0&&temp>data[j];j-=space[i])//移动元素.......temp>data[j]也虚改变符号 
                       data[j+space[i]]=data[j];
                   data[j+space[i]]=temp;
               }
           }
           i++;
       
       }
   
   
   
   
   }
   
   void Quick_Sort(int data[],int low,int high)
   {
       int temp,i,j;
       if(low<high){//递归的返回条件 
               i=low;
               j=high;
               temp=data[low];//取数组的第一个元素作排序标准 
           while(i<j)//边界控制，i不能大于等于j（大于等于说明已经对所有数据遍历了一次） 
               {
                   while(i<j&&data[j]>=temp)
                       j--;
                   if(i<j)
                       data[i++]=data[j];
                   while(i<j&&data[i]<=temp)
                       i++;
                   if(i<j)
                       data[j--]=data[i];
   
   
               }
           data[i]=temp;//当退出上面的那个while循环时，此时的i和j应该是相等的 
           Quick_Sort(data,low,i-1);//递归 
           Quick_Sort(data,i+1,high);
       }
   
   
   }
   
   /*
   n,m分别为数组data,data2的上标，这里将数组data，data2归并递增排序，
   将结果保存到des-data中。所有参与排序的数组下标定为0
   */
   void Merge_Sort(int data[],int data2[],int des_data[],int n,int m) 
   {
       int i,j,k;//i,j,k分别为data,data2,des_data的下标 
       i=j=k=0;
       while(i<n&&j<m){//参与归并的数组是否已经都遍历完毕 
           if(data[i]>data2[j])
           {
               des_data[k++]=data2[j++];
           }
           else if(data[i]<data2[j])
           {
               des_data[k++]=data[i++];
           }
           else
           {
               des_data[k++]=data[i++];
               des_data[k++]=data2[j++];
           }
       }
       if(i<n)//将还未遍历完的数组的所有数据复制到des_data数组中 
           while(i<n)
               des_data[k++]=data[i++];
       if(j<m)
           while(j<m)
               des_data[k++]=data2[j++];
   
   
   }
   /*
       调整堆元素，大堆
   */
   void Heap_Adjust(int data[],int n,int suffix)
   {
       int temp;
       int child;
       child=suffix*2;
       temp=data[suffix];
       /*调整逻辑：先判断要调整节点的子节点中谁的值最大，
       然后与该节点比较，如果该节点的值均大于其子节点的值
       ，退出调整，否则调值大者到该节点位置，
       然后从相应子节点位置继续调整，直至没有子节点为止。
       */
       while(child<=n)
       {
           if(child+1<n)//判断是否有右节点 
           {
               if(data[child]<data[child+1])
               {
                   child++;
               }
               if(temp>data[child])
                   break;
               else
               {
                   data[child/2]=data[child];
                   child=child*2;
               }
           }
           else
           {
               if(temp>data[child])
                   break;
               else
               {
                   data[child/2]=data[child];
                   child=child*2;
               }
           }
   
       }
           data[child/2]=temp;
   }
   /*
   void Heap_Adjust2(int data[],int n,int suffix)
   {
       int temp,child;
       temp=data[suffix];
       child=suffix*2;
       while(child<=n)
       {
           if(child<n)
               if(data[child]<data[child+1])
                   child++;
           if(temp>data[child])
               break;
           else
           {
               data[child/2]=data[child];
               child*=2;
           }
       }
           data[child/2]=temp;
   }
   */
   /*
       构建堆结构
   */
   void Heap_Build(int data[],int n)
   {
       int i;
       for(i=n/2;i>0;i--)//从下向上构建，这样可以遍历所有元素 
           Heap_Adjust(data,n,i);
       
   
   }
   void Heap_Sort(int data[],int n)
   {
       int i,temp;
       Heap_Build(data,n);
       for(i=n-1;i>=1;i--)//调整首元素和尾元素 
       {
           data[0]=data[1];
           data[1]=data[i];
           data[i]=data[0];
           Heap_Adjust2(data,i,1);
       }
   }