求排序算法思路，使得 array[0]<array[1]>array[2]<array[3]...

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2555 天前的主题，其中的信息可能已经有所发展或是发生改变。

python，如输入[8,8,4,6,2,7],输出[4,8,6,7,2,8]

array

Python

排序

算法

20 条回复 • 2017-11-29 10:47:49 +08:00

blueset

2017-11-27 21:18:55 +08:00 via Android

排序，然后左右交替取数？

8 8 4 6 2 7 → 2 4 6 7 8 8

2 4 6 (7 8 8)
- 8 8 7 (6 4 2)

2 <= 8 >= 4 <= 8 >= 6 <= 7

jzy

2017-11-27 21:19:00 +08:00 via iPhone

从小到大排序，前面一半放奇数位，后面一半放偶数位。如果奇数位和偶数位首位相等，应该是无解了

momocraft

2017-11-27 21:20:44 +08:00

先排成升序然后反复横跳地取: arr[3] --(向左)-- arr[2] --(向右)-- arr[4] --(向左)--

lhx2008

2017-11-27 21:21:38 +08:00 via Android

答案不唯一呀，还要随机分布么

ballshapesdsd

2017-11-27 21:29:00 +08:00

leetcode 上有这道题。。一模一样的

liemehoc

2017-11-27 21:30:56 +08:00

@blueset
@jzy
@momocraft
我第一反应也是这个，不知道有没有更优雅的解法

@lhx2008 是的，能不能算出所有有效解

liemehoc

2017-11-27 21:32:09 +08:00

@ballshapesdsd 名字叫啥

ballshapesdsd

2017-11-27 21:38:01 +08:00

@liemehoc 噗，找了半天
https://leetcode.com/problems/wiggle-subsequence/description/
o(n)时间复杂度的解法

liemehoc

2017-11-27 21:48:09 +08:00

@ballshapesdsd 学习了，解法有意思

SlipStupig

2017-11-27 23:03:15 +08:00

我今天也遇到类似的问题：
python:
list_a = ['m', 'z', 'k', 'i']
dict_a = {'z': 2, ‘ k ’: 3, 'm':'a', 'i': -1}

dict_a 有什么办法能优雅的按照 list_a 中的 key 顺序排列呢？

jmc891205

2017-11-27 23:22:34 +08:00

@SlipStupig
[dict_a[k] for k in list_a]这样？

dangoron

2017-11-27 23:28:18 +08:00 via Android

shell sort 做到一半的感觉。。

panda0

2017-11-28 00:28:46 +08:00 via iPhone

@jmc891205 这样是个 list 了吧

nondanee

2017-11-28 01:53:40 +08:00 via Android

@SlipStupig dict 就是无序的呀，用 collections.OrderedDict 哇

LukeXuan

2017-11-28 03:07:00 +08:00

找到中位数(O(n))，然后比中位数小的放在偶数位，大的放在奇数位。

vegito2002

2017-11-28 03:33:32 +08:00

Wiggle Sort, Google 原题, LC 上面有

SlipStupig

2017-11-28 07:24:14 +08:00

@jmc891205 哈哈，好像是这样，但是如果是两个 list 呢？

dangyuluo

2017-11-28 08:36:35 +08:00

我觉得答案不唯一吧。

leetao94

2017-11-28 08:41:54 +08:00

leetcode 的中类似的一题,http://www.leetao94.cn/2017/08/24/Wiggle%20Sort%20II/

liemehoc

2017-11-29 10:47:49 +08:00

@vegito2002
@dangyuluo
@leetao94
扩展一下问题，如果要求所有满足规则的解呢