中位数3快速排序实现
|
我的中位数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;
}
没有找到相关结果
已邀请:
2 个回复
埃输林桨铃
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; } }末钉蹈泰唬
首先，当您应该与其他元素交换数组时，您要更改数组的某些元素。如果您不这样做，则是在破坏数据。 其次，您的数组的大小为10，但是您要在0到99之间的随机位置处要求一个索引。显然，您不能这样做，这就是为什么您得到垃圾的原因。