c - 快速排序实现在 C 中不排序

Question

我已经尝试用 C 语言编写快速排序实现了 2 天，但它不起作用。我的意思是，它确实可以编译，但输出不是我所期望的。

我一直在研究一本《数据结构》书，无论如何，它已翻译成葡萄牙语，这是我的母语......我将在下面将说明与我的代码一起传递。

QuickSort Image Partition Image

//
//  Quick sort V2.c
//  IFTM Exercises
//
//  Created by Lelre Ferreira on 7/9/19.
//  Copyright © 2019 Lelre Ferreira. All rights reserved.
//

#define size 5
#include <stdio.h>

void printfArrays(int *array);
void receiveArray(int *array);
int QuickSortPartition(int *array, int begin, int end);
void QuickSortFunction(int *array, int begin, int end);


int main (int argc, const char * argv[]){

    int array[size];

    receiveArray(array);
    printfArrays(array);

    return 0;
}

void receiveArray(int* array){

    int i = 0;
    for (i = 0; i < size; i++) {
        printf("Insert value of [%d]: ", i);
        scanf("%d", &array[i]);
    }
}

void printfArrays(int *array){

    int i = 0;
    for (i = 0; i < size; i++) {
        printf("Value sorted: %d\n", array[i]);
    }
}

int QuickSortPartition(int *array, int begin, int end){


    int pivot = array[end];
    int i = (begin - 1), j = 0;

    for (j = begin; j <= end - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            array[i] = array[j];
        }
    }
    array[i + 1] = array[end];
    return (i + 1);
}

void QuickSortFunction(int *array, int begin, int end){

    if (begin < end) {
        int pivot = QuickSortPartition(array, begin, end);
        QuickSortPartition(array, begin, pivot - 1);
        QuickSortPartition(array, pivot + 1, end);
    }

}

Answer 1

当您编写一个函数时，请在程序中使用它之前对其进行测试。

函数 QuickSortPartition 显然是错误的。

考虑以下演示程序与您的函数实现

#include <stdio.h>

int QuickSortPartition(int *array, int begin, int end){


    int pivot = array[end];
    int i = (begin - 1), j = 0;

    for (j = begin; j <= end - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            array[i] = array[j];
        }
    }
    array[i + 1] = array[end];
    return (i + 1);
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    QuickSortPartition( a, 0, ( int )( N - 1 ) );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}    

它的输出是

5 4 2 1 3 
2 1 3 1 3 

您需要交换函数中的值，而不是使用简单的赋值。例如

#include <stdio.h>

size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
    const int pivot = array[end];

    size_t i = begin - 1;

    for ( size_t j = begin; j < end; j++ ) 
    {
        if ( array[j] <= pivot ) 
        {
            int tmp = array[++i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

    int tmp = array[++i];
    array[i] = array[end];
    array[end] = tmp;

    return i;
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    size_t partition = QuickSortPartition( a, 0, N - 1 );

    printf( "%zu: ", partition );
    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}    

它的输出是

5 4 2 1 3 
2: 2 1 3 4 5

对于索引，我使用了 size_t 类型(您也应该这样做)而不是 int 类型。

在函数 QuickSortFunction 中，您需要调用它本身，而不是函数 QuickSortPartition。

void QuickSortFunction(int *array, size_t begin, size_t end){

    if (begin < end) {
        size_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }

}

考虑到函数 QuickSortPartition 声明中的初始化

int i = (begin - 1), j = 0;
        ^^^^^^^^^^^

很糟糕。 (似乎每个人都从一个坏例子中复制算法:))。当所有元素都小于或等于pivot的值时，该函数效率较低。

您还可以编写一个单独的函数来交换数组的两个元素。

下面有一个演示程序，展示了如何改进 QuickSortPartition 函数的代码。

#include <stdio.h>

void swap( int *a, int *b )
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
    const int pivot = array[end];

    size_t i = begin;

    for ( size_t j = begin; j < end; j++ ) 
    {
        if ( array[j] <= pivot ) 
        {
            if ( i != j ) swap( &array[i], &array[j] );
            ++i;
        }
    }

    if ( i != end ) swap( &array[i], &array[end] );

    return i;
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    size_t partition = QuickSortPartition( a, 0, N - 1 );

    printf( "%zu: ", partition );
    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}