C语言折半排序算法（附带完整实现源码）

所谓折半排序，是指选择一个中间值（在程序中使用数组中间值），即 middle，然后把比中间值小的数据放在左边、把比中间值大的数据放在右边（具体的实现是从两边找，找到一对数后进行交换）。接着对两边分别递归进行这样的操作。

折半法又称二分法，对 n 个数排序，只需要排 log(n) 次。

下面以将数字 9、6、15、4、2 按从小到大的顺序排列为例，介绍对这几个数字进行折半法排序，如下图所示。


折半法排序的过程如下：

• 第 1 次排序首先获取数组中间值 15；
• 从左侧取出数组元素与中间值进行比较，也就是取 9 与 15 进行比较，因为 9 比 15 小，所以位置不变；
• 再取 6 与 15 进行比较，因为 6 比 15 小，所以位置依然不变；
• 然后从右侧取出数组元素与中间值进行比较，也就是取 2 与 15 比较，2 比 15 小，2 与 15 互换位置；
• 此时中间值是 2，取 4 与 2 进行比较，2 比 4 小，所以位置不变。这时第 1 次排序就完成了。
• 然后看前 3 个数据（9、6、2），取中间值 6，再取 9 与 6 比较，9 比 6 大，所以交换位置。
• 此时中间值是 9，然后取 2 与 9 比较，2 比 9 小，交换位置；

以此类推，按上面的比较方法继续进行比较，直到将一组数字按从小到大的顺序排列为止。

下面通过实例来介绍如何通过程序使用折半法实现数组元素按从小到大的顺序排列。

【实例】在本实例的代码中，声明了一个整型数组，用于存储用户输入的数字，还定义了一个函数，用于对数组元素进行排序，最后将排好序的数组进行输出。

具体代码如下：

#define _CRT_SECURE_NO_WARNINGS                /*解除vs安全性检测问题*/
#include <stdio.h>                            /*包含头文件*/
/*声明函数*/
void CelerityRun(int left, int right, int array[]);

int main()                                    /*主函数main()*/
{
   int i;                                     /*定义变量*/
   int a[8];
   printf("输入数据：\n");
   for (i = 0; i<8; i++)                      /*输入数据*/
   {
          printf("a[%d]=", i);
          scanf("%d", &a[i]);
   }

   /*从小到大排序*/
   CelerityRun(0, 7, a);
   printf("从小到大排序如下：\n");

   /*输出数组*/
   for (i = 0; i<8; i++)
   {
          printf("%d\t", a[i]);                    /*输出制表符*/
          if (i == 4)                              /*如果是第5个元素*/
              printf("\n");                        /*输出换行符*/
   }
   printf("\n");
   return 0;                                     /*程序结束*/
}

void CelerityRun(int left, int right, int array[])  /*定义函数*/
{
   int i, j;                                     /*定义变量*/
   int middle, iTemp;
   i = left;
   j = right;
   middle = array[(left + right) / 2];           /*求中间值*/
   do
   {
        while ((array[i]<middle) && (i<right))  /*从左找小于中间值的数*/
             i++;
        while ((array[j]>middle) && (j>left))   /*从右找大于中间值的数*/
             j--;
        if (i <= j)                             /*如果找到一对值*/
        {
             iTemp = array[i];                  /*交换这对值*/
             array[i] = array[j];
             array[j] = iTemp;
             i++;
             j--;
          }
   } while (i <= j);                /*如果两边的索引相同，就停止（完成一次）*/
   /*递归左边*/
   if (left<j)
          CelerityRun(left, j, array);
   /*递归右边*/
   if (right>i)
          CelerityRun(i, right, array);
}

运行程序，结果是：

输入数据：
a[0]=6
a[1]=7
a[2]=34
a[3]=14
a[4]=26
a[5]=27
a[6]=43
a[7]=35
从小到大排序如下：
6       7       14      26      27
34      35      43