烧饼问题

随便翻了翻《编程之美》，看到了一个算法描述，也就是以前听说过的翻饼问题，描述如下：服务员一只手托着盘

子，另外一只手也没闲着，他想用另外一直手翻转这饼，最终使得饼按照大小顺序排列，小的在上面，大的在下面

，请设计算法实现：

一开始我想都没想，唉，最简单的方法不就是冒泡排序么。后来经过别人提醒，题目有要求，意思就是不能从中间

抽取，所以，冒泡根本不适用。额，尴尬了。

然后就想着想着，还是用代码写出来再说吧，好了。代码如下：

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年07月28日 星期三 19时47分36秒
 * File Name: sort5.c
 * Description:
 * 这个文章解决的一个算法问题，问题描述如下：服务员端了一碟烧饼，
 * 大小不一，先只能通过另一只手来翻转，使其按大小顺序排序。其中不能抽出任何一张饼
 * 只能对其进行翻转。
 *
 */

#include <stdio.h>
#include <stdlib.h>
/**
 *将一个数组逆置
 * */
void reversal(int r[],int start,int end)
{
    int i,j;
    int tmp;
    for(i = start,j = end;i-1 != j && j+1 != i-1;i++,j--){
        tmp = r[i];
        r[i] = r[j];
        r[j] = tmp;
    }
}

void sort(int r[],int length)
{
    int i,tmp = r[0];
    int maxIndex = 0;
    int tmplength = length;

    for(i = 0;i < tmplength;i++){

        if(r[i] >= tmp){//记录当前需要排序的最大下标

            maxIndex = i;
            tmp = r[i];
        }

        if(i+1 == tmplength){//除了排好序的，对剩余的进行最后处理

            reversal(r,0,maxIndex);
            reversal(r,0,tmplength-1);
            //下面是初始化需要继续排序的剩余的元素

            tmp = 0;
            maxIndex = 0;
            i = -1; //这里为什么要令i=-1呢？因为，if执行完成后i++一次，之前忽略了这点，够折腾的。

            tmplength--;
        }
    }

}

int main(int argc, char *argv[])
{
    
    int i;
    int arr[] = {2,5,7,4,3,6,9,10,22,14};
    int length = sizeof(arr)/sizeof(arr[0]);
    for(i = 0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    //reversal(arr,0,0);

    sort(arr,length);

    for(i = 0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}

这里，我是用一个数组模拟这些饼，最终实现从小到大排序就行了。算法大致描述如下，首先从这么多饼中

找到最大的，这很容易办到吧，然后将最大的饼一直到最上面的整体翻转，先让最大饼到最顶端，然后整体再

翻转，这样，最大饼到了最底下了。

接着继续，将剩余的上面的饼不断的运用上面的算法，次大的，次次大的饼不断的被弄到底下，直到最后肯定

就将所有的排好了。

恩，其实，效率问题是这个算法的最大缺陷，有时间研究研究。今天就先说道这。