首页 > 剑指offer > 烙饼排序
2014
08-14

烙饼排序

问题

给一个为排序的数组,你只能再改对该数组做如下操作:flip(arr, i): 将数组arr[0...i]进行逆置。如何对该数组进行排序?

这个问题在编程之美一书也有提及:

星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:“我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢?”

你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢?

关于这个问题的最优化解法是比较困难的,大家可以参考书上的解法。

这里只给出直接的解法。算法思想类似选择排序,每次找到一个最大的元素,对其进行两次 flip操作,可将最大的放在最后面,让后缩小数组的范围。因此最大需要 2*(n-1)次flip操作。

可以通过下面的视频理解这个操作过程:

C++代码实现如下:

#include <stdlib.h>
#include <stdio.h>

/* 逆置数组 arr[0..i] */
void flip(int arr[], int i)
{
    int temp, start = 0;
    while (start < i)
    {
        temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        start++;
        i--;
    }
}

/* 找出 arr[0..n-1] 内最大的元素的下标 */
int findMax(int arr[], int n)
{
   int mi, i;
   for (mi = 0, i = 0; i < n; ++i)
       if (arr[i] > arr[mi])
              mi = i;
   return mi;
}

int pancakeSort(int *arr, int n)
{
    // 每次翻转可以定位一个做大的元素
    for (int curr_size = n; curr_size > 1; --curr_size)
    {
        // 在 arr[0..curr_size-1] 找到最大的元素
        int mi = findMax(arr, curr_size);

        //记性两次flip操作,将最大的元素翻转到最后
        if (mi != curr_size-1)
        {
            flip(arr, mi);
            flip(arr, curr_size-1);
        }
    }
}

/* 打印数组 */
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
}

int main()
{
    int arr[] = {23, 10, 20, 11, 12, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    pancakeSort(arr, n);

    puts("Sorted Array ");
    printArray(arr, n);

    return 0;
}

参考:http://www.geeksforgeeks.org/pancake-sorting/


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.