几种排序算法

#include

//冒泡排序
void bubbleSort(int* s,int n)
{
 for(int i=1;i {
  for(int j=0;j  {
   if(s[j+1]   {
    int temp = s[j+1];
    s[j+1]=s[j];
    s[j]=temp;
   }
  }
 }
}
//改进后的冒泡排序
void bubbleSort_2(int *s,int n)
{
 bool exchange=true;
 int i=1;
 while(exchange)
 {
  exchange=false;
  for(int j=0;j  {
   if(s[j+1]   {
    int temp = s[j+1];
    s[j+1]=s[j];
    s[j]=temp;
    exchange=true;
   }
  }
  i++;
 }

}

//直接插入排序
void directInserSort(int *s,int n)
{
 for(int i=1;i {
  int tm = s[i];//这里注意要要用一个变量把值暂存起来，要不然值会被冲掉
  for(int j=i-1;j>=0&&s[j]>tm;j--)
  {
  
    int temp = s[j+1];
    s[j+1]=s[j];
    s[j]=temp;
   
  }
  s[j+1]=tm;
 }

}

//折半插入排序
void halfInsertSort(int *s,int n)
{
 for(int i=1;i {
  int low=0;
  int high=i-1;

  int tm =s[i];
  while(low<=high)//注意等号
  {
   int mid = (high+low)/2;
   if(tm>s[mid])
   {
    low=mid+1;
   }
   else
   {
    high=mid-1;
   }
  }
  for(int j=i-1;j>=high+1;j--)
  {
    int temp = s[j+1];
    s[j+1]=s[j];
    s[j]=temp;
  }
  s[high+1]=tm;
 
 }

}

//希尔排序
void shellSort(int *s,int n)
{

 for(int d=n/2;d>0;d=d/2)
 {
  for(int i=d;i  {
   int tm=s[i];
   for(int j=i-d;j>=0&&s[j]>tm;j=j-d)
   {
    int temp = s[j+d];
    s[j+d]=s[j];
    s[j]=temp;
   }
   s[j+d]=tm;
  }
 
 } 
}

//快速排序一次分割
int partion(int *s,int low,int high)
{
  int tm=s[low];
  while(low  {
  while(low=tm)
  {
   --high;
  }

  if(low  {
   s[low++]=s[high];
  }
  while(low  {
   ++low;
  }

  if(low  {
   s[high--]=s[low];
  }
  }
  s[low]=tm;

  return low;
}
//快速排序
void quikSort(int *s,int low,int high)
{
 if(low {
  int pos=partion(s,low,high);
  quikSort(s,low,pos-1);
  quikSort(s,pos+1,high);

 }
 
}
//选择排序
void selectSort(int *s,int n)
{
 for(int i=0;i {
  int k=i;
  for(int j=i+1;j  {
   if(s[j]   {
    k=j;
   }  
  }

  if(k!=i)
  {
    int temp = s[k];
    s[k]=s[i];
    s[i]=temp;
  }
 }
}
///堆排序
void shift(int a[] , int i , int m)
{
int k , t;

    t = a[i]; k = 2 * i +1;
    while (k < m)
    {
        if ((k < m - 1) && (a[k] < a[k+1])) k ++;
        if (t < a[k]) {a[i] = a[k]; i = k; k = 2 * i + 1;}
        else break;
 }
    a[i] = t;
}

void heap(int a[] , int n)  //a 为排序数组，n为数组大小（编号0-n-1）
{
int i , k;

 for (i = n/2-1; i >= 0; i --) shift(a , i , n);
 
 for (i = n-1; i >= 1; i --)
    {
  k = a[0]; a[0] = a[i]; a[i] = k;
  shift(a , 0 , i);
    }

}