-1

这是一些工作代码，它实现了快速排序算法的修改版本，该算法使用插入排序来处理数组大小n > 8。我的测试数组排序不完全正确，我认为它必须与我的Insertionsortand实现有关Insert。

Insertionsort递归算法的一般形式是：

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;
}

这是我的完整工作代码，但排序不完全正确：

#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);
                }
            }
        }
    }
}
4

2 回答 2

1

应该按升序对三个数组元素进行排序的函数不会：

int Sort3(int list[], int p, int r)
{

只需要p + 2 <= r, 所以

    int median = (p + r) / 2;

p < median < r这里。让和。a = list[p]_b = list[median]c = list[r]

    comparisons++;
    if(list[p] <= list[median])
    {
        comparisons++;
        if(list[median]>list[r])
        {
            comparisons++;
            if(list[p]<list[r])
            {

所以在这里我们有a <= b,c < b和a < c, 一起a < c < b

                int temp = list[p];
                list[p] = list[r];
                list[r] = list[median];
                list[median] = temp;

但你把它们按顺序排列c, a, b。可能您打算在if (list[r] < list[p])那里使用。

            }
            else

c <= a <= b

            {
                exchange(list,median,r);

以便按顺序排列它们a, c, b。

            }
        }
        else
            ;

    }
    else

在这里，b < a。

    {
        comparisons++;
        if(list[p] > list[r])
        {

c < a

            comparisons++;
            if(list[median] < list[r])
            {

然后b < c < a

                int temp = list[p];
                list[p] = list[median];
                list[median] = list[r];
                list[r] = temp;

是的，没错。

            }
            else

c <= b < a

            {
                exchange(list,p,r);
            }

奥克多克。

        }
        else
        {

b < a <= c

            exchange(list,p,median);

好的。

        }

    }


    return list[r];
}

为什么这个函数会返回任何东西？无论如何，您都不使用返回值。

于 2012-11-21T16:29:05.390 回答
0

“递归插入排序算法的一般形式是”——如果你需要一个头递归算法，是的，否则更好的版本是：

void Insertionsort(int S[], int i, int n)
{
    Insert(S, i, n);
    if(i < n)
        Insertionsort(S, i+1, n);
}

这更容易理解。此外，您不妨将 Insert 的主体放入 Insertionsort。

我不会尝试找出您过于复杂的快速排序版本。一个不错的快速排序大约是 20 行或更少（像这样 - www.algolist.net/Algorithms/Sorting/Quicksort）（并添加另外 10 行或更少用于插入排序）。我建议通过查看另一个实现并重写您的实现来更好地理解。

我相信这可以作为您之前问题的延伸提出。

于 2012-11-21T14:10:39.500 回答