《编程之美》一摞烙饼的排序

题目：盘子中一堆烙饼，杂乱放着。一位有强迫症的顾客看到后，心里很不舒服，打算把这些饼给从小到大、从上到下放好。他注意到这些烙饼大小不一，心想该如何把它们放好。想了半天，他一手托着盘子，一手抓住最上面的几块饼，把它们上下颠倒个个，几次之后，顺序排列好了。他心里也舒服多了。

假如用程序描述这位强迫症顾客的行为，该如何描述？尽量优化。

想法：

1、先找大的：由于一次要翻转最上面的几块饼，并且是颠倒个个，因此每次颠倒之前，找到当前最大的饼，颠倒，把最大的饼放到最上面，再颠倒，把这个当前最大的饼放到合适的位置，依次递推，最后从小到大、从上到下排好顺序。

2、先找小的：每次颠倒前，找到当前最小的，颠倒，把当前最小的饼放到最上面，然后颠倒，把当前最小的放到比之更小的饼的上面，然后从所有最小的饼所放的位置颠倒，即可。

在任何一种想法实现过程中，每次排序之前，查看当前位置的饼是否符合要求，如果符合要求就不进行排序，否则进行排序，这样可以减少排序次数。

每次颠倒次数，想法1的比想法2的要少。

代码：

想法1：

#include <stdio.h>
#define MAXSIZE 10

void print(int bing[]);
void findbigger(int bing[]);
void sort_size(const int bing[], int bing_size[]);
int find_bigger_pos(const int size, const int bing[]);

/*  打印当前饼的大小*/
void print(int bing[])
{
    int index = 0;
    printf("(bing size)： ");
    while(index < MAXSIZE)
    {
        printf("%d ",bing[index]);
        index ++;
    }
    printf("\n");
}

/*  想法1：先找大的*/
void findbigger(int bing[])
{
    int bing_size[MAXSIZE];//饼的排序后的大小（从大到小）
    int tmp_bigger_pos = 0;//当前最大size的饼的位置
    int tmp_index = MAXSIZE - 1;//指向排序后的饼的临时索引值
    int bing_a_set[MAXSIZE];
    int bing_b_set[MAXSIZE];
    int a_set_index = 0;
    int b_set_index = 0;
    int number = 0;//排序次数

    sort_size(bing, bing_size);

    while(tmp_index >= 0)
    {
        //首先查看当前的饼的位置是否符合要求
        if(bing[tmp_index] == bing_size[tmp_index])//符合要求，查看下一个
        {
            ;
        }
        else//不符合要求，调整
        {
            tmp_bigger_pos = find_bigger_pos(bing_size[tmp_index], bing);//查找到当前最大的饼的位置，正常情况下，该位置小于调整后的位置

            a_set_index = 0;
            //从当前位置到位置0处，划分为一部分a_set，另存储，从调整后的位置到当前位置+1，划分为另一部分b_set。a_set部分按照当前顺序移动到调整后位置，b_set部分逆序排列到从位置0处
            while(a_set_index <= tmp_bigger_pos)
            {
                bing_a_set[a_set_index] = bing[a_set_index];
                a_set_index ++;
            }

            //b_set部分逆序从位置0存储
            b_set_index=0;
            while(b_set_index +a_set_index <=tmp_index)
            {
                bing_b_set[b_set_index] = bing[tmp_index - b_set_index];
                b_set_index++;
            }

            //b_set逆序从位置0存储
            b_set_index = 0;
            while(b_set_index < tmp_index - tmp_bigger_pos)
            {
                bing[b_set_index] = bing_b_set[b_set_index];
                b_set_index++;
            }

            //a_set按照当前顺序移动到调整后的位置
            a_set_index = 0;
            while(a_set_index <= tmp_bigger_pos)
            {
                bing[a_set_index +b_set_index] = bing_a_set[a_set_index];
                a_set_index++;
            }
            if(tmp_bigger_pos == 0)
                number++;
            else
                number +=2;
            printf("%d ", number);
            print(bing);
        }

        tmp_index --;
    }

    printf("Total %d times to sort OK.\n",number);
}

/*  对饼的大小进行排序(从小到大)，方便找饼及判断是否找完
 *  bing[]：原来饼的大小
 *  bing_size[]：排序后饼的大小
 *  使用冒泡法
 */
void sort_size(const int bing[], int bing_size[])
{
    int out_index = 0;//外部循环索引
    int in_index = 0;//内部循环索引
    int tmp_value = 0;//临时变量

    for(in_index = 0;in_index < MAXSIZE;in_index++)
    {
        bing_size[in_index] = bing[in_index];
    }

    while(out_index < (MAXSIZE - 1))
    {
        in_index = MAXSIZE - 1;
        while(in_index > out_index)
        {
            if(bing_size[in_index - 1] > bing_size[in_index])
            {
                tmp_value = bing_size[in_index];
                bing_size[in_index] = bing_size[in_index-1];
                bing_size[in_index-1] = tmp_value;
            }
            in_index --;
        }
        out_index ++;
    }
}

/*
 * 根据大小查找原有饼中的位置
 */
int find_bigger_pos(const int size, const int bing[])
{
    int tmp_pos = 0;
    while(tmp_pos < MAXSIZE)
    {
        if(size == bing[tmp_pos])
            break;
        tmp_pos++;
    }
    return tmp_pos;
}

/*  主程序*/
int main()
{
    int bing[10] = {3,5,4,8,9,10,1,6,2,7};

    /*  当前饼的大小*/
    print(bing);

    /*  想法1：先找大的*/
    findbigger(bing);

    return 0;
}

想法2：

#include <stdio.h>
#define MAXSIZE 10

void print(int bing[]);
void findsmaller(int bing[]);
void sort_size(const int bing[], int bing_size[]);
int find_smaller_pos(const int size, const int bing[]);

/*  打印当前饼的大小*/
void print(int bing[])
{
    int index = 0;
    printf("(bing size)： ");
    while(index < MAXSIZE)
    {
        printf("%d ",bing[index]);
        index ++;
    }
    printf("\n");
}

/*  想法2：先找小的*/
void findsmaller(int bing[])
{
    int bing_size[MAXSIZE];//饼的排序后的大小（从大到小）
    int tmp_smaller_pos = 0;//当前最小size的饼的位置
    int tmp_index = 0;//指向排序后的饼的临时索引值
    int bing_a_set[MAXSIZE];
    int a_set_index = 0;
    int number = 0;//排序次数

    sort_size(bing, bing_size);

    while(tmp_index < MAXSIZE)
    {
        //首先查看当前的饼的位置是否符合要求
        if(bing[tmp_index] == bing_size[tmp_index])//符合要求，查看下一个
        {
            ;
        }
        else//不符合要求，调整
        {
            tmp_smaller_pos = find_smaller_pos(bing_size[tmp_index], bing);//查找到当前最小的饼的位置，一般情况下，该位置大于调整后的位置

            a_set_index = tmp_index;
            //从调整的位置到当前最小的饼的位置，需要逆序存储，然后从调整位置到当前位置存放到原来的饼处
            while(a_set_index <= tmp_smaller_pos)
            {
                bing_a_set[tmp_smaller_pos - a_set_index] = bing[a_set_index];
                a_set_index ++;
            }


            //a_set逆序从位置0存储
            a_set_index = 0;
            while(a_set_index < tmp_smaller_pos - tmp_index + 1)
            {
                bing[a_set_index + tmp_index] = bing_a_set[a_set_index];
                a_set_index++;
            }
            if(tmp_index == 0)
            {
                number ++;
            }
            else
                number += 3;
            printf("%d ", number);
            print(bing);
        }

        tmp_index ++;
    }

    printf("Total %d times to sort OK.\n",number);
}

/*  对饼的大小进行排序(从小到大)，方便找饼及判断是否找完
 *  bing[]：原来饼的大小
 *  bing_size[]：排序后饼的大小
 *  使用选择排序法
 */
void sort_size(const int bing[], int bing_size[])
{
    int index;
    int tmp_index;
    int small_index;
    int small_value;

    index = 0;
    while(index < MAXSIZE)
    {
        bing_size[index] = bing[index];
        index++;
    }

    index=0;
    while(index<MAXSIZE)
    {
        small_value = bing_size[index];
        small_index = index;
        tmp_index = index+1;
        while(tmp_index < MAXSIZE)
        {
            if(small_value > bing_size[tmp_index])
            {
                small_value = bing_size[tmp_index];
                small_index = tmp_index;
            }
            tmp_index++;
        }

        if(small_index != index)
        {
            bing_size[small_index] = bing_size[index];
            bing_size[index] = small_value;
        }
        index++;
    }
}

/*
 * 根据大小查找原有饼中的位置
 */
int find_smaller_pos(const int size, const int bing[])
{
    int tmp_pos = 0;
    while(tmp_pos < MAXSIZE)
    {
        if(size == bing[tmp_pos])
            break;
        tmp_pos++;
    }
    return tmp_pos;
}

/*  主程序*/
int main()
{
    int bing[10] = {3,5,4,8,9,10,1,6,2,7};

    /*  当前饼的大小*/
    print(bing);

    /*  想法2：先找小的*/
    findsmaller(bing);

    return 0;
}

《编程之美》一摞烙饼的排序

继续阅读

浮点数计算精度控制

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

QR码编码原理三（日本汉字和中文编码）

hdu7108哈希