选择排序顺序
Selection sort order
我的书说：
Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difficulty writing a program to solve this problem. There are quite a few “obvious” solutions. One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order.
它说按降序对数组进行排序是有意义的。这有什么意义？如果我有一个 {1,9,3,7,4,6} 的数组并且我想要最大的元素，我会按升序对它进行排序，所以 {1,3,4,6,7,9} 然后 return 最后一个元素。为什么书上会说降序？
因为你可能不想要最大的元素，书上说
would like to determine the kth largest
如果你按升序排序，你怎么知道第三大数字是多少而不首先找出数组有多大？
如果数组是递减的，这会更容易，因为第三大元素就是第三个元素。
顺序本身并不是那么重要，但是如果你想要第k个最大元素，那么如果你按降序排序顺序，它位于第 k 个元素（如果我们从索引 0 开始，则为 k-1），而如果我们按升序排序顺序，它位于索引 n-k+1（如果索引从 0 开始，则为 n-k）。
对于 lazy 排序算法（就像 Haskell 和 C# Linq 的 .OrderBy 中的算法），这实际上可能对时间复杂度有影响。如果我们实现一个 lazy 选择排序算法（也就是一个生成器），那么这将 运行 in O(k×n) O(n2)。例如，如果我们使用快速排序的 lazy 变体，它将需要 O(n + k log n) 来获得第一个 k个元素。
在像 Haskell 这样的语言中，懒惰确实是一个关键特征，通常不仅要最小化生成整个结果的算法的时间复杂度，还要生成结果的子集。
我的书说：
Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difficulty writing a program to solve this problem. There are quite a few “obvious” solutions. One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order.
它说按降序对数组进行排序是有意义的。这有什么意义？如果我有一个 {1,9,3,7,4,6} 的数组并且我想要最大的元素，我会按升序对它进行排序，所以 {1,3,4,6,7,9} 然后 return 最后一个元素。为什么书上会说降序？
因为你可能不想要最大的元素，书上说
would like to determine the kth largest
如果你按升序排序，你怎么知道第三大数字是多少而不首先找出数组有多大？
如果数组是递减的，这会更容易，因为第三大元素就是第三个元素。
顺序本身并不是那么重要，但是如果你想要第k个最大元素，那么如果你按降序排序顺序，它位于第 k 个元素（如果我们从索引 0 开始，则为 k-1），而如果我们按升序排序顺序，它位于索引 n-k+1（如果索引从 0 开始，则为 n-k）。
对于 lazy 排序算法（就像 Haskell 和 C# Linq 的 .OrderBy 中的算法），这实际上可能对时间复杂度有影响。如果我们实现一个 lazy 选择排序算法（也就是一个生成器），那么这将 运行 in O(k×n) O(n2)。例如，如果我们使用快速排序的 lazy 变体，它将需要 O(n + k log n) 来获得第一个 k个元素。
在像 Haskell 这样的语言中，懒惰确实是一个关键特征，通常不仅要最小化生成整个结果的算法的时间复杂度，还要生成结果的子集。