median 3 quick sort-Implementierung
mein median 3 ist die Umsetzung nicht funktioniert hier gut. ich habe zu entscheiden, 3 Nummern, die zufällig für das medium, hier ist mein code bitte helft mir.
#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;
}
- Erzählen Sie uns, warum es nicht funktioniert würde uns helfen, Ihnen zu helfen. Scheitert es kompilieren? Läuft es aber Fehler zeigen? Läuft es aber produziert falsche Ergebnisse? Tut es ewig so weitergehen?
- Martinho Fernandes, wenn ich die pivot-Links-element funktioniert es einwandfrei, aber wenn ich ändern möchten, den Wert des pivot -, indem der median der ersten 3-element als pivot-es produziert einige Müll Wert.
- Dies ist das 5. mal, Sie haben diese Frage gestellt, und der code ist immer noch völlig gebrochen. Vielleicht sollte man diese Aufgabe beiseite und beginnen Sie mit etwas einfacher.
- Dies ist ganz klar nicht C-code.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dein code war zu Komplex für diese einfachen Algorithmus, überprüfen Sie folgenden code:
Den zweiten Algorithmus ist nur ein Schub, den ich schrieb für die Optimierung der schnellen Sorte, zum Beispiel auf einem 40000-Elemente-array regelmäßige schnell sortiert habe über 800k Aktionen, die median einen habe 650k und der zufälligen median wollte man etwa 620k. Das ist die beste, die ich habe, so weit. 🙂
Vielleicht ist das problem hier:
Erste, das Sie ändern, einige Elemente des Arrays, wenn es sein soll swapping Sie Sie mit anderen. Wenn Sie nicht sind, Daten zu vernichten.
Zweite, das array hat die Größe 10, aber du bist zu Fragen für einen index in einer beliebigen position zwischen 0 und 99. Natürlich können Sie nicht tun, und das ist, warum Sie immer Müll.
array
jedes mal, wenn Sie rufenQuickSort()
. Median-von-drei-Implementierung ist die Zerstörung von Daten in der array.