标签: quicksort

我昨天正在努力实现一个快速排序,然后我运行它,期望比Mergesort更快的运行时间(我也已实现).我运行了两个,虽然快速排序对于较小的数据集<100个元素更快(并且我确实验证了它的工作原理),但mergesort很快就成为了更快的算法.有人告诉我,quicksort几乎总是比mergesort"更快",我理解这个话题有一些争论,但我至少预计它会比这更接近.对于数据集> 10000个元素,mergesort的速度提高了4倍以上.这是预期的,还是我的快速排序代码中有错误？

归并排序:

public static void mergeSort(int[ ] e)
{
    if (e.length <= 1) return;
    int[] first = new int[e.length/2];
    int[] second = new int[e.length - first.length];
    System.arraycopy(e, 0, first, 0, first.length);
    System.arraycopy(e, first.length, second, 0, second.length);
    mergeSort(first);
    mergeSort(second);
    System.arraycopy(merge(first, second), 0, e, 0, e.length);
}

private static int[] merge(int[] first, int[] second) {
    int iFirst = 0;
    int iSecond = 0;
    int iCombined = 0;

    int[] combined = new int[first.length + second.length];
    while(iFirst < first.length && iSecond …

下面的Quicksort分区算法是否会产生稳定的排序(即它是否保持元素的相对位置具有相等的值):

  partition(A,p,r)
  {
     x=A[r];
     i=p-1;
     for j=p to r-1
       if(A[j]<=x)
          i++;
          exchange(A[i],A[j])

       exchang(A[i+1],A[r]); 
     return i+1;
   }

我在本书中找到了快速排序算法

这是算法

QUICKSORT (A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x=A[r]
i=p-1
for j = p to r - 1
  if A <= x
     i = i + 1
     exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

我做了这个c#代码:

private void quicksort(int[] input, int low, int high)
{
    int pivot_loc = 0;

    if (low < high)
        pivot_loc = partition(input, low, high);
    quicksort(input, low, …

我正在搞乱Python试图练习我的排序算法并发现一些有趣的东西.

我有三个不同的数据:

• x =要排序的数字的数量
• y =数字所在的范围(所有随机生成的int)
• z =排序所需的总时间

当:
x = 100000且
y =(0,100000)时,则
z = 0.94182094911秒

当:
x = 100000且
y =(0,100),则
z = 12.4218382537秒

当:
x = 100000且
y =(0,10),则
z = 110.267447809秒

有任何想法吗？

码:

import time
import random
import sys

#-----Function definitions

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    for items in array:
        if items <= pivotVal:
            smaller.append(items) …

我正在努力找出一个有效的quicksort算法.它工作正常,但是当元素数量巨大时,需要很长时间才能运行,并且数组的某些部分是预先排序的.我正在查阅维基百科的文章,在quicksort那里我找到了这样写的:

为了确保最多使用O(log N)空间,首先递归到数组的较小一半,然后使用尾调用递归到另一个.

对于这种小阵列上的调用(即长度小于实验确定的阈值t),使用插入排序,其具有较小的常数因子并因此在小阵列上更快.这可以通过将这些数组保持未排序并在末尾运行单个插入排序传递来实现,因为插入排序有效地处理几乎排序的数组.在识别每个小段时单独插入排序会增加启动和停止许多小排序的开销,但避免浪费在多个段边界上比较密钥的工作量,由于快速排序过程的工作原因,这些密钥将按顺序排列.它还改善了缓存的使用.

我目前正在递归两个分区.知道如何实现第一个提示吗？何谓递归先入阵的小一半,并使用尾部调用递归到其他？其次,我如何insertion-sort在快速排序中实施？它是否总能提高效率,或者只有在阵列的某些部分进行预先排序时？如果是第二种情况,那么当然我无法知道何时会发生这种情况.那我insertion-sort什么时候应该包括？

Quicksort不稳定,因为它交换不相邻的元素.

请帮我理解这个陈述.

我知道分区是如何工作的,以及稳定性是什么.但我无法弄清楚是什么导致上述不稳定的原因？然后我相信合并排序也是如此 - 尽管它被引用为一种稳定的算法.

我只是想知道(在一些严重的偏执和某些情况下)使用QuickSort算法是否会被视为应用程序中的安全风险.

它的基本实现和改进版本(如3-median-quicksort)都具有特定输入数据行为异常的特性,这意味着它们的运行时间在这些情况下可能会极大地增加(具有O(n^2)复杂性),更不用说堆栈溢出的可能性.

因此,我认为通过向程序提供预先排序的数据可能会造成伤害,导致算法表现得像这样,这可能会对例如多客户端Web应用程序产生不可预测的后果.

这个奇怪的案例是否值得任何安全考虑(因此会迫使我们使用Intro-或Mergesort)？

编辑:我知道有很多方法可以阻止Quicksort的最坏情况,但是语言集成排序(如.NET的3中位数)呢.他们会成为禁忌吗？

我学习了快速排序以及如何在递归和迭代方法中实现它.
在迭代方法中:

1. 将范围(0 ... n)推入堆栈
2. 使用数据透视表对给定数组进行分区
3. 弹出顶部元素.
4. 如果范围包含多个元素,则将分区(索引范围)推入堆栈
5. 执行上述3个步骤,直到堆栈为空

递归版本是wiki中定义的正常版本.

我了解到递归算法总是慢于迭代算法.
那么,就时间复杂度而言,哪种方法更受欢迎(内存不是问题)？
哪一个在编程竞赛中使用得足够快？
c ++ STL sort()是否使用递归方法？

我一直在网上寻找一段时间,我想知道是否存在通常使用的快速排序的"稳定"事实实现？我可以写自己的,但为什么重新发明轮子......

我有一个我在这里写的快速入口:

void swap(int& a, int& b);
int mid(int lo, int hi);

// My quicksort implementation
void sort(int vec[], int lo, int hi)
{
        int mid;
        if (hi > lo) {
                int i = lo + 1;
                int j = hi;
                int p = mid(lo, hi);
                swap(vec[lo], vec[p]);
                mid = vec[lo];
                while (i < j) {
                        if (vec[i] <= mid) {
                                i++;
                        } else {
                                while (i < --j && vec[j] >= mid);
                                swap(vec[i], vec[j]);
                        }
                }
                i++;
                swap(vec[lo], vec[i]);
                sort(vec, …