数据结构&算法实践—奇偶排序

533 查看

排序>>交换排序>>奇偶排序

List:

  1. start

基本概念:

维基百科http://zh.wikipedia.org/wiki/%E5%A5%87%E5%81%B6%E6%8E%92%E5%BA%8F

伪代码:

奇偶排序

类似于冒泡排序,冒泡排序并行化的版本()

简单但效率不高

每一轮存在两次排序:奇数排序(下标奇数与其邻居比较&交换),偶数排序(下标偶数与其邻居比较交换)

直到不存在数据交换

示例:

第一轮 偶数排序

第一轮 奇数排序

第二轮 偶数排序

第二轮 奇数排序

第三轮 不存在数据交换

  1. start

    :::python
    def oddeven_sort(l):
    odd_range = range(0,len(l)-1,2)
    even_range = range(1,len(l)-1,2)
    sign = 1
    while sign:
    sign = 0
    for i in odd_range:
    if l[i] > l[i+1]:
    l[i], l[i+1] = l[i+1],l[i]
    sign = 1
    for j in even_range:
    if l[j] > l[j+1]:
    l[j], l[j+1] = l[j+1], l[j]
    sign = 1
    print l

  2. start

A.奇偶排序概念,过程描述?

B. 时间复杂度?空间复杂度?是否是稳定排序?

  1. start

后续扩展——Batcher奇偶归并排序(后面实现)