使用qsort函数以交替方式对整数数组进行排序。
/ *我最近学习了qsortfunction。 这个c代码给出了错误的输出。 需要帮助。 问题 – 以交替方式对整数数组进行排序。 （偶数指数的元素和奇数指数的元素分别排序）OUTPUT- 0 4 1 2 5 8 7 5 9 3 10 5 * /
#include #include // This function is used in qsort to decide the relative order // of elements at addresses p and q. int comparator(const void *p, const void *q) { // Get the values at given addresses int l = *(const int *)p; int r = *(const int *)q; return (lr); } // A utility function to print an array void printArr(int arr[], int n) { int i; for (i = 0; i < n; i = i+1) printf("%d ", arr[i]); } // Driver program to test above function int main() { int arr[] = {1,4,7,2,9,3,0,8,6,5}; int size0 = sizeof(arr) / sizeof(arr[0]); int size1 = (int) ((float)sizeof(arr) / sizeof(arr[0]) / 2 + 0.5); int size2 = size0 - size1; qsort((void *)arr+1, size2, 2*sizeof(arr[0]), comparator); //sort odd positions qsort((void *)arr, size1, 2*sizeof(arr[0]), comparator); //sort even positions printf("Output array is\n"); printArr(arr, size0); printf("\n%d %d", size0, size1); return 0; } qsort ：
void qsort（void * ptr，size_t count，size_t size，int（* comp）（const void *，const void *））;
按升序对ptr指向的给定数组进行排序。 该数组包含大小字节的计数元素。 comp指向的函数用于对象比较。
ptr – 指向要排序的数组的指针
count – 数组中的元素数
size – 数组中每个元素的大小（以字节为单位）
comp – 比较函数，如果第一个参数小于第二个参数，则返回负整数值，
在你的程序中，你将每个元素的大小传递为2*sizeof(arr[0]) ，这导致8个字节，这是对qsort()错误输入。 因此，您输出的输出不正确。
可以使用qsort()对偶数/奇数元素进行排序。 但是，必须稍微更改设置才能完成此操作。
正如Peter提到的那样（我之前没有考虑过，因为我必须承认），偶数元素的排序会“破坏”奇数元素的结果，因为交换会考虑元素大小，表示为偶数和奇数元素对。
考虑到这一点，如果在第二次排序完成之前保存了第一次排序的结果，则可以为所有这些做出解决方案。
在我的示例中，我在第一次排序后复制了相关元素，并在第二次排序后将它们合并。
这是我的示例testQSortEvenOdd.c ：
#include #include #include int compEven(const int *p1, const int *p2) { return (p1[0] > p2[0]) - (p1[0] < p2[0]); } int compOdd(const int *p1, const int *p2) { return (p1[1] > p2[1]) - (p1[1] < p2[1]); } void printArray(size_t n, int *arr, int step) { for (; n--; arr += step) printf(" %d", *arr); putchar('\n'); } int main() { int arr[] = { 1, 4, 7, 2, 9, 3, 0, 8, 6, 5 }; enum { size = sizeof arr / sizeof *arr }; assert(!(size & 1)); /* sort odd positions */ qsort(arr, (size + 1) / 2, 2 * sizeof *arr, (int(*)(const void*, const void*))&compOdd); /* output of sorted array for odd positions */ puts("Odd elements sorted:"); printArray(size / 2, arr + 1, 2); int arrRes[(size + 1) / 2]; for (size_t i = 1; i < size; i += 2) arrRes[i / 2] = arr[i]; /* sort even positions */ qsort(arr, (size + 1) / 2, 2 * sizeof *arr, (int(*)(const void*, const void*))&compEven); /* output of sorted array for even positions */ puts("Even elements sorted:"); printArray((size + 1) / 2, arr, 2); /* merge array with copy */ for (size_t i = 1; i < size; i += 2) arr[i] = arrRes[i / 2]; puts("Merged elements:"); printArray(size, arr, 1); /* done */ return 0; }
在Windows 10（64位）上测试Cygwin：
$ gcc --version gcc (GCC) 6.4.0 $ gcc -std=c11 -o testQSortEvenOdd testQSortEvenOdd.c $ ./testQSortEvenOdd Odd elements sorted: 2 3 4 5 8 Even elements sorted: 0 1 6 7 9 Merged elements: 0 2 1 3 6 4 7 5 9 8 $
一些额外的说明：
-
我（和提问者）使用
qsort()，它一次处理两个连续的int值。 因此，必须授予该数组具有适当数量的元素。 （否则，qsort()要么进行qsort()访问，要么不能考虑最后一个元素。）为了考虑这个事实，我插入了assert(!(size & 1));可以读作“确保arrays具有偶数个元素”。
-
我决定将单独的函数
compEven()和compOdd()作为恕我直言，它简化了一些事情。 我将两者的签名都改为我的需要，并从gcc中得到关于错误function签名的抱怨（警告）。 因此，我将函数指针转换为期望的类型（使gcc无声）。 -
Jonathon给出了一个很好的暗示，使比较函数能够抵抗下溢问题。
return p1[0] - p2[0];当差值大于INT_MAX或小于INT_MIN时，会导致错误的结果。 相反，他建议使用：return (p1[0] > p2[0]) - (p1[0] < p2[0]);从来没有任何溢出/下溢问题。
这个怎么运作：
如果a < b ： (a > b) - (a < b) ⇒0 0 - 1 1⇒ -1
如果a == b ： (a > b) - (a < b) ⇒0 0 - 0 0⇒0
如果a > b ： (a > b) - (a < b) ⇒1 1 - 0 0⇒1
非常聪明的Jonathan Leffler - 我印象深刻。
qsort需要一个连续的内存块才能正常运行。
如果需要单独对奇数和偶数索引元素进行排序，可以先分离元素，对它们进行独立排序，然后合并这两个部分。
即使不分配任何额外的内存，您也可以这样做：
#include #include int less_int(const void *lhs, const void *rhs) { return *(const int *)lhs < *(const int *)rhs ? -1 : *(const int *)lhs > *(const int *)rhs ? 1 : 0; } int greater_int(const void *lhs, const void *rhs) { return *(const int *)lhs > *(const int *)rhs ? -1 : *(const int *)lhs < *(const int *)rhs ? 1 : 0; } void sort_ascending(int* arr, size_t n) { qsort(arr, n, sizeof *arr, less_int); } void sort_descending(int* arr, size_t n) { qsort(arr, n, sizeof *arr, greater_int); } inline void swap_int(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } size_t partition_odd_even(int* arr, size_t n ) { size_t n_odds = n - n / 2; for (size_t i = 1, j = n_odds + n_odds % 2; i < n_odds; i += 2, j += 2) { swap_int(arr + i, arr + j); } return n_odds; } void interleave_odd_even(int* arr, size_t n ) { size_t n_odds = n - n / 2; for (size_t i = 1; i < n_odds; ++i ) { for (size_t j = n_odds - i; j < n_odds + i; j += 2) { swap_int(arr + j, arr + j + 1); } } } void print_arr(int* arr, size_t n); int main(void) { int arr[] = {1, 4, 7, 2, 9, 3, 0, 8, 6, 5}; size_t arr_size = sizeof arr / sizeof *arr; print_arr(arr, arr_size); size_t n_odds = partition_odd_even(arr, arr_size); size_t n_evens = arr_size - n_odds; // print_arr(arr, arr_size); sort_ascending(arr, n_odds); // print_arr(arr, n_odds); sort_descending(arr + n_odds, n_evens); // print_arr(arr + n_odds, n_evens); interleave_odd_even(arr, arr_size); print_arr(arr, arr_size); return 0; } void print_arr(int* arr, size_t n) { for(size_t i = 0; i < n; ++i) { printf(" %d", arr[i]); } puts(""); }
这使：
1 4 7 2 9 3 0 8 6 5 0 8 1 5 6 4 7 3 9 2
编辑
如下面greybeard的评论中所述，由于合并部分为O（N²），因此上述代码实际上并不具有时间效率。 使用仅包含要以特定方式排序的元素的临时数组，以下程序仅需要O（N）额外时间和O（N / K）空间，其中K是所需的不同排序顺序的数量（2 in OP的问题）。
Jonathan Leffler还指出，可以更加通用，允许算法“处理3,4，...... N均匀交错的子arrays，可能每个都有不同的排序顺序” 。 我通过向sort函数传递一个指向比较函数的指针数组，在下面的代码片段中实现了它。
#include #include // compare functions typedef int (*PCMPFN)(const void*, const void*); int ascending_cmp_int(const void *lhs, const void *rhs) { return *(const int *)lhs < *(const int *)rhs ? -1 : *(const int *)lhs > *(const int *)rhs ? 1 : 0; } int descending_cmp_int(const void *lhs, const void *rhs) { return *(const int *)lhs > *(const int *)rhs ? -1 : *(const int *)lhs < *(const int *)rhs ? 1 : 0; } // This function is never called. Whithout knowing the actual implementation // of 'qsort' we can't make any assumption int untouched_cmp_int(const void *lhs, const void *rhs) { (void)lhs; // Those parameters are unused here, this is to avoid a warning (void)rhs; return 0; } // Copy the elements of the source array starting from index 'start' with stride 'step' size_t strided_split(int* dest, const int *src, size_t n, size_t start, size_t step) { size_t j = 0; for (size_t i = start; i < n; i += step, ++j) { dest[j] = src[i]; } return j; } // Inverse of the previous void strided_merge(int* dest, const int *src, size_t n, size_t start, size_t step) { for (size_t i = start, j = 0; j < n; i += step, ++j) { dest[i] = src[j]; } } // Apply different sort orders to different elements void alternate_sort(int* arr, const size_t n, PCMPFN comps[], const size_t k) { int tmp[n/k + 1]; // Please note that VLA are optional in C11 for ( size_t i = 0; i < k; ++i ) { if ( comps[i] == untouched_cmp_int ) continue; // First select the elements size_t n_copied = strided_split(tmp, arr, n, i, k); // then sort only them as needed qsort(tmp, n_copied, sizeof tmp[0], comps[i]); // Once sorted, copy back the elements in the source array strided_merge(arr, tmp, n_copied, i, k); } } void print_arr(const int* arr, const size_t n); int main(void) { int arr[] = {1, 4, 7, 2, 9, 3, 0, 8, 6, 5}; const size_t N = sizeof arr / sizeof *arr; print_arr(arr, N); PCMPFN compares[] = { descending_cmp_int, untouched_cmp_int, ascending_cmp_int }; const size_t K = sizeof compares / sizeof *compares; alternate_sort(arr, N, compares, K); print_arr(arr, N); return 0; } void print_arr(const int* arr, const size_t n) { for(size_t i = 0; i < n; ++i) { printf(" %d", arr[i]); } puts(""); }