《程式設計之美》一摞烙餅的排序

題目：盤子中一堆烙餅，雜亂放着。一位有強迫症的顧客看到後，心裡很不舒服，打算把這些餅給從小到大、從上到下放好。他注意到這些烙餅大小不一，心想該如何把它們放好。想了半天，他一手托着盤子，一手抓住最上面的幾塊餅，把它們上下颠倒個個，幾次之後，順序排列好了。他心裡也舒服多了。

假如用程式描述這位強迫症顧客的行為，該如何描述？盡量優化。

想法：

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哈希