位數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之間的隨機位置。顯然，你不能這樣做，這就是爲什麼你會得到垃圾。