介绍

奇偶排序，或奇偶换位排序，或砖排序，是一种相对简单的排序算法，最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。

该算法中，通过比较数组中相邻的（奇 - 偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶 - 奇）位置数字对。如此交替进行下去。

复杂度

• 最坏时间复杂度$\Theta (n^{2})$
• 最优时间复杂度$O(n)$

实现

JavaScript

/*
  odd–even sort or odd–even transposition sort
  is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections.
  It is a comparison sort related to bubble sort, with which it shares many characteristics.
   for more information : https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort
*/

// Helper function to swap array items
swap (arr, i, j) {
  const tmp = arr[i]
  arr[i] = arr[j]
  arr[j] = tmp
}

function oddEvenSort (arr) {
  let sorted = false
  while (!sorted) {
    sorted = true
    for (let i = 1; i < arr.length - 1; i += 2) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1)
        sorted = false
      }
    }
    for (let i = 0; i < arr.length - 1; i += 2) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1)
        sorted = false
      }
    }
  }
  return arr
}

参考

• 奇偶排序 - 维基百科，自由的百科全书 (opens new window)