问题描述
下面是一些工作code,它实现了快速排序算法的使用插入排序数组大小 N'GT的修改版本; 8
。我的测试数组排序不完全正确,我想那一定是我的执行 Insertionsort
和插入
的。
递归 Insertionsort
算法的一般形式是:
无效Insertionsort(INT S [],INT N)
{
如果(正→1)
Insertionsort(S,N-1);
插入(S,N-1);
}
无效插入(INT * S,INT K)
{
INT键= S [K]
INT J = K-1;
而(J> = 0&功放;&放大器; S [J] GT;密钥)
{
S [J + 1] = S [J]。
j--;
}
S [J + 1] =键;
}
下面是我的完整的工作code表示不排序很完全正确的:
的#include<的iostream>
#包括<字符串>
#包括< stdlib.h中>
使用名字空间std;
诠释比较= 0;
诠释compare_qs_m3_ins [12];
//函数原型
INT分区(INT * S,诠释L,诠释U);
无效交换(INT名单[],INT磷,INT Q);
无效插入(INT S [],INT K);
无效Insertionsort(INT S [],INT低,诠释喜);
无效Quicksort_Insert_M3(INT S [],INT N,INT磷,INT读);
诠释的main()
{
函数srand(时间(NULL));
//声明用于测试的所有阵列
INT S1_500 [500];
INT S2_500 [500];
INT S3_500 [500];
INT S1_300 [300];
INT S2_300 [300];
INT S3_300 [300];
INT S1_100 [100];
INT S2_100 [100];
INT S3_100 [100];
INT S1_8 [8];
INT S2_8 [8];
INT S3_8 [8];
//填充随机整数数组
的for(int i = 0; I< 500;我++)
{
S1_500 [I] =兰特()%1000;
S2_500 [I] =兰特()%1000;
S3_500 [I] =兰特()%1000;
}
的for(int i = 0; I< 300;我++)
{
S1_300 [I] =兰特()%1000;
S2_300 [I] =兰特()%1000;
S3_300 [I] =兰特()%1000;
}
的for(int i = 0; I< 100;我++)
{
S1_100 [I] =兰特()%500;
S2_100 [I] =兰特()%500;
S3_100 [I] =兰特()%500;
}
的for(int i = 0; I< 8;我++)
{
S1_8 [I] =兰特()%100;
S2_8 [I] =兰特()%100;
S3_8 [I] =兰特()%100;
}
Quicksort_Insert_M3(S1_500,500,0,499);
compare_qs_m3_ins [0] =比较;
比较= 0;
Quicksort_Insert_M3(S2_500,500,0,499);
compare_qs_m3_ins [1] =比较;
比较= 0;
Quicksort_Insert_M3(S3_500,500,0,499);
compare_qs_m3_ins [2] =比较;
比较= 0;
Quicksort_Insert_M3(S1_300,300,0,299);
compare_qs_m3_ins [3] =比较;
比较= 0;
Quicksort_Insert_M3(S2_300,300,0,299);
compare_qs_m3_ins [4] =比较;
比较= 0;
Quicksort_Insert_M3(S3_300,300,0,299);
compare_qs_m3_ins [5] =比较;
比较= 0;
Quicksort_Insert_M3(S1_100,100,0,99);
compare_qs_m3_ins [6] =比较;
比较= 0;
Quicksort_Insert_M3(S2_100,100,0,99);
compare_qs_m3_ins [7] =比较;
比较= 0;
Quicksort_Insert_M3(S3_100,100,0,99);
compare_qs_m3_ins [8] =比较;
比较= 0;
Quicksort_Insert_M3(S1_8,8,0,7);
compare_qs_m3_ins [9] =比较;
比较= 0;
Quicksort_Insert_M3(S2_8,8,0,7);
compare_qs_m3_ins [10] =比较;
比较= 0;
Quicksort_Insert_M3(S3_8,8,0,7);
compare_qs_m3_ins [11] =比较;
比较= 0;
//的for(int i = 0; I< 12;我++)
// cout的<< compare_qs_m3_ins [1] - ;&其中; ENDL;
的for(int i = 0; I< 499;我++)
COUT<< S1_500 [1] - ;&其中; ENDL;
}
INT分区(INT * S,诠释L,诠释U)
{
INT X = S [升];
诠释J = 1;
的for(int i = L + 1; I< = U;我++)
{
比较++;
如果(S [1] - ; x)的
{
J ++;
掉期(S [I],S [J]);
}
}
INT P = D];
交换(S [升],S [P]);
返回磷;
}
无效掉期(INT和放大器; VAL1,INT和放大器;将val2)
{
INT TEMP = VAL1;
VAL1 = val2的;
将val2 =温度;
}
无效交换(INT名单[],INT磷,INT Q)
{
INT TEMP =列表[P]。
列表[P] =列表[Q]
列表[Q] =温度;
}
INT Sort3(INT名单[],INT磷,INT读)
{
INT中位数=(P + R)/ 2;
比较++;
如果(名单[P]< =列表[位数])
{
比较++;
如果(名单[位数]≥列表[R])
{
比较++;
如果(名单[P]<列表[R])
{
INT TEMP =列表[P]。
列表[P] =列表[R]。
列表[R] =列表[位数]
列表[位数] =气温;
}
其他
{
交换(列表,中位数,R);
}
}
其他
;
}
其他
{
比较++;
如果(名单[P]>清单[R])
{
比较++;
如果(名单[位数]其中,列表[R])
{
INT TEMP =列表[P]。
列表[P] =列表[位数]
列表[位数] =列表[R]。
列表[R] =温度;
}
其他
{
交换(列表中,P,R);
}
}
其他
{
交换(列表页,中位数);
}
}
返回列表[R]。
}
无效插入(INT * S,INT K)
{
INT键= S [K]
INT J = K-1;
而(J> = 0&功放;&放大器; S [J] GT;密钥)
{
S [J + 1] = S [J]。
j--;
比较++;
}
比较++;
S [J + 1] =键;
}
无效Insertionsort(INT S [],INT低,诠释喜)
{
如果((高至低)+ 1→1)
Insertionsort(S,低+ 1,喜);
插入(S,高保真低);
}
无效Quicksort_Insert_M3(INT S [],int的N,INT低,诠释喜)
{
如果((高至低)< = 8)
Insertionsort(S,低,HI);
其他
{
如果(低<喜)
{
如果((低+ 1)==喜)
{
比较++;
如果(S [小]> S [喜])
掉期(S [小],S [喜]);
}
其他
{
Sort3(S,低,HI);
如果((低+ 2)<喜)
{
掉期(S [低+ 1],S [(低+ HI)/ 2]);
INT Q =分区(S,低+ 1,HI-1);
Quicksort_Insert_M3(S,N,低,Q-1);
Quicksort_Insert_M3(S,N,Q + 1,喜);
}
}
}
}
}
应该升序李树斌数组元素进行排序的功能不会:
INT Sort3(INT名单[],INT磷,INT读)
{
仅供 P + 2'调用; = R
,所以
INT值=(P + R)/ 2;
P<平均< - [R
在这里。让 A =列表[P]
, B =列表[位数]
和 C =列表[R]
。
比较++;
如果(名单[P]< =列表[位数])
{
比较++;
如果(名单[位数]≥列表[R])
{
比较++;
如果(名单[P]<列表[R])
{
所以在这里,我们有 A< = B
, C< b
和 A< ç
,以及 A< C< b
INT TEMP =列表[P]。
列表[P] =列表[R]。
列表[R] =列表[位数]
列表[位数] =气温;
但将它们放在顺序 C,A,B
。也许你打算使用如果(名单[R]<列表[P])。
有
}
其他
C< = A LT; = B
{
交换(列表,中位数,R);
,以便安排他们为了 A,C,B
。
}
}
其他
;
}
其他
下面, B<一个
。
{
比较++;
如果(名单[P]>清单[R])
{
C<一个
比较++;
如果(名单[位数]其中,列表[R])
{
然后 B< C<一个
INT TEMP =列表[P]。
列表[P] =列表[位数]
列表[位数] =列表[R]。
列表[R] =温度;
是啊,这是正确的。
}
其他
C< = B<一个
{
交换(列表中,P,R);
}
Okedoke。
}
其他
{
B< A< = C
交换(列表页,中位数);
好了。
}
}
返回列表[R]。
}
为什么这个函数返回任何东西?你不使用返回值呢。
Here is some working code that implements a modified version of the Quicksort algorithm that uses Insertion Sort for array size n > 8
. My test array isn't sorting exactly right, and I think it must be with my implementation of Insertionsort
and Insert
.
The general form of the recursive Insertionsort
algorithm is:
void Insertionsort(int S[], int n)
{
if(n>1)
Insertionsort(S,n-1);
Insert(S,n-1);
}
void Insert(int *S, int k)
{
int key = S[k];
int j = k-1;
while(j>=0 && S[j] > key)
{
S[j+1] = S[j];
j--;
}
S[j+1] = key;
}
Here is my complete working code that does not sort quite exactly right:
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
int comparisons = 0;
int compare_qs_m3_ins[12];
// Function prototypes
int partition(int *S,int l, int u);
void exchange(int list[], int p, int q);
void Insert(int S[], int k);
void Insertionsort(int S[], int low, int hi);
void Quicksort_Insert_M3(int S[], int n, int p, int r);
int main()
{
srand (time(NULL));
// Declare all arrays used for testing
int S1_500[500];
int S2_500[500];
int S3_500[500];
int S1_300[300];
int S2_300[300];
int S3_300[300];
int S1_100[100];
int S2_100[100];
int S3_100[100];
int S1_8[8];
int S2_8[8];
int S3_8[8];
// Fill arrays with random integers
for(int i=0; i<500; i++)
{
S1_500[i] = rand()%1000;
S2_500[i] = rand()%1000;
S3_500[i] = rand()%1000;
}
for(int i=0; i<300; i++)
{
S1_300[i] = rand()%1000;
S2_300[i] = rand()%1000;
S3_300[i] = rand()%1000;
}
for(int i=0; i<100; i++)
{
S1_100[i] = rand()%500;
S2_100[i] = rand()%500;
S3_100[i] = rand()%500;
}
for(int i=0; i<8; i++)
{
S1_8[i] = rand()%100;
S2_8[i] = rand()%100;
S3_8[i] = rand()%100;
}
Quicksort_Insert_M3(S1_500,500,0,499);
compare_qs_m3_ins[0] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_500,500,0,499);
compare_qs_m3_ins[1] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_500,500,0,499);
compare_qs_m3_ins[2] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_300,300,0,299);
compare_qs_m3_ins[3] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_300,300,0,299);
compare_qs_m3_ins[4] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_300,300,0,299);
compare_qs_m3_ins[5] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_100,100,0,99);
compare_qs_m3_ins[6] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_100,100,0,99);
compare_qs_m3_ins[7] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_100,100,0,99);
compare_qs_m3_ins[8] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_8,8,0,7);
compare_qs_m3_ins[9] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_8,8,0,7);
compare_qs_m3_ins[10] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_8,8,0,7);
compare_qs_m3_ins[11] = comparisons;
comparisons = 0;
//for(int i=0; i<12; i++)
//cout << compare_qs_m3_ins[i] << endl;
for(int i=0;i<499;i++)
cout << S1_500[i] << endl;
}
int partition(int *S,int l, int u)
{
int x = S[l];
int j = l;
for(int i=l+1; i<=u; i++)
{
comparisons++;
if(S[i] < x)
{
j++;
swap(S[i],S[j]);
}
}
int p = j;
swap(S[l],S[p]);
return p;
}
void swap(int &val1, int &val2)
{
int temp = val1;
val1 = val2;
val2 = temp;
}
void exchange(int list[], int p, int q)
{
int temp = list[p];
list[p] = list[q];
list[q] = temp;
}
int Sort3(int list[], int p, int r)
{
int median = (p + r) / 2;
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
}
else
{
exchange(list,median,r);
}
}
else
;
}
else
{
comparisons++;
if(list[p] > list[r])
{
comparisons++;
if(list[median] < list[r])
{
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
}
else
{
exchange(list,p,r);
}
}
else
{
exchange(list,p,median);
}
}
return list[r];
}
void Insert(int *S, int k)
{
int key = S[k];
int j = k-1;
while(j>=0 && S[j] > key)
{
S[j+1] = S[j];
j--;
comparisons++;
}
comparisons++;
S[j+1] = key;
}
void Insertionsort(int S[], int low, int hi)
{
if((hi-low)+1>1)
Insertionsort(S,low+1,hi);
Insert(S,hi-low);
}
void Quicksort_Insert_M3(int S[], int n, int low, int hi)
{
if((hi-low)<=8)
Insertionsort(S,low,hi);
else
{
if(low < hi)
{
if((low+1) == hi)
{
comparisons++;
if(S[low] > S[hi])
swap(S[low],S[hi]);
}
else
{
Sort3(S,low,hi);
if((low+2)<hi)
{
swap(S[low+1],S[(low+hi)/2]);
int q = partition(S, low+1, hi-1);
Quicksort_Insert_M3(S, n, low, q-1);
Quicksort_Insert_M3(S, n, q+1, hi);
}
}
}
}
}
The function supposed to sort three array elements in ascending order doesn't:
int Sort3(int list[], int p, int r)
{
called only for p + 2 <= r
, so
int median = (p + r) / 2;
p < median < r
here. Let a = list[p]
, b = list[median]
and c = list[r]
.
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
So here we have a <= b
, c < b
and a < c
, together a < c < b
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
but you place them in order c, a, b
. Probably you intended to use if (list[r] < list[p])
there.
}
else
c <= a <= b
{
exchange(list,median,r);
so that arranges them in order a, c, b
.
}
}
else
;
}
else
Here, b < a
.
{
comparisons++;
if(list[p] > list[r])
{
c < a
comparisons++;
if(list[median] < list[r])
{
Then b < c < a
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
Yup, that's correct.
}
else
c <= b < a
{
exchange(list,p,r);
}
Okedoke.
}
else
{
b < a <= c
exchange(list,p,median);
Okay.
}
}
return list[r];
}
Why does this function return anything? You don't use the return value anyway.
这篇关于采用插入排序算法错误 - 阵列是不完全排序。的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!