优化的合并排序比快速排序更快
[http://jsperf.com/optimized-mergesort-versus-
quicksort][1]
为什么这个半缓冲区合并排序的工作速度与quicksort一样快？
QuickSort是：
- 就地虽然会占用
log(n)递归（堆栈空间） - 缓存友好
这一半缓冲区合并排序：
- 使用
n/2Buffer进行合并。 - 使用
log(n)递归。 - 进行较少的比较。
我的问题是，在这种情况下，为什么半缓冲区合并排序与QuickSort的速度匹配？另外，我对quickSort做错了什么，这会使它变慢了吗？
function partition(a, i, j) {
var p = i + Math.floor((j - i) / 2);
var left = i + 1;
var right = j;
swap(a, i, p);
var pivot = a[i];
while (left <= right) {
while (builtinLessThan(a[left], pivot)) {
++left;
}
while (builtinLessThan(pivot, a[right])) {
--right;
}
if (left <= right) {
swap(a, left, right);
++left;
--right;
}
}
swap(a, i, right);
return right;
};
function quickSort(a, i, j) {
var p = partition(a, i, j);
if ((p) - i > j - p) {
if (i < p - 1) {
quickSort(a, i, p - 1);
}
if (p + 1 < j) {
quickSort(a, p + 1, j);
}
} else {
if (p + 1 < j) {
quickSort(a, p + 1, j);
} if (i < p - 1) {
quickSort(a, i, p - 1);
}
}
};
问题答案：
合并排序的比较次数较少，但比快速排序的动作更多。必须调用函数进行比较会增加比较的开销，这会使快速排序变慢。示例快速排序中的所有if语句也使它变慢。如果比较和交换是内联完成的，那么如果对伪随机整数数组进行排序，则快速排序应该会更快一些。
如果在具有16个寄存器的处理器（例如64位模式的PC）上运行，则使用一堆最终在寄存器中的指针进行的4方式合并排序大约与快速排序一样快。2路合并排序平均值对每个移动的元素进行比较1，而4路合并排序平均值3对每个移动的元素进行比较，但只需要通过次数的1/2，因此基本操作的次数是相同的，但是比较起来对缓存的友好性更高，这使得4路合并排序的速度提高了约15％，与快速排序的速度差不多。
我对Java脚本不熟悉，因此我将示例转换为C ++。
使用Java脚本合并排序的转换版本，排序1600万伪随机32位整数大约需要2.4秒。下面显示的示例快速排序需要大约1.4秒，下面显示的示例自下而上合并需要大约1.6秒。如前所述，在带有16个寄存器的处理器上使用一堆指针（或索引）进行4路合并也将花费大约1.4秒。
C ++快速排序示例：
void QuickSort(int a[], int lo, int hi) {
int i = lo, j = hi;
int pivot = a[(lo + hi) / 2];
int t;
while (i <= j) { // partition
while (a[i] < pivot)
i++;
while (a[j] > pivot)
j--;
if (i <= j) {
t = a[i]
a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
if (lo < j) // recurse
QuickSort(a, lo, j);
if (i < hi)
QuickSort(a, i, hi);
}
C ++自下而上的合并排序示例：
void BottomUpMergeSort(int a[], int b[], size_t n)
{
size_t s = 1; // run size
if(GetPassCount(n) & 1){ // if odd number of passes
for(s = 1; s < n; s += 2) // swap in place for 1st pass
if(a[s] < a[s-1])
std::swap(a[s], a[s-1]);
s = 2;
}
while(s < n){ // while not done
size_t ee = 0; // reset end index
while(ee < n){ // merge pairs of runs
size_t ll = ee; // ll = start of left run
size_t rr = ll+s; // rr = start of right run
if(rr >= n){ // if only left run
rr = n;
BottomUpCopy(a, b, ll, rr); // copy left run
break; // end of pass
}
ee = rr+s; // ee = end of right run
if(ee > n)
ee = n;
BottomUpMerge(a, b, ll, rr, ee);
}
std::swap(a, b); // swap a and b
s <<= 1; // double the run size
}
}
void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}
void BottomUpCopy(int a[], int b[], size_t ll, size_t rr)
{
while(ll < rr){ // copy left run
b[ll] = a[ll];
ll++;
}
}
size_t GetPassCount(size_t n) // return # passes
{
size_t i = 0;
for(size_t s = 1; s < n; s <<= 1)
i += 1;
return(i);
}
使用指针的4种方式进行合并排序的C
++示例（goto用于节省代码空间，它是旧代码）。它开始进行4种方式的合并，然后在运行结束时切换为3种方式的合并，然后进行2种方式的合并，然后再复制剩余的剩余部分。这类似于用于外部排序的算法，但是外部排序逻辑更为通用，通常可以处理多达16种方式的合并。
int * BottomUpMergeSort(int a[], int b[], size_t n)
{
int *p0r; // ptr to run 0
int *p0e; // ptr to end run 0
int *p1r; // ptr to run 1
int *p1e; // ptr to end run 1
int *p2r; // ptr to run 2
int *p2e; // ptr to end run 2
int *p3r; // ptr to run 3
int *p3e; // ptr to end run 3
int *pax; // ptr to set of runs in a
int *pbx; // ptr for merged output to b
size_t rsz = 1; // run size
if(n < 2)
return a;
if(n == 2){
if(a[0] > a[1])std::swap(a[0],a[1]);
return a;
}
if(n == 3){
if(a[0] > a[2])std::swap(a[0],a[2]);
if(a[0] > a[1])std::swap(a[0],a[1]);
if(a[1] > a[2])std::swap(a[1],a[2]);
return a;
}
while(rsz < n){
pbx = &b[0];
pax = &a[0];
while(pax < &a[n]){
p0e = rsz + (p0r = pax);
if(p0e >= &a[n]){
p0e = &a[n];
goto cpy10;}
p1e = rsz + (p1r = p0e);
if(p1e >= &a[n]){
p1e = &a[n];
goto mrg201;}
p2e = rsz + (p2r = p1e);
if(p2e >= &a[n]){
p2e = &a[n];
goto mrg3012;}
p3e = rsz + (p3r = p2e);
if(p3e >= &a[n])
p3e = &a[n];
// 4 way merge
while(1){
if(*p0r <= *p1r){
if(*p2r <= *p3r){
if(*p0r <= *p2r){
mrg40: *pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg3123; // merge 1,2,3
} else {
mrg42: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg3013; // merge 0,1,3
}
} else {
if(*p0r <= *p3r){
goto mrg40; // run 0 smallext
} else {
mrg43: *pbx++ = *p3r++; // run 3 smallest
if(p3r < p3e) // if not end run continue
continue;
goto mrg3012; // merge 0,1,2
}
}
} else {
if(*p2r <= *p3r){
if(*p1r <= *p2r){
mrg41: *pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg3023; // merge 0,2,3
} else {
goto mrg42; // run 2 smallest
}
} else {
if(*p1r <= *p3r){
goto mrg41; // run 1 smallest
} else {
goto mrg43; // run 3 smallest
}
}
}
}
// 3 way merge
mrg3123: p0r = p1r;
p0e = p1e;
mrg3023: p1r = p2r;
p1e = p2e;
mrg3013: p2r = p3r;
p2e = p3e;
mrg3012: while(1){
if(*p0r <= *p1r){
if(*p0r <= *p2r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg212; // merge 1,2
} else {
mrg32: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg201; // merge 0,1
}
} else {
if(*p1r <= *p2r){
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg202; // merge 0,2
} else {
goto mrg32; // run 2 smallest
}
}
}
// 2 way merge
mrg212: p0r = p1r;
p0e = p1e;
mrg202: p1r = p2r;
p1e = p2e;
mrg201: while(1){
if(*p0r <= *p1r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto cpy11;
} else {
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto cpy10;
}
}
// 1 way copy
cpy11: p0r = p1r;
p0e = p1e;
cpy10: while (1) {
*pbx++ = *p0r++; // copy element
if (p0r < p0e) // if not end of run continue
continue;
break;
}
pax += rsz << 2; // setup for next set of runs
}
std::swap(a, b); // swap ptrs
rsz <<= 2; // quadruple run size
}
return a; // return sorted array
}
-
在处理接近排序的数组时，哪种算法的快速排序或合并排序性能更好？为什么？我意识到，在这种情况下，其他算法可能会比这些算法表现得更好。
-
问题：Mergesort将一个数字列表分成两半，并对这两个数字进行递归调用。相反，您能在左半部分执行quicksort，在右半部分执行mergesort吗？如果是，则通过显示每个步骤来显示它将如何对下面的数字列表进行排序。如果没有，请解释为什么不能。 Iam应该使用MergeSort对数字列表进行排序。左半部分将使用快速排序进行排序？ 我想出来了。安：是的，我们可以 使用mergeSort对数组的
-
快速排序 from typing import List def quick_sort(arr: List, left, right) -> List: """ 快速排序是对冒泡排序的改进，核心思想是找到一个中值点pivot，然后将小于等于pivot的放在pivot的左边，大于pivot的放在右边，一直递归到无法拆分pivot点。 :param arr: :re
-
问题内容： 如何为Java实现并发的quicksort或mergesort算法？ 我们在16（虚拟）核的Mac上遇到问题，其中只有一个核（！）使用默认的Java排序算法工作，而且很好的机器没有得到充分利用是不好的。因此，我们编写了自己的代码（我编写了代码），并且确实取得了不错的提速（我编写了多线程快速排序，由于其分区特性，它可以很好地并行化，但我也可以编写合并排序）……但是我的实现只能扩展最多4个
-
本文向大家介绍JavaScript希尔排序、快速排序、归并排序算法，包括了JavaScript希尔排序、快速排序、归并排序算法的使用技巧和注意事项，需要的朋友参考一下 以var a = [4,2,6,3,1,9,5,7,8,0];为例子。 1.希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。 过程输出： 由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序
-
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两