如何使用最少的写入次数对数组进行排序？

Question

我的朋友在他的采访中被问到一个问题:

面试官给了他一系列未分类的数字并请他排序.限制是应该最小化写入次数,而对读取次数没有限制.

Answer 1

选择排序不是正确的算法. 选择排序将交换值,每个选择最多两次写入,每次最多提供2n次写入.

一种比选择排序好两倍的算法是"循环"排序,它不会交换.循环排序将为每种排序提供最多n次写入.写入次数绝对最小化.它只会将一个数字写入其最终目的地,并且只有当它不存在时才会写入.

它基于这样的想法:所有排列都是循环的乘积,您可以简单地循环每个循环并将每个元素写入适当的位置一次.

import java.util.Random;
import java.util.Collections;
import java.util.Arrays;

public class CycleSort {
  public static final <T extends Comparable<T>> int cycleSort(final T[] array) {
    int writes = 0;

    // Loop through the array to find cycles to rotate.
    for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) {
      T item = array[cycleStart];

      // Find where to put the item.
      int pos = cycleStart;
      for (int i = cycleStart + 1; i < array.length; i++)
        if (array[i].compareTo(item) < 0) pos++;

      // If the item is already there, this is not a cycle.
      if (pos == cycleStart) continue;

      // Otherwise, put the item there or right after any duplicates.
      while (item.equals(array[pos])) pos++;
      {
        final T temp = array[pos];
        array[pos] = item;
        item = temp;
      }
      writes++;

      // Rotate the rest of the cycle.
      while (pos != cycleStart) {
        // Find where to put the item.
        pos = cycleStart;
        for (int i = cycleStart + 1; i < array.length; i++)
          if (array[i].compareTo(item) < 0) pos++;

        // Put the item there or right after any duplicates.
        while (item.equals(array[pos])) pos++;
        {
          final T temp = array[pos];
          array[pos] = item;
          item = temp;
        }
        writes++;
      }
    } 
    return writes;
  }

  public static final void main(String[] args) {
    final Random rand = new Random();

    final Integer[] array = new Integer[8];
    for (int i = 0; i < array.length; i++) { array[i] = rand.nextInt(8); }

    for (int iteration = 0; iteration < 10; iteration++) {
      System.out.printf("array: %s ", Arrays.toString(array));
      final int writes = cycleSort(array);
      System.out.printf("sorted: %s writes: %d\n", Arrays.toString(array), writes);
      Collections.shuffle(Arrays.asList(array));
    }
  }
}

一些示例运行:

array: [3, 2, 6, 1, 3, 1, 4, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 3, 4, 1, 3, 2, 4, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 4
array: [3, 3, 1, 1, 4, 4, 2, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 1, 3, 2, 4, 3, 6, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [3, 2, 3, 4, 6, 4, 1, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [6, 2, 4, 3, 1, 3, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [6, 3, 2, 4, 3, 1, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 5
array: [4, 2, 6, 1, 1, 4, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [4, 3, 3, 1, 2, 4, 6, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [1, 6, 4, 2, 4, 1, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7

array: [5, 1, 2, 3, 4, 3, 7, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 5
array: [5, 1, 7, 3, 2, 3, 4, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [4, 0, 3, 1, 5, 2, 7, 3] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 8
array: [4, 0, 7, 3, 5, 1, 3, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [3, 4, 2, 7, 5, 3, 1, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 3, 2, 3, 7, 1, 4] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [1, 4, 3, 7, 2, 3, 5, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [1, 5, 0, 7, 3, 3, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 7, 3, 3, 4, 2, 1] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 4
array: [7, 3, 1, 0, 3, 5, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7

Answer 2

如果数组较短(即少于约100个元素),如果您还想减少写入次数,则选择排序通常是最佳选择.

来自维基百科:

另一个关键区别是选择排序总是执行Θ(n)交换,而插入排序在平均和最差情况下执行Θ(n ²)交换.因为交换需要写入数组,所以如果写入内存比读取要昂贵得多,则选择排序更为可取.如果物品很大但钥匙很小,通常就是这种情况.写入时间至关重要的另一个例子是存储在EEPROM或Flash中的数组.没有其他算法可以减少数据移动.

对于较大的数组/列表,Quicksort和朋友将提供更好的性能,但可能仍然需要更多的写入而不是选择排序.

如果您感兴趣,这是一个梦幻般的排序可视化站点,它允许您观察特定的排序算法完成其工作,并且还"竞争"彼此不同的排序算法.