C 语言实现各排序算法

面试官：“ 先手写一个快速排序吧！”

最近整理了一些排序算法，并记录下实现过程！作为备忘笔记。主要有：快速排序、堆排序、归并排序、插入排序、冒泡排序、选择排序等。

前言

• 算法是程序的灵魂。无论程序多么的复杂，只要我们能够抓住程序的主要“矛盾”，就能够适时地解决这些问题，而算法就是其主要矛盾。
• 排序算法是算法的基础。我们需要学习算法，就必然需要打好自己学习的基石，排序算法作为最基本易懂的算法，我们不精通它又怎么能驾驭得了其他高级算法呢？
• C 语言：本文选择 C 作为实现语言，主要是本人在看 Linux 下的 C 编程一书，于是就顺便直接在 Linux 系统下开写了！我想 C 语言是每个人都能看得懂的语言，并且其特殊性很少，几乎完全能转化为其他各式语言 ( Java, Php, Python 等 )，因此这也是 C 的好处。

排序算法说明

一、快速排序 / FastSort

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序方法，其核心是分治法。

实现过程：

从数列中选取一个作为 基准数 ( 不妨就选第一个，通常也都是选择第一个 )；然后进行分区，将比它小的数放在它左边，比其大的则放在右边；然后对 左右区间进行相同操作 ( 也就是递归 )，直到各个区间只剩一个数。

void quicksort(int array[],int startIndex,int endIndex){
  if(startIndex<endIndex){
  	 //x作为基准数
    int i=startIndex,j=endIndex,x=array[startIndex];
    //下面进行分区
    while(i<j){
      while(i<j&&array[j]>=x){
        j--;
      }
      if(i<j){
        array[i++]=array[j];
      }
      while(i<j&&array[i]<x){
        i++;
      }
      if(i<j){
        array[j--]=array[i];
      }
      array[i]=x;
    }
    //左右区间进行相同操作
    quicksort(array,startIndex,i-1);
    quicksort(array,i+1,endIndex);
  }
}

二、堆排序 / HeapSort

堆排序是 Robert W．Floyd 和 J．Williams 在 1964 年共同发明的，其核心是堆数据结构的运用。

堆：是一种数据结构，属于树类，它是 一棵完全二叉树 ( 也就是二叉树的儿子要么没有要么一定要有左儿子，不会出现只有右儿子的情况 )，并且通常父亲要大于其两个儿子 ( 也就是大堆 )。

实现过程：首先将数组建成堆数据结构，然后将堆的根结点与最后结点交换，再对前 n-1 个数再进行调整堆，从而根结点又是 n-1 个数中最大的，与最后结点再次交换，如此循环。

//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength){
  int nChild;
  int nTemp;
  for(;2*i+1<nLength;i=nChild){
    //子节点的位置=2*(父节点位置)+1
    nChild=2*i+1;
    //得到子节点中较大的节点
    if(nChild<nLength-1&&array[nChild+1]>array[nChild]){
      ++nChild;
    }
    //如果较大的子节点大于父节点那么把较大的子节点往上移动，替换它的父节点
    if(array[i]<array[nChild]){
      nTemp=array[i];
      array[i]=array[nChild];
      array[nChild]=nTemp;
    }else{
      break;//否则退出循环
    }
  }
}
//堆排序算法
void HeadSort(int array[],int length){
  int i,temp;
  //调整序列的前半部分元素，调整完之后第一个元素是序列的最大元素
  //length/2-1是最后一个非叶节点，（length为下标加1）
  for(i=length/2-1;i>=0;--i){
    HeapAdjust(array,i,length);
  }
  //从最后一个元素开始对序列进行调整，不断缩小调整的范围直到第一个元素
  for(i=length-1;i>0;--i){
    temp=array[0];
    array[0]=array[i];
    array[i]=temp;
    //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
    HeapAdjust(array,0,i);
  }
}

三、归并排序 / MergeSort

归并排序核心也是 分治法。

实现过程：首先是申请变量空间，归并排序是这些算法中空间占用最大的算法，然后循环将数组分为两个子序列，再将两子序列合并为有序段。

归并排序的算法我们通常用递归实现，先把待排序区间 [s,t] 以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t]。

//将两个有序数列合并成一个有序数列
//sourceArr为待合并数列，tempArr为合并后序列，仅仅作为中转操作存储
//startIndex,midIndex,endIndex分别为sourceArr中分为两序列的前中后下标
void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){
  int i=startIndex,j=midIndex+1,k=startIndex;
  //分别从两个序列的起始开始，逐一比较两个序列中元素大小
  while(i!=midIndex+1 && j!=endIndex+1){
    if(sourceArr[i]>sourceArr[j]){
      //较小的存入合并序列
      tempArr[k++]=sourceArr[j++];
    }else{
      //较小的存入合并序列
      tempArr[k++]=sourceArr[i++];
    }
  }
  //将未合并的直接放到合并序列里
  while(i!=midIndex+1){
    tempArr[k++]=sourceArr[i++];
  }
  while(j!=endIndex+1){
    tempArr[k++]=sourceArr[j++];
  }
  //最后将合并序列在放入原始数列中
  for(i=startIndex;i<=endIndex;i++){
    sourceArr[i]=tempArr[i];
  }
}
//sourceArr为原待排序列，tempArr为合并后序列，作为临时存放区
//startIndex为数组开始下标，endIndex为结束下标
void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex){
  int midIndex;
  if(startIndex<endIndex){
    //将原序列二分为两个序列
    midIndex=(startIndex+endIndex)/2;
    //分别对两个序列，再进行二分
    MergeSort(sourceArr,tempArr,startIndex,midIndex);
    MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
    //对每个二分序列进行合并
    Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
  }
}

四、插入排序 / InsertSort

插入排序是将未排序的数插入到已经排好序的数组里，使得新生成的数列也是有序的。

实现过程：将第一个数作为已经排好的序列，然后从后面开始循环插入到第一个数列中，插入的方法是从第一个序列的最后一位开始循环与待插入的数对比，如果比其大则往后移动，直至小于等于其大小或则循环到第一个数为止。

//两层循环，外循环从下标+1处开始到结束
//内层循环，将外层循环中的数与其前面的所有数对比插入。
void insertsort(int array[],int startIndex,int endIndex){
  int i,j,item;
  if(endIndex>startIndex){
    for(j=startIndex+1;j<=endIndex;j++){
      item=array[j];
      i=j-1;
      while(i>=startIndex&&item<array[i]){
        //i>=startIndex为防止i--越界
        array[i+1]=array[i];//将比item大的数依次后移
        i--;
      }
      array[i+1]=item;
    }
  }
}

五、冒泡排序 / BubbleSort

冒泡排序应该是最简单的排序算法了，它的实现过程就是利用两层数组循环，逐一将两个数进行对比，将小数放前面，大数放后面。

//冒泡排序--顺序比较
//array为数组，startIndex为开始下标(>=0),endIndex为结束下标
void bubblesort(int array[],int startIndex,int endIndex){
  int i,j;
  for(i=startIndex;i<endIndex;i++){
    //将最大值放在最后面
    for(j=startIndex;j<endIndex-i;j++){
      if(array[j]>array[j+1]){
        swap(&array[j],&array[j+1]);
      }
    }
  }
}

六、选择排序 / SelectSort

选择排序其实现过程是通过两层循环，每次找出剩余序列中的最小值，最终得到排序好的数组。

//每次选择剩余中的最小值，依次到结束
void selectsort(int array[],int startIndex,int endIndex){
  int i,j,minIndex;
  for(i=startIndex;i<endIndex;i++){
    minIndex=i;
    //选出最小下标，放在最前面
    for(j=i+1;j<=endIndex;j++){
      if(array[minIndex]>array[j]){
        minIndex=j;
      }
    }
    if(minIndex!=i){
      swap(&array[i],&array[minIndex]);
    }
  }
}

总结

项目实现

1. C实现排序项目地址：https://github.com/jiyiren/CSort

2. Android图形化排序地址：https://github.com/jiyiren/JYSort

归并排序和堆排序、快速排序的比较

• 若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
• 若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
• 若从平均情况下的排序速度考虑，应该选择快速排序。

参考资料

• http://www.cnblogs.com/jingmoxukong/p/4308823.html
• http://blog.csdn.net/morewindows/article/details/6684558