arrays - 对数组中大于 n 的元素按升序排序并在 C 中降序排列

Question

我需要按升序和降序对 C 中的数组进行排序。

大于 n 的值需要排在最前面并按升序排列，任何小于 n 的值都将排在最后并按降序排列。将有未知数量的输入，下面的代码不反射(reflect)实际输入，仅作为示例。

#include <stdio.h>

void main(){

int n = 4;
int arr[] = {5, 6, 2, 8, 3}

结果输出为 5,6,8,3,2

我的解决方案:

if (arr[0] >n){
  for (i = 0; i < arrSize; i++){
     for (j = 0; i < arrSize; j++){
     if ( arr[j] < arr[i] && arr[i] < n){
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
     }

这部分对于第一部分(数组元素 > n)工作正常，但我在后面部分遇到了问题。从前面的代码继续我的解决方案:

     else if(arr[i] < n){
      int temp2 = arr[n-1];
      arr[n-1] = arr[i];
      arr[i] = temp2;
     }
     

不幸的是，这只适用于 n 以下的元素，如果它们被连续放置在输入中，否则排序失败。

非常感谢任何帮助或引用我可以阅读的有关此排序的主题。抱歉，如果有人问我，我在 stackoverflow 搜索中没有找到任何类似的东西

Answer 1

您可以通过 3 个步骤解决您的问题:

• 首先将数组分成大于n 的元素和小于或等于n 的元素。
• 然后将前半部分按升序排序
• 将后半部分降序排列

void swap(int *array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void split_sort(int *array, int size, int n) {
    int i, j, middle;

    /* partition the array using n as a pivot value */
    for (i = 0, j = size; i < j;) {
        while (i < j && array[i] > n)
            i++;
        while (j > i && array[j - 1] <= n)
            j--;
        if (i >= j)
            break;
        swap(array, i++, --j);
    }
    middle = i;
    /* sort the left half in ascending order with a simplistic algorithm */
    for (i = 1; i < middle; i++) {
        for (j = 0; j < i; j++) {
            if (array[j] > array[i]) {
                swap(array, i, j);
            }
        }
    }
    /* sort the right half in descending order with a simplistic algorithm */
    for (i = middle + 1; i < size; i++) {
        for (j = middle; j < i; j++) {
            if (array[j] < array[i]) {
                swap(array, i, j);
            }
        }
    }
}