中位数3快速排序实现

Question

我的中位数3实现在这里不能正常工作。我必须随机选择3个数字作为中间，这是我的代码，请帮助我。

#include"stdafx.h"
#include <iostream>
#include<algorithm>
using namespace std;
#define size 10
int i;                               
void show(int* array, int n);
int partition(int* array, int pValue, int left, int right);
void QuickSort(int* array, int left, int right);
int main(void)
{
    int array[size];
    int i;
    for( i = 0; i < size; i++)              
    {
         array[i]=rand()%100;
    }
    cout<<endl<<"The random generated numbers are: "<<endl;
    show(array, size);
    QuickSort(array,0,size - 1);                
    cout<<endl<<"The sorted numbers are : "<<endl;
    show(array, size);
    system("pause");
    return 0;
}
void show(int* array, int n)
{
    int i;
    for( i = 0; i < n; i++) cout<<array[i]<<'t';
}

void QuickSort(int* array, int left, int right)
{
    for(i=0;i<3;i++)
    {
       array[i]=array[rand()%100];
      }
      stable_sort(array,array+3);
     int p=array[(i+1)/2];
    //int p = array[left];              
    int split;
    if(right > left)                         
    {
        split = partition(array, p, left, right);
        array[split] = p;
        QuickSort(array, left, split-1);   
        QuickSort(array, split+1, right);    
    }
}

int partition(int* array, int p, int left, int right)
{
    int lb = left;
    int rb = right;
    while(lb < rb)             
    {
         while( p < array[rb]&& rb > lb)      
         {
              rb--;                     
         }
         swap(array[lb], array[rb]);
         while( p >= array[lb]&& lb < rb)     
         {
              lb++;                      
         }
         swap(array[rb], array[lb]);
    }
    return lb;                            

}

Answer 1

对于这个简单的算法来说，你的代码太复杂了，检查下面的代码:

void QuickSortMedian(int a[],int start,int end) {
    int q;
    count++;
    if (end-start<2) return;
    q=MedianOfThreePartition(a,start,end);
    QuickSortMedian(a,start,q);
    QuickSortMedian(a,q,end);
}
int MedianOfThreePartition(int a[],int p, int r) {
    int x=a[p],y=a[(r-p)/2+p],z=a[r-1],i=p-1,j=r;
    if (y>x && y<z || y>z && y<x ) x=y;
    else if (z>x && z<y || z>y && z<x ) x=z;
    while (1) {
        do  {j--;count++;} while (a[j] > x);
        do  {i++;count++;} while (a[i] < x);
        if  (i < j) swap(&a[i],&a[j]);
        else return j+1;
    }
}

void QuickSortRandomAndMedian(int a[],int start,int end) {
    int q;
    count++;
    if (end-start<2) return;
    q=RandomAndMedianPartition(a,start,end);
    QuickSortRandomAndMedian(a,start,q);
    QuickSortRandomAndMedian(a,q,end);
}
int RandomAndMedianPartition(int a[],int p, int r) {
    int t,x=a[t=((rand()%(r-p))/2)+p+(r-p)/4],y=a[t+1],z=a[t-1],i=p-1,j=r;
    if (y>x && y<z || y>z && y<x ) x=y;
    else if (z>x && z<y || z>y && z<x ) x=z;
    while (1) {
        do  {j--;count++;} while (a[j] > x);
        do  {i++;count++;} while (a[i] < x);
        if  (i < j) swap(&a[i],&a[j]);
        else return j+1;
    }
}

第二个算法只是我为优化快速排序而写的一个提升，例如在一个40000个元素的数组上，常规快速排序执行了大约800k次操作，中位数执行了650k次，随机中位数执行了大约620k次。这是目前最好的了。:)

Answer 2

问题可能出在这里:

array[i]=array[rand()%100];

首先，当您应该与其他元素交换时，更改了数组的一些元素。如果你不这样做，你正在破坏数据。

第二，你的数组大小为10，但你要求在0到99之间的随机位置上的索引。显然，你不能这样做，这就是为什么你得到垃圾。