/* 标题：<<系统设计师>>应试编程实例-[分治法程序设计] 作者：成晓旭 时间：2002年09月18日(21:43:00-22:03:00)    实现“快速排序算法”问题的分而治之算法函数*/#include "stdio.h"#include "stdlib.h" //:============================“快速排序算法”问题的分而治之算法===========================/* 时间：2002年09月18日(21:43:00-22:03:00)    实现“快速排序算法”问题的分而治之算法函数 问题描述:   用分治法的思想实现快速排序算法。 编程思想:   快速排序算法的基本思想本身就是分治法。通过分割，将无序序列分成两部分，  其中前一部分的元素值都小于后一部分的元素值。然后每一部分再各自递归进行上  述过程，直到每一部分的长度为1为止。   首先，在序列的第一个，中间一个，最后一个元素中选取中项，设为p[middle],  并作temp = p[middle](保存中项);   其次，将序列中的第一个元素移到p[middle]的位置上；   然后，设两个指针i,j分别指向将排序序列的第一个元素和最后一个元素；   重复以上两步，直到i = j为止；   最后，将array[i] = temp(将tmep移到array[i])。*/#define MAXN 20 void Carve_up(int array[],int number,int *m){ int i,j,k,middle,temp; i = 0; j = number - 1; k = (i + j) / 2; //在下标i,j,k的数组元素中选取中项 if(array[i] >= array[j] && array[j] >= array[k])  middle = j;  //Array[j]是中项 else if(array[i] >= array[k] && array[k] >= array[j])  middle = k;  //Array[k]是中项 else  middle = i;  //Array[i]是中项 temp = array[middle]; array[middle] = array[i]; while(i != j) {  while(i < j && array[j] >= temp)   j --; //j逐步减小，直到发现一个array[j] < temp为止  if(i < j)  {   array[i] = array[j];   i ++ ;   while(i < j && array[i] <= temp)    i ++ ; //i逐步减小，直到发现一个array[i] > temp为止   if(i < j)   {    array[j] = array[i];    j --;   }  } } array[i] = temp; *m = i; return;}void Quick_Sort(int array[],int number){ int i; if(number > 1) {  Carve_up(array,number,&i);  Quick_Sort(array,i);  Quick_Sort(&array[i + 1],number - i - 1); } return;}void Run_Quick_Sort(){ int i,array[MAXN] = {1,9,3,7,18,2,20,4,16,5,15,6,14,7,13,6,12,8,11,10}; Quick_Sort(array,MAXN); for(i = 0;i < MAXN;i++)  printf("%3d",array[i]);}//:============================“快速排序算法”问题的分而治之算法=========================== int main(int argc, char* argv[]){ Run_Quick_Sort();  printf("\n应用程序运行结束！\n"); return 0;}

评论