选择类排序

#include<stdio.h>
/*
*选择类排序，每天一道算法题 
*按照从小到大的顺序进行排序 
* 
*/
//遍历序列
void traverseArray(int *p,int length)
{
   int i=0;
   for(;i<length;i++)
   {
     printf("%d\n",p[i]);
   } 

}
//简单选择类排序 
void selectSort(int *p,int length)
{
  int i,j,temp,index;
  for(i=0;i<length;i++)
  {
    index=i;
    for(j=i;j<length;j++)
    {
        if(p[index]>p[j])
           index=j; 
    }
    temp=p[i];
    p[i]=p[index];
    p[index]=temp;
  }
} 
void heapAdjest(int *p,int s,int length)
{
  int i;
  int temp=p[s];
  for(i=2*s+1;i<=length;i*=2)
  {
     if(i<length&&p[i]<p[i+1]) ++i;  
     if(!temp>p[i]) break;
     
       p[s]=p[i];
       s=i;       
  } 
  p[s]=temp; 
}
void heapSort(int *p,int length)
{
 int i;
 int temp;
 //建立大顶堆
 for(i=length/2;i>0;--i)                       
  heapAdjest(p,i,length);for(i=length-1;i>-1;i--)
 {
   temp=p[i];
   p[i]=p[0];
   p[0]=temp;
   heapAdjest(p,0,i-1);
   traverseArray(p,length);
   printf("\n");
 }
 

}
int main()
{
  int a[]={9,2,1,4,5,7,3,8,6}; 
  
 // selectSort(a,sizeof(a)/sizeof(int));
  heapSort(a,sizeof(a)/sizeof(int));
  traverseArray(a,sizeof(a)/sizeof(int));
  
  system("pause");
  return 0;
}

 简单选择排序算法采用首先查找到最大值，然后将其放到最后。其算法的时间复杂度为O(n²).

 堆排序的思想是首先建立堆，建立堆时从序列的一半递减开始创建，然后再进行调整。堆排序只要进行筛选调整，必然需要调整，每次调整的次数小于其深度2k（其中k=logn）(最多比较两个分支)，因此不管原来数据为何种类型，其算法的时间复杂度均为O(nlogn).