标签: quicksort

显然LINQ的"OrderBy"最初被指定为不稳定,但到Orca时,它被指定为稳定.并非所有文档都已相应更新 - 请考虑以下链接:

• Jon Skeet对OrderBy的稳定性
• Troy Magennis对OrderBy的稳定性

但是,如果LINQ的OrderBy现在"稳定",那么这意味着它没有使用快速排序(这本质上是不稳定的),即使某些文档(例如Troy的书)说它是.所以我的问题是:如果不是快速排序,那么LINQ的orderBy使用的实际算法是什么？

是否有人能够提供一个"简单的英语"直观,但正式的解释是什么让QuickSort n登录？根据我的理解,它必须通过n个项目,并且它会记录n次...我不知道如何将其记入单词为什么它会执行此日志n次.

我有一个用Python和Haskell编写的简单脚本.它读取一个包含1,000,000个换行符分隔整数的文件,将该文件解析为整数列表,对其进行快速排序,然后将其写入已排序的其他文件.此文件的格式与未排序的文件相同.简单.

这是Haskell:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

main = do
    file <- readFile "data"
    let un = lines file
    let f = map (\x -> read x::Int ) un
    let done = quicksort f
    writeFile "sorted" (unlines (map show done))

这是Python:

def qs(ar):
    if len(ar) == 0:
        return ar

    p …

在分析QS时,每个人总是指"几乎排序"的最坏情况.什么时候可以通过自然输入发生这种情况？

我想出的唯一例子是重新编制索引.

似乎Radix sort具有非常好的平均案例性能,即O(kN):http://en.wikipedia.org/wiki/Radix_sort

但似乎大多数人仍在使用Quick Sort,不是吗？

为什么quicksort(或introsort)或任何基于比较的排序算法比radix-sort更常见？特别是对于数字排序.

基数排序不是基于比较的,因此可能比O(n logn)更快.实际上,它是O(k n),其中k是用于表示每个项目的位数.并且内存开销并不重要,因为您可以选择要使用的桶数,并且所需的内存可能小于mergesort的要求.

它与缓存有关吗？或者可能访问数组中的随机字节整数？

堆排序具有最差的情况复杂性,O(nlogn)而Quicksort O(n^2).但是,经验证据表明,快速排序是优越的.这是为什么？

具有3路分区的QuickSort是什么？

我已经实现了以下快速排序算法.在线我已经读过它的空间要求为O(log(n)).为什么会这样？我没有创建任何额外的数据结构.

是因为我的递归会在堆栈上使用一些额外的空间吗？如果是这种情况,是否可以通过不使用递归(而是使其迭代)来减少内存？

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on …

这是我写的快速排序代码.该功能不起作用,因为它无法到达基本情况.如果我记录枢轴r和l控制台,无论调用sort函数多少次,它们都保持不变.所以我想如果参数l,r并没有真正传递给函数的数据.为什么会这样？

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}