为什么快速排序比冒泡排序慢？

Question

所以我在我的大学里有那个 class，我们在那里做各种各样的事情，现在我们进行递归排序，也就是快速排序。好的，你们都知道它的作用，将数组分成两部分，依此类推，直到它以 1 个元素结尾，然后对它们进行排序。

所以我们讨论了哪个会更快以及为什么这就是所谓的快速排序，结果是快速排序的复杂度是 n.log2(n)，而例如冒泡排序是 n^2。好的，所以我用 c# 编写了 bouth 代码，并使用 c# 的秒表 i calcualte hte ms 来执行 bouth alogirithyms ，我在其中生成运行dom 数字 -65000,65000 和长度为 50 000 个元素的数组。

所以 bubblesort 第一次排序 23 秒，第二次 29（因为它们是运行doms ..），即使我制作了一个包含 50k 个元素且第一个元素为 n-i 的数组。也就是说，它需要对所有内容进行排序，它会持续 27 秒（所以关闭运行dom）如果我从 i 开始创建一个数组，它确实需要 17 秒来对它进行排序。

所以我运行 quickSort ，并且已经过去了 5 分钟仍然没有结果...如果我运行它与 arra[i] = i;或 n-i；它给了我 Whosebug 异常。

qSort 唯一更快的地方是当有一个包含 100 或 200 之类的元素的数组并且它们已经排序（又名数组 [i]=i）时，它更快，大约 0.1-0.2 秒。 buble sort 可以对非常大的数组进行排序，而 qSort 给了我 Whosebug。

回到复杂性，50 000 个元素的 qSort = 780482 而 bublesort = 2 500 000 000 很明显 qSort 需要什么？快 99.99%。但不是吗？为什么我真的对此感到好奇，因为我的讲师曾说过 qSort 快得多。但经过各种测试后，它似乎比 bubblesort 更快（稍微）快，并且它只适用于元素不多的数组。（10k 运行doms 元素 qSort 17 秒，而 bublesort 7）。

我的电脑配备 i7 4 核，每个 2.6 GHz，我有 16 GB RAM DDR4。

如果有人把事情弄清楚我会很高兴，因为我的讲师似乎给我一个虚假信息。

编辑两个代码： qsort................................

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
class QuickSort
{
    static public int Partition(int[] numbers, int left, int right)
    {
        int pivot = numbers[left];
        while (true)
        {
            while (numbers[left] < pivot)
                left++;

            while (numbers[right] > pivot)
                right--;

            if (left < right)
            {
                int temp = numbers[right];
                numbers[right] = numbers[left];
                numbers[left] = temp;
            }
            else
            {
                return right;
            }
        }
    }

    static public void SortQuick(int[] arr, int left, int right)
    {
        // For Recusrion  
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot > 1)
                SortQuick(arr, left, pivot - 1);

            if (pivot + 1 < right)
                SortQuick(arr, pivot + 1, right);
        }
    }

    static void Main(string[] args)
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();
        Random rnd = new Random();

        int max = Convert.ToInt32(Console.ReadLine());

        int[] numbers = new int[max];

        for (int i = 0; i < max; i++)
        {

            numbers[i] = rnd.Next(-65000, 65000);
        }


        // the code that you want to measure comes here






        SortQuick(numbers, 0, max - 1);

        for (int i = 0; i < max; i++)
            Console.WriteLine(numbers[i]);
        watch.Stop();
        var elapsedMs = watch.ElapsedMilliseconds;
        Console.WriteLine(elapsedMs);
        Console.ReadLine();
    }
}
}

Bublesort................................

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace bublesort
{
class Program
{
    static void Main(string[] args)
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();
        // the code that you want to measure comes here

        int n = int.Parse(Console.ReadLine());
        int[] arr = new int[n];
        Random rnd = new Random();
        int temp = 0;
        for (int i = 0; i < n; i++)
        {

            arr[i] = rnd.Next(-65000,65000);
        }
        for (int write = 0; write < arr.Length; write++)
        {
            for (int sort = 0; sort < arr.Length - 1; sort++)
            {
                if (arr[sort] > arr[sort + 1])
                {
                    temp = arr[sort + 1];
                    arr[sort + 1] = arr[sort];
                    arr[sort] = temp;
                }
            }
        }

        for (int i = 0; i < arr.Length; i++)
            Console.WriteLine(arr[i]);
        watch.Stop();
        var elapsedMs = watch.ElapsedMilliseconds;
        Console.WriteLine(elapsedMs);
    }
}
}

Answer 1

如果数组中有重复项，则两个 while 循环会以数组 [left] = array [right] = pivot 结尾。交换什么都不做，因为你不增加左边和减少右边，你的快速排序将永远卡住。

尝试使用长度为 2 的数组和两个相等的元素。它会立即挂起。

此外，通过选择数组 [left] 作为基准，一旦该错误得到修复，您可以保证排序数组的最坏情况（二次）行为。

Answer 2

 static public void Quicksort(int[] numbers, int left, int right)
    {
        int i = left, j = right;
        int pivot = numbers[(left+right)/2];

        while (i <= j)
        {
            while (numbers[i] < pivot)
            {
                i++;
            }

            while (numbers[j] > pivot)
            {
                j--;
            }

            if (i <=j)
            {
                // Swap
                int tmp = numbers[i];
               numbers[i] = numbers[j];
               numbers[j] = tmp;

                i++;
                j--;
            }

        }

        // Recursive calls
        if (left < j)
        {
            Quicksort(numbers, left, j);
        }

        if (i < right)
        {
            Quicksort(numbers, i, right);
        }
    }

是的问题解决了 thx for guidence，当我将枢轴设为中间元素时，我现在对区间 [-65000 到 65000] 中的 100 000 个随机元素进行排序 8 秒。虽然 buble sort 需要 71 秒。或者 Q 排序比 bublesort 快 90% ;)。

为什么快速排序比冒泡排序慢？

Why quickSort is slower then bubblesort?

arrays

sorting

compare

quicksort

bubble-sort