快速排序 C 中的数组

Question

我正在尝试使用快速排序算法对包含 10 个整数的数组进行排序，下面是我的代码，它排序不正确，有人可以指出我可能犯的错误吗？

int partition(int arr[], int first, int last)
{
    int pivot = arr[first];
    int low = first;
    int i = first + 1;
    while(i <= last){
        if(arr[i] < pivot){
            low++;
            swap(&arr[i], &arr[low]);
        }
        i++;
    }
    swap(&arr[first], &arr[low]);
    return low;
}

void quick_sort(int arr[], int first, int last)
{
    int pivot_pos;
    if(first < last){
        pivot_pos = partition(arr, first, last);
        quick_sort(arr, first, pivot_pos-1);
        quick_sort(arr, pivot_pos+1, last);
    }
}

Answer 1

这是您的代码的检测版本。由于您没有提供 swap() 功能，所以我写了那个；我还写了 dump_data() 来打印一段数组的内容，还有一个 main() 用于测试。根据我所做的有限测试，排序有效。鉴于您说没有，我怀疑您的 swap() 代码可能有问题；或者你的测试工具代码有问题（或者我的测试恰好是有效的！）。

#include <stdio.h>

static inline void swap(int *a, int *b) { int c = *a; *a = *b; *b = c; }

static void dump_data(const char *tag, int *data, int first, int last)
{
    printf("%s: (%d:%d)\n", tag, first, last);
    for (int i = first; i <= last; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

static
int partition(int arr[], int first, int last)
{
    int pivot = arr[first];
    int low = first;
    int i = first + 1;
    while (i <= last)
    {
        if (arr[i] < pivot)
        {
            low++;
            swap(&arr[i], &arr[low]);
        }
        i++;
    }
    swap(&arr[first], &arr[low]);
    return low;
}

static
void quick_sort(int arr[], int first, int last)
{
    if (first < last)
    {
        dump_data("-->> QS", arr, first, last);
        int pivot_pos = partition(arr, first, last);
        printf("Pivot: arr[%d] = %d\n", pivot_pos, arr[pivot_pos]);
        quick_sort(arr, first, pivot_pos - 1);
        dump_data("-1-- QS", arr, first, pivot_pos - 1);
        quick_sort(arr, pivot_pos + 1, last);
        dump_data("-2-- QS", arr, pivot_pos + 1, last);
        dump_data("<<-- QS", arr, first, last);
    }
}

int main(void)
{
    int data[] = { 9, 2, 4, 7, 1, 3, 8, 6, 5 };
    int size = sizeof(data) / sizeof(data[0]);
    dump_data("Before", data, 0, size - 1);
    quick_sort(data, 0, size - 1);
    dump_data("After", data, 0, size - 1);
    return 0;
}

示例运行：

Before: (0:8)
 9 2 4 7 1 3 8 6 5
-->> QS: (0:8)
 9 2 4 7 1 3 8 6 5
Pivot: arr[8] = 9
-->> QS: (0:7)
 5 2 4 7 1 3 8 6
Pivot: arr[4] = 5
-->> QS: (0:3)
 3 2 4 1
Pivot: arr[2] = 3
-->> QS: (0:1)
 1 2
Pivot: arr[0] = 1
-1-- QS: (0:-1)

-2-- QS: (1:1)
 2
<<-- QS: (0:1)
 1 2
-1-- QS: (0:1)
 1 2
-2-- QS: (3:3)
 4
<<-- QS: (0:3)
 1 2 3 4
-1-- QS: (0:3)
 1 2 3 4
-->> QS: (5:7)
 7 8 6
Pivot: arr[6] = 7
-1-- QS: (5:5)
 6
-2-- QS: (7:7)
 8
<<-- QS: (5:7)
 6 7 8
-2-- QS: (5:7)
 6 7 8
<<-- QS: (0:7)
 1 2 3 4 5 6 7 8
-1-- QS: (0:7)
 1 2 3 4 5 6 7 8
-2-- QS: (9:8)

<<-- QS: (0:8)
 1 2 3 4 5 6 7 8 9
After: (0:8)
 1 2 3 4 5 6 7 8 9

更彻底的测试将自动验证结果实际上已排序，并且还有一个更大的数组，其中包含 post-排序检查确保未更改的虚拟元素，并且会有多个测试运行s 不同尺寸（包括0、1、2、3、4，然后是一些更大的尺寸）。这只是测试正确性。为了测试性能，你可以做一些事情，比如测试已经排序的数据，或者所有的值都相同，或者反向排序的数据，或者风琴管结构（∧和∨形式）等，在数据中有和没有重复（以及随机序列）。

Answer 2

根据您的代码，qsort 函数很好，即使分区有点难以理解！我猜你的问题是交换功能！这是一个使用易于理解的分区函数实现的工作代码：

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


/* the aim of the partition is to return the subscript of the exact */
/* position of the pivot when it is sorted */
// the low variable is used to point to the position of the next lowest element
int partition(int arr[], int first, int last)
{
    int pivot = arr[last]; // changed the pivot  
    int low = first;
    int i = first; // changed
    while(i <= last-1 ){// or you can do for(i=first;i<last;i++)
        if(arr[i] < pivot){
            swap(&arr[i], &arr[low]);
            low++; 
        }
        i++;
    }
    swap(&arr[last], &arr[low]);
    // after finishing putting all the lower element than the pivot 
    // It's time to put the pivot into its place and return its position
    return low;
}



void quick_sort(int arr[], int first, int last)
{
    int pivot_pos;
    if(first < last){
        pivot_pos = partition(arr, first, last);
        quick_sort(arr, first, pivot_pos-1);
        quick_sort(arr, pivot_pos+1, last);
    }
}

要测试程序，您可以使用下面的主要功能

int main(int argc, char *argv[])
{
    int tab[]={4,53,5,6,7,1};
    quick_sort(tab,0,5);
    int i=0;
    for (i=0;i<6;i++)
    {
        printf(" %d ",tab[i]);
    }
    printf("\n");

    return 0;
}

它将生成排序后的数组

1 4 5 6 7 53

如果你想看看究竟发生了什么这里是一个完整的代码:)

#include <stdio.h> 

void affiche(int *p,int size);
void swap(int *p, int a, int b)
{
    int temp=p[a];
        p[a]=p[b];
    p[b]=temp;
}

int partition(int *p, int start, int end)
{
    int pindex=start;
    int pivot=p[end];
    int i=0;
    for (i=start;i<=end-1;i++)
    {
        if (p[i]<pivot)
        {
            printf("swap p[%d] and p[%d]    pivot %d\n",i,pindex,pivot);
            swap(p,i,pindex);
            affiche(p,7);
            pindex++;
        }
    }
            printf("==>swap p[%d] and p[%d]  pivot %d\n",pindex,end,pivot);
    swap(p,pindex,end);
    return pindex;
}
void quicksort(int *p,int a,int b)
{
    if (a<b)
    {
        affiche(p,7);
        int pindex=partition(p,a,b);
        quicksort(p,a,pindex-1);
        quicksort(p,pindex+1,b);
    }
}

void affiche(int *p,int size)
{
int i=0;
for (i=0;i<size;i++)
{
    printf(" %d ",p[i]);
}
printf("\n");

}
int main(int argc, char *argv[])
{
  int tab[]={7,2,4,8,4,0,4};
    affiche(tab,7); 
    quicksort(tab,0,6);
     affiche(tab,7); 

    return 0;
}

快速排序 C 中的数组

Quicksort an array in C

c

algorithm

sorting

quicksort