Блог

моя реализация median 3 здесь работает неправильно. я должен случайным образом выбрать 3 числа для medium вот мой код, пожалуйста, помогите мне.

 #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]amp;amp; rb > lb)      
         {
              rb--;                     
         }
         swap(array[lb], array[rb]);

         while( p >= array[lb]amp;amp; lb < rb)     
         {
              lb  ;                      
         }
         swap(array[rb], array[lb]);

    }
    return lb;                            


}
  

Ваш код был слишком сложным для этого простого алгоритма, проверьте код ниже:

 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 amp;amp; y<z || y>z amp;amp; y<x ) x=y;
    else if (z>x amp;amp; z<y || z>y amp;amp; z<x ) x=z;
    while (1) {
        do  {j--;count  ;} while (a[j] > x);
        do  {i  ;count  ;} while (a[i] < x);
        if  (i < j) swap(amp;a[i],amp;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 amp;amp; y<z || y>z amp;amp; y<x ) x=y;
    else if (z>x amp;amp; z<y || z>y amp;amp; z<x ) x=z;
    while (1) {
        do  {j--;count  ;} while (a[j] > x);
        do  {i  ;count  ;} while (a[i] < x);
        if  (i < j) swap(amp;a[i],amp;a[j]);
        else return j 1;
    }
}
  

Второй алгоритм — это просто дополнение, которое я написал для оптимизации быстрой сортировки, например, для массива из 40000 элементов обычная быстрая сортировка выполняла около 800 тыс. действий, медианная — 650 тыс., а случайная медианная — около 620 тыс. Это лучшее, что у меня пока есть. 🙂

Возможно, проблема здесь:

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

Во-первых, вы изменяете некоторые элементы массива, в то время как вы должны заменять их другими. В противном случае вы уничтожаете данные.

Во-вторых, ваш массив имеет размер 10, но вы запрашиваете индекс в случайном положении от 0 до 99. Очевидно, что вы не можете этого сделать, и именно поэтому вы получаете мусор.