Quicksort 中不同的偶数和奇数排序

Question

我遇到了这样一个算法问题：我需要让 Quicksort 像这样工作：

1) 数组索引为奇数时，应从小到大排序

2) 即使是索引也应该从大到小排序。

所以如果我们有数组：2 5 1 3 4 0 6 2 5，我们应该得到这样的东西：6 0 5 2 4 3 2 5 1

这是我在 C 中实现的快速排序：

    void quicksort(int tab[], int start, int end) {
    int i=start;
    int j=end;
    int x=tab[(i+j)/2];
    do {
        while(tab[i]<x) i++;
        while(tab[j]>x) j--;
        if(i<=j) {
            int tmp=tab[i];
            tab[i]=tab[j];
            tab[j]=tmp;
            i++;
            j--;
        }
    } while(i<=j);
    if(start<j) quicksort(tab,start,j);
    if(i<end) quicksort(tab,i,end);
    }

是否可以只使用一个快速排序来实现它，或者我应该尝试创建两个函数：一个对奇数索引进行排序，第二个对偶数索引进行排序？

Answer 1

Is it possible to make it using just one quicksort or I should try sth like creating two functions: one will sort odd indexes and second one even indexes?

quick sort 通常用于按升序或降序顺序对元素进行排序，所以我认为不会仅对所需模式 中的元素进行排序很有用（既不升序也不降序，甚至在答案数组中也不能保证特定模式） 仅使用 quick sort.

In my opinion creating an additional custom function say required_sort() and sort elements as required along with the help of qucksort() (here in my case it sorts in ascending order) would be the best way to go

void required_sort(int array[], int size_of_array)
{
    int no_of_even_elements, no_of_odd_elements
    if(size_of_array%2 == 0)
    {
        no_of_even_elements = no_of_odd_elements = n/2;
    }    
    else
    {
        no_of_even_elements = (n/2)+1;
        no_of_odd_elements = n/2;     
    }

    int even[no_of_even_elements], odd_even[elements];

    //inserting elements into new arrays
    for(int index=0; index < size_of_array; index++)
    {
        if(index%2 == 0)
        {
            even[index/2] = array[index];
        }
        else
        { 
            odd[index/2] = array[index];
        }
    }

    //call quicksort function to sort the even[] array in ascending order
    //call quicksort function to sort the odd[] array in ascending order

    for(int index=0; index < size_of_array; index++)
    {
        if(index%2 == 0)
        {
            array[index] = even[(no_of_even_elements)-(index/2)];
        }
        else
        {
           array[index] = odd[index/2];
        }
    }

}

required_sort 的解释 :

首先检查size_of_array是偶数还是奇数
如果 size_of_array 是 even 则奇数索引和偶数索引处的元素数量相等。所以
```
no_of_even_elements = no_of_odd_elements = n/2
```
如果 size_of_array 是 odd 则奇数索引和偶数索引处的元素数量相等。所以
```
no_of_even_elements = (n/2)+1
no_of_odd_elements = n/2 
```
再创建两个数组。说 odd[no_of_odd_elements] 和 even[no_of_even_elements]
在第一个数组中存储 odd 索引处的元素，在第二个数组中存储 even 索引处的元素。
使用quicksort()（升序）对两个数组进行排序

现在使用 for 循环以这种方式更新原始 array[] 的值：

for(int index=0; index < size_of_array; index++)
{
    if(index%2 == 0)
    {
        array[index] = even[(no_of_even_elements)-(index/2)];
    }
    else
    {
       array[index] = odd[index/2];
    }
}

希望这对您有所帮助:)

Answer 2

您可以参数化您的快速排序算法以支持 (1) 基于步长的部分排序和 (2) 排序方向。

void quicksort2(int tab[], int start, int end, int step, int (*comparer)(int, int))

引入参数step，用于访问距离start和end
step个元素的元素
每当更改索引时，使用步长而不是 1：i+=step;、j-=step; 等等。

为了支持步长 > 1 的不均匀索引，计算枢轴的中间元素变得稍微复杂一些：int mid = (end / step - start / step) / 2 * step + start; int x=tab[mid];

start 和 end 索引必须是 step 的倍数。
将比较更改为 comparer 函数而不是本机 < 和 > 运算符用法

比较器函数预计 return a < b 的负值和 b < a 的正值。用法：while(comparer(tab[i],x) < 0) // ...

综合起来：

void quicksort(int tab[], int start, int end, int step, int (*comparer)(int, int))
{
    int i=start;
    int j=end;
    int mid = (end / step - start / step) / 2 * step + start;
    int x=tab[mid];
    do {
        while(comparer(tab[i],x) < 0) i+=step;
        while(comparer(tab[j],x) > 0) j-=step;
        if(i<=j) {
            int tmp=tab[i];
            tab[i]=tab[j];
            tab[j]=tmp;
            i+=step;
            j-=step;
        }
    } while(i<=j);
    if(start<j) quicksort(tab,start,j, step, comparer);
    if(i<end) quicksort(tab,i,end, step, comparer);
}

我尽量贴近您最初的本机快速排序实现，因此这段代码看起来应该很熟悉。

这可用于执行所需的排序，如下所示：

为升序和降序定义比较器函数。

int smaller(int a, int b)
{
    return a - b;
}

int bigger(int a, int b)
{
    return b - a;
}

并为两个子排序调用两次快速排序

int values[] = { 2, 5, 1, 3, 4, 0, 6, 2, 5 };
quicksort(values, 0, 8, 2, &smaller);
quicksort(values, 1, 7, 2, &bigger);

注意正确设置开始索引和结束索引，或者在快速排序函数中为它们添加健全性检查

Quicksort 中不同的偶数和奇数排序

Different even and odd sorting in Quicksort

c

sorting

quicksort