现在的位置: 首页 > 综合 > 正文

“快速排序算法”问题的分而治之算法

2013年06月20日 ⁄ 综合 ⁄ 共 2197字 ⁄ 字号 评论关闭
/*
    标题:>应试编程实例-[分治法程序设计]
    作者:成晓旭
    时间: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] 
        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;
    
*= 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(
" 应用程序运行结束! ");
    
return 0;
}


抱歉!评论已关闭.