位数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元阵列提振定期快速分类做了大约80万次的动作，中位数做了650k，随机中位数做了大约620k。这是迄今为止最好的。 :)

Answer 2

也许问题就在这里：

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

首先，您要更改阵列的一些元素，当你应该交换他们与其他人。如果你不这样做，你会破坏数据。

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