为什么在我的电脑上运行快速排序要比归并排序要慢啊= =

来源：3-5 快速排序法 - Quick Sort

山重山

2016-11-22

快速排序和归并排序（优化版）用的都是老师您的代码哦= =

基本上测试结果：

归并排序都是0.2左右

快速排序都是0.9左右

处理的数据规模是1000000

写回答

7回答

liuyubobobo

2016-11-22

已采纳

差距这么大，不太应该。是不是Quick Sort连随机化都没做？在这种情况下，Quick Sort在一些测试用例中确实会慢一些。

课程中逐步介绍了4个版本的Quick Sort

1）经典实现

2）加入随机化

3）两端向中间靠拢的partition

4）三路快排

其中2）的那部优化，每次随机选取pivot，在真正的快排实现中必须加入。

另外，如果使用VS测试，请确认使用release模式测试性能。

山重山

老师，您请看下面我新的运行结果

2016-11-24

共7条回复

阳光的味道3821399

2017-01-12

我这边也是这样的问题，归并排序效率比快速排序效率高（见下图, 100w的随机数据）：

//szimg.mukewang.com/587746b90001266602690070.jpg

需要说明的是，我的代码中没有用标准库中的swap函数，因为效率更低，而是自己写了一个简单的交换函数

template<typename T>
void _swap(T &a, T &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

// Quicksort, following Bentley and McIlroy,

// ``Engineering a Sort Function,'' SP&E November 1993.

上面这篇论文给出了cpu运算的执行时间，如下图

//szimg.mukewang.com/587748670001597505740595.jpg

从图中可以看出，标准库里面的swap函数效率很低，是赋值50多倍，而即使是自己写的交换函数，效率也是比较低的。

归并排序中没有用到交换，而快排中主要操作就是交换，会不会是这个原因导致效率下降的呢？

timpcfan

应该就是这个原因，我自己测试，原本我这边快排处理100w级数据要0.276秒，直接将swap函数换成3个赋值操作，处理同样的数据只需要0.182秒了，已经超过了我这边的归并排序的0.227秒

2017-03-11

共5条回复

qq_一路成长_0

2018-01-22

1.swap函数自己写2.运行方式是release，结果就不是这样了。

keyboard2steper

2017-02-11

我也遇到这样的问题

keyboard2steper

liuyubobobo

谢谢老师，效果很显著~

2017-02-13

共2条回复

山重山

提问者

2016-11-24

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include"SortTestHelper.h"
#define True 1

template<typename T>
void insertionSort(T arr[], int l, int r) {

	for (int i = l + 1; i <= r; i++) {

		T e = arr[i];
		int j;
		for (j = i; j > l && arr[j - 1] > e; j--)
			arr[j] = arr[j - 1];
		arr[j] = e;
	}

	return;
}

//===================================================================

template<typename  T>
void __merge(T arr[], int l, int mid, int r) {

	T *aux=new T[r-l+1];
	for (int i = l; i <= r; i++)
		aux[i - l] = arr[i];

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++) {

		if (i > mid) { arr[k] = aux[j - l]; j++; }
		else if (j > r) { arr[k] = aux[i - l]; i++; }
		else if (aux[i - l] < aux[j - l]) { arr[k] = aux[i - l]; i++; }
		else { arr[k] = aux[j - l]; j++; }
	}
	delete[] aux;
}

template<typename T>
void __mergeSort(T arr[], int l, int r) {

	if (r - l <= 15) {
		insertionSort(arr, l, r);
		return;
	}

	int mid = (l + r) / 2;
	__mergeSort(arr, l, mid);
	__mergeSort(arr, mid + 1, r);
	if (arr[mid] > arr[mid + 1])
		__merge(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n) {

	__mergeSort(arr, 0, n - 1);
}

//=======================================================================

//是对arr[l...r]进行partition操作
//返回p,使得arr[l...p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int __partition(T arr[], int l, int r)
{
	swap(arr[l], arr[rand() % (r - l + 1) + l]);
	T v = arr[l];

	int j = l;
	for (int i = l + 1; i <= r; i++)
		if (v > arr[i])
			swap(arr[++j], arr[i]);

	swap(arr[j], arr[l]);

	return j;
}

//对arr[l...r]部分进行快速排序
template<typename T>
void __quicksort(T arr[], int l, int r)
{
	//if (l >= r)
	//	return;

	if (r - l <16)
	{
		insertionSort(arr, l, r);
		return;
	}

	int p = __partition(arr, l, r);
	__quicksort(arr, l, p - 1);
	__quicksort(arr, p + 1, r);
	return;
}

//快速排序！
template<typename T>
void quick_sort(T arr[], int n)
{
	srand((int)time(NULL));
	__quicksort(arr, 0, n - 1);
}

//=============================================================

//是对arr[l...r]进行partition操作
//返回p,使得arr[l...p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int __partition2(T arr[], int l, int r)
{
	swap(arr[l], arr[rand() % (r - l + 1) + l]);
	T v = arr[l];

	//arr[l+1...i)部分小于v,arr(j...r]部分大于v
	int i = l + 1, j = r;
	while (True)
	{
		while (i <= r&&arr[i] < v)
			i++;
		while (j >= l + 1 && arr[j] > v)
			j--;
		if (i > j)
			break;
		swap(arr[i], arr[j]);
		i++;
		j--;
	}
	swap(arr[l], arr[j]);

	return j;
}

//对arr[l...r]部分进行快速排序
template<typename T>
void __quicksort2(T arr[], int l, int r)
{
	//if (l >= r)
	//	return;

	if (r - l <16)
	{
		insertionSort(arr, l, r);
		return;
	}

	int p = __partition2(arr, l, r);
	__quicksort2(arr, l, p - 1);
	__quicksort2(arr, p + 1, r);
	return;
}

//快速排序！
template<typename T>
void quick_sort2(T arr[], int n)
{
	srand((int)time(NULL));
	__quicksort2(arr, 0, n - 1);
}

//测试快速排序和归并排序的运行速度
int main()
{
	
	//int time = 0,avm=0,avq=0,avq2=0;
	int *arr1, *arr2, *arr3;
	int n = 1000000;
	//while (time < 1000000)
	//{
		arr1 = SortTestHelper::generateRandomArray(n, 0, n);
		arr2 = SortTestHelper::copyIntArray(arr1, n);
		arr3 = SortTestHelper::copyIntArray(arr1, n);
		/*Guibing_BU_sort(arr1, n);
		quick_sort(arr2, n);*/
		//快排若没有随机化则会退化到o(n**2)级的算法
		SortTestHelper::testSort("merge sort", mergeSort, arr1, n);
		SortTestHelper::testSort("quick sort", quick_sort, arr2, n);
		SortTestHelper::testSort("quick sort2", quick_sort2, arr3, n);

		delete[] arr1;
		delete[] arr2;
		delete[] arr3;
	/*}*/
		putchar('\n');

		int swaptime = 100;
		arr1 = SortTestHelper::generateNearlyOrderedArray(n, swaptime);
		arr2 = SortTestHelper::copyIntArray(arr1, n);
		arr3 = SortTestHelper::copyIntArray(arr1, n);

		SortTestHelper::testSort("merge sort", mergeSort, arr1, n);
		SortTestHelper::testSort("quick sort", quick_sort, arr2, n);
		SortTestHelper::testSort("quick sort2", quick_sort2, arr3, n);

		delete[] arr1;
		delete[] arr2;
		delete[] arr3;

		putchar('\n');

		 n = 1000000;
		 arr1 = SortTestHelper::generateRandomArray(n, 0, 10);
		 //arr2 = SortTestHelper::copyIntArray(arr1, n);
		 arr3 = SortTestHelper::copyIntArray(arr1, n);
		/*Guibing_BU_sort(arr1, n);
		quick_sort(arr2, n);*/
		//快排若没有随机化则会退化到o(n**2)级的算法
		SortTestHelper::testSort("merge sort", mergeSort, arr1, n);
		//SortTestHelper::testSort("quick sort", quick_sort, arr2, n);
		SortTestHelper::testSort("quick sort2", quick_sort2, arr3, n);

		delete[] arr1;
		//delete[] arr2;
		delete[] arr3;

		putchar('\n');
		putchar('\n');


	system("pause");
}

//szimg.mukewang.com/5836faf00001dabd03050342.jpg

插入，归并，用的都是您的代码！

难道是我电脑有问题？

我有我舍友的电脑测试了下，运行结果甚至比我的更差！

哎呦不错哦12

liuyubobobo

老师，我试了一下release模式下快排确实比归并快很多，看来果然是VS的问题

2016-12-02

共5条回复

小狗和小猫咪30

2017-12-15

你这个差别也太夸张了，一百万数据我优化后的归并排序0.303,卡快速排序是0.34,跟老师的结论刚刚好相反，归并排序比快排快了30%

liuyubobobo

小狗和小猫咪30

如果使用VS做算法性能测试，请确保是在release模式下运行哦。具体可以看这个问题：http://coding.imooc.com/learn/questiondetail/3603.html

2017-12-15

共2条回复

山重山

提问者

2016-11-24

老师我加上随机化了，但还是，改变不大

//szimg.mukewang.com/5836d8fa0001f48602590605.jpg

下面是源代码

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include"SortTestHelper.h"
#include"Sort_collection.h"
using namespace std;
//是对arr[l...r]进行partition操作
//返回p,使得arr[l...p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int __partition(T arr[], int l, int r)
{
	swap(arr[l] , arr[rand() % (r - l + 1) + l]);
	T v = arr[l];

	int j = l;
	for (int i = l + 1; i <= r; i++)
		if (v > arr[i])
			swap(arr[++j], arr[i]);

	swap(arr[j], arr[l]);

	return j;
}

//对arr[l...r]部分进行快速排序
template<typename T>
void __quicksort(T arr[], int l, int r)
{
	//if (l >= r)
	//	return;

	if (r - l <16)
	{
		charu_guibing_sort(arr, l, r);
		return;
	}

	int p = __partition(arr, l, r);
	__quicksort(arr, l, p - 1);
	__quicksort(arr, p + 1, r);
	return;
}

//快速排序！
template<typename T>
void quick_sort(T arr[],int n)
{
	srand((int)time(NULL));
	__quicksort(arr, 0, n - 1);
}

//测试快速排序和归并排序的运行速度
int main()
{
	char c;
	do {
		int n = 1000000;
		int *arr1 = SortTestHelper::generateRandomArray(n, 0, n);
		int *arr2 = SortTestHelper::copyIntArray(arr1,n);

		/*Guibing_BU_sort(arr1, n);
		quick_sort(arr2, n);*/
		//快排若没有随机化则会退化到o(n**2)级的算法
		SortTestHelper::testSort("merge sort", Guibing_sort, arr1, n);
		SortTestHelper::testSort("quick sort", quick_sort, arr2, n);

		delete[] arr1;
		delete[] arr2;

		int swaptime = 100;
		arr1 = SortTestHelper::generateNearlyOrderedArray(n, swaptime);
		arr2 = SortTestHelper::copyIntArray(arr1, n);

		SortTestHelper::testSort("merge sort", Guibing_sort, arr1, n);
		SortTestHelper::testSort("quick sort", quick_sort, arr2, n);

		delete[] arr1;
		delete[] arr2;
	} while ((c = getchar()) == '\n');

	system("pause");
}

liuyubobobo

如果使用VS做算法性能测试，请确保是在release模式下运行哦。具体可以看这个问题：http://coding.imooc.com/learn/questiondetail/3603.html

2017-02-11

共4条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

自底向上归并排序在2^n+1大小的数据集上是否性能会比较差？

回答 1

为何有递归的自顶向下的排序方法要快？