c - 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 为偶数，则奇数索引和偶数索引处的元素数量相等。所以

  no_of_even_elements = no_of_odd_elements = n/2
  

• 如果 size_of_array 为奇数，则奇数索引和偶数索引处的元素数量相等。所以

  no_of_even_elements = (n/2)+1
  no_of_odd_elements = n/2 
  

• 再创建两个数组。说 odd[no_of_odd_elements] 和 even[no_of_even_elements]

• 第一个数组存储奇数 索引处的元素，第二个数组存储偶数 索引处的元素。
• 使用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];
      }
  }
  

希望这有帮助:)