排序算法C Part01

1、冒泡排序

//冒泡排序BubbleSort
//每次扫描，比较和交换相邻元素，保证一次扫描后，最大元素在最后一个
//每次扫描后，扫描队列长度减一
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void BubbleSort(int Q[], int N)
{
  int i;
  int swap=1;
  int Temp;
  
  while(swap>0)
    {
      swap=0;
      for(i=1;i<N;i++)
	{
	  if(Q[i-1]>Q[i])
	    {
	      swap++;
	      Temp=Q[i-1];
	      Q[i-1]=Q[i];
	      Q[i]=Temp;
	    }
	}
    }
}

2、选择排序

//选择排序SelectionSort
//从头扫描到尾，每次将最小元素放到第一个
//每次扫描后，队列长度减一
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void SelectionSort(int Q[], int N)
{
  int i,j,k;
  int Temp;
  for(i=0;i<N;i++)
    {
      k=i;
      for(j=i+1;j<N;j++)
	{
	  if(Q[j]<Q[i])k=j;
	}  

      Temp=Q[k];
      Q[k]=Q[i];
      Q[i]=Temp;
    }
}

3、插入排序

//插入排序InsertionSort
//起始队列长度为1，每次队列长度加1
//通过元素移动，将队列调整为有序状态
//时间复杂度：O(N^2)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void InsertionSort(int Q[], int N)
{
  int i,j;
  int Temp;
  for(i=1;i<N;i++)
    {
      Temp = Q[i];
      for(j=i;j>0 && Q[j-1]>Temp;j--)
	{
	  Q[j]=Q[j-1];
	}

      Q[j]=Temp;
    }
}

4、希尔排序

//希尔排序ShellSort
//指定一个步长，将需要排序的数字，按序号%步长分组
//对每组进行插入排序，然后减小步长，再次分组，排序直到步长为1结束
//时间复杂度：O(n^2)
//空间复杂度：O(n)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void ShellSort(int Q[], int N)
{
  int i,j;
  int Temp;
  int Step;

  for(Step=N/2;Step>0;Step=Step/2)
    {
      for(i=Step;i<N;i++)
	{
	  Temp = Q[i];
	  for(j=i;j>=Step && Q[j-Step]>Temp;j=j-Step)
	    {
	      Q[j]=Q[j-Step];
	    }
	  Q[j]=Temp;
	}
      //dumpArray(Q,N);
    }
}

5、归并排序

//归并排序MergeSort
//二路归并首先将归并长度定为2，在归并集内进行排序
//然后归并长度×2，将有序集合进行归并
//时间复杂度：O(NlogN)
//空间复杂度：O(N)
//稳定性：稳定
//输入：要排序的数组，数组长度
//输出：void，Q[]将处于排序状态
void Merge(int Q[],int TempArray[], int left, int mid, int right)
{
  int i=left,j=mid,k=left;

  while(i<mid && j<=right)
    {
      if(Q[i]>Q[j])
	{
	  TempArray[k++]=Q[j++];
	}
      else
	{
	  TempArray[k++]=Q[i++];
	}
    }

  while(i<mid)
    {
	  TempArray[k++]=Q[i++];
    }

  while(j<=right)
    {
      	  TempArray[k++]=Q[j++];
    }

  for(k=left;k<=right;k++)
    {
      Q[k]=TempArray[k];
    }

}

void MSort(int Q[],int TempArray[], int left, int right)
{
  int center;

  if(left<right)
    {
      center=(left+right)/2;
      MSort(Q,TempArray,left,center);
      MSort(Q,TempArray,center+1,right);
      Merge(Q,TempArray,left,center+1,right);
    }
}

void MergeSort(int Q[], int N)
{
  int *TempArray = malloc(N*sizeof(int));

  if(TempArray!=NULL)
    {
      MSort(Q,TempArray,0,N-1);
    }
  else
    {
      //Todo: deal with not enough memory
      //RaiseError("MergeSort: not enough memory");
    }
}