按降序排序奇数,甚至按升序排序

给定一组随机整数,按降序对奇数元素进行排序,按升序对偶数进行排序。

输入示例: (1,4,5,2,3,6,7)
产出: (7,5,3,1,2,4,6)

优化时间复杂度。

它是哪种语言,C或C ++(我看到两个标签)

在C ++中,您可以使用具有适当排序function的std::sort() 。 在C中, qsort()工作方式类似:

 #include  #include  bool Order(int a, int b) { if (a%2 != b%2) return a%2; else return a%2 ? b 

这是ac#one-liner:

 int[] x = { 1,4,5,2,3,6,7 }; Array.Sort(x, (a, b) => a % 2 == 0 ? b % 2 == 0 ? a.CompareTo(b) : 1 : b % 2 == 0 ? -1 : -1 * a.CompareTo(b)); 

不要把它交给老师。 你的老师想看到你自己实施排序算法,所以他知道你可以做到并且知道你了解所涉及的内容。

在实践中,你(几乎)永远不会在工作中这样做。 您的平台已经具有高度优化的排序方法,并且您希望利用它们,无论是C#的Array.Sort().OrderBy()还是C ++ stl算法。 这段代码是为了向您展示如何在现实世界中解决这个问题,虽然如果我想通过代码审查,我可能不会在一条线上挤压它。

只是为了提供替代解决方案:

 #include  #include  bool is_odd(int x) { return x & 1; } int* rushakoff(int* begin, int* end) { int* middle = std::partition(begin, end, is_odd); std::sort(begin, middle, std::greater()); std::sort(middle, end, std::less()); return middle; } int main() { int array[] = {1,4,5,2,3,6,7}; rushakoff(array, array + 7); } 

也许不那么优化,但可读性很强。 这也很重要;-)

 // Sort with a custom comparison function // returns -1 if a before b, 0 if a==b, 1 if a after b int _cmp(a,b) { if (a % 2) == 0 { if (b % 2) == 0 { return (a>b) ? 1 : (a==b) 0 : -1; # Even(a) vs Even(b) } else { return 1; # Even(a) vs Odd(b) all evens are after all odds } } else { if (b % 2) == 0 { return -1; # Odd(a) vs Even(b) all odds are before all evens } else { return (b>a) ? 1 : (a==b) 0 : -1; # Odd(a) vs Odd(b) has reverse order } } } 

使用整数作为排序目标,您可以使用计数排序和一点点关注将其转换为O(n)排序。

曾几何时,这段代码将被添加到SO文档项目中。 然后没有文档项目,所以现在可以去这里。 这是不悔改的C代码。

分别对奇数和偶数进行排序的主题有很多变化:

  1. 在下降之前奇数上升
  2. 甚至在上升之前奇数下降
  3. 甚至在奇数下降之前上升
  4. 甚至在奇数上升之前下降
  5. 在提升之前奇数上升
  6. 在下降之前奇数下降
  7. 甚至在奇数上升之前上升
  8. 甚至在奇数下降之前下降

下面的代码显示了选项1-4 – 选项5-8很容易从这些中创建(不要对奇数与偶数进行最终测试;选择正确的升序或降序比较):

 #include  #include  #include  /* odd numbers in ascending order before even numbers in descending order */ static int oddasc_evendesc(const void *vp1, const void *vp2) { int v1 = *(int *)vp1; int v2 = *(int *)vp2; if ((v1 & 1) != (v2 & 1)) { /* One odd, one even */ if (v1 & 1) return -1; /* Odd is smaller */ return +1; } /* Both odd or both even */ if ((v1 & 1) == 1) return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0; /* Ascending */ return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0; /* Descending */ } /* even numbers descending before odd numbers ascending */ static int evendesc_oddasc(const void *vp1, const void *vp2) { int v1 = *(int *)vp1; int v2 = *(int *)vp2; if ((v1 & 1) != (v2 & 1)) { /* One odd, one even */ if (v1 & 1) return +1; /* Odd is larger */ return -1; } /* Both odd or both even */ if ((v1 & 1) == 1) return (v1 > v2) - (v1 < v2); /* Ascending */ return (v1 < v2) - (v1 > v2); /* Descending */ } /* odd numbers in descending order before even numbers in ascending order */ static int odddesc_evenasc(const void *vp1, const void *vp2) { int v1 = *(int *)vp1; int v2 = *(int *)vp2; if ((v1 & 1) != (v2 & 1)) { /* One odd, one even */ if (v1 & 1) return -1; /* Odd is smaller */ return +1; } /* Both odd or both even */ if ((v1 & 1) == 1) return (v1 < v2) ? +1 : (v1 > v2) ? -1 : 0; /* Descending */ return (v1 < v2) ? -1 : (v1 > v2) ? +1 : 0; /* Ascending */ } /* even numbers ascending before odd numbers descending */ static int evenasc_odddesc(const void *vp1, const void *vp2) { int v1 = *(int *)vp1; int v2 = *(int *)vp2; if ((v1 & 1) != (v2 & 1)) { /* One odd, one even */ if (v1 & 1) return +1; /* Odd is larger */ return -1; } /* Both odd or both even */ if ((v1 & 1) == 1) return (v1 < v2) - (v1 > v2); /* Descending */ return (v1 > v2) - (v1 < v2); /* Ascending */ } static void dump_array(const char *tag, int num, int *data) { printf("%s:\n", tag); int i; const char *pad = ""; for (i = 0; i < num; i++) { printf("%s%+3d", pad, data[i]); pad = " "; if (i % 10 == 9) { putchar('\n'); pad = ""; } } if (i % 10 != 0) putchar('\n'); /* End partial line */ putchar('\n'); /* Blank line */ } int main(void) { int data1[] = { /* random -n 80 -- -99 99 | commalist -b ' ' -n 10 */ +39, +36, +78, -92, +63, -21, -51, +49, 0, -77, -10, -49, -98, -17, +60, +83, +30, -97, -68, +86, +70, +84, -56, +3, +33, -34, +14, -40, -72, -86, -95, -87, -73, -20, -72, -86, -3, -71, -55, -80, -60, -4, -26, -64, -31, -84, -79, +25, +41, +80, -54, -51, +24, -48, +13, +61, -99, +60, -2, +16, -66, -30, +24, +88, +5, -77, +13, +3, +16, -69, -60, +26, +51, +16, -13, +71, -9, -2, +51, +72, }; enum { NUM_DATA = sizeof(data1) / sizeof(data1[0]) }; int data2[NUM_DATA]; int data3[NUM_DATA]; int data4[NUM_DATA]; memmove(data2, data1, sizeof(data1)); memmove(data3, data1, sizeof(data1)); memmove(data4, data1, sizeof(data1)); printf("Sort odd numbers ascending before even numbers descending\n"); dump_array("Before", NUM_DATA, data1); qsort(data1, NUM_DATA, sizeof(data1[0]), oddasc_evendesc); dump_array("After", NUM_DATA, data1); printf("Sort even numbers descending before odd numbers ascending\n"); dump_array("Before", NUM_DATA, data2); qsort(data2, NUM_DATA, sizeof(data2[0]), evendesc_oddasc); dump_array("After", NUM_DATA, data2); printf("Sort odd numbers descending before even numbers ascending\n"); dump_array("Before", NUM_DATA, data3); qsort(data3, NUM_DATA, sizeof(data3[0]), odddesc_evenasc); dump_array("After", NUM_DATA, data3); printf("Sort even numbers ascending before odd numbers descending\n"); dump_array("Before", NUM_DATA, data4); qsort(data4, NUM_DATA, sizeof(data4[0]), evenasc_odddesc); dump_array("After", NUM_DATA, data4); return 0; } 

输出:

 Sort odd numbers ascending before even numbers descending Before: +39 +36 +78 -92 +63 -21 -51 +49 +0 -77 -10 -49 -98 -17 +60 +83 +30 -97 -68 +86 +70 +84 -56 +3 +33 -34 +14 -40 -72 -86 -95 -87 -73 -20 -72 -86 -3 -71 -55 -80 -60 -4 -26 -64 -31 -84 -79 +25 +41 +80 -54 -51 +24 -48 +13 +61 -99 +60 -2 +16 -66 -30 +24 +88 +5 -77 +13 +3 +16 -69 -60 +26 +51 +16 -13 +71 -9 -2 +51 +72 After: -99 -97 -95 -87 -79 -77 -77 -73 -71 -69 -55 -51 -51 -49 -31 -21 -17 -13 -9 -3 +3 +3 +5 +13 +13 +25 +33 +39 +41 +49 +51 +51 +61 +63 +71 +83 +88 +86 +84 +80 +78 +72 +70 +60 +60 +36 +30 +26 +24 +24 +16 +16 +16 +14 +0 -2 -2 -4 -10 -20 -26 -30 -34 -40 -48 -54 -56 -60 -60 -64 -66 -68 -72 -72 -80 -84 -86 -86 -92 -98 Sort even numbers descending before odd numbers ascending Before: +39 +36 +78 -92 +63 -21 -51 +49 +0 -77 -10 -49 -98 -17 +60 +83 +30 -97 -68 +86 +70 +84 -56 +3 +33 -34 +14 -40 -72 -86 -95 -87 -73 -20 -72 -86 -3 -71 -55 -80 -60 -4 -26 -64 -31 -84 -79 +25 +41 +80 -54 -51 +24 -48 +13 +61 -99 +60 -2 +16 -66 -30 +24 +88 +5 -77 +13 +3 +16 -69 -60 +26 +51 +16 -13 +71 -9 -2 +51 +72 After: +88 +86 +84 +80 +78 +72 +70 +60 +60 +36 +30 +26 +24 +24 +16 +16 +16 +14 +0 -2 -2 -4 -10 -20 -26 -30 -34 -40 -48 -54 -56 -60 -60 -64 -66 -68 -72 -72 -80 -84 -86 -86 -92 -98 -99 -97 -95 -87 -79 -77 -77 -73 -71 -69 -55 -51 -51 -49 -31 -21 -17 -13 -9 -3 +3 +3 +5 +13 +13 +25 +33 +39 +41 +49 +51 +51 +61 +63 +71 +83 Sort odd numbers descending before even numbers ascending Before: +39 +36 +78 -92 +63 -21 -51 +49 +0 -77 -10 -49 -98 -17 +60 +83 +30 -97 -68 +86 +70 +84 -56 +3 +33 -34 +14 -40 -72 -86 -95 -87 -73 -20 -72 -86 -3 -71 -55 -80 -60 -4 -26 -64 -31 -84 -79 +25 +41 +80 -54 -51 +24 -48 +13 +61 -99 +60 -2 +16 -66 -30 +24 +88 +5 -77 +13 +3 +16 -69 -60 +26 +51 +16 -13 +71 -9 -2 +51 +72 After: +83 +71 +63 +61 +51 +51 +49 +41 +39 +33 +25 +13 +13 +5 +3 +3 -3 -9 -13 -17 -21 -31 -49 -51 -51 -55 -69 -71 -73 -77 -77 -79 -87 -95 -97 -99 -98 -92 -86 -86 -84 -80 -72 -72 -68 -66 -64 -60 -60 -56 -54 -48 -40 -34 -30 -26 -20 -10 -4 -2 -2 +0 +14 +16 +16 +16 +24 +24 +26 +30 +36 +60 +60 +70 +72 +78 +80 +84 +86 +88 Sort even numbers ascending before odd numbers descending Before: +39 +36 +78 -92 +63 -21 -51 +49 +0 -77 -10 -49 -98 -17 +60 +83 +30 -97 -68 +86 +70 +84 -56 +3 +33 -34 +14 -40 -72 -86 -95 -87 -73 -20 -72 -86 -3 -71 -55 -80 -60 -4 -26 -64 -31 -84 -79 +25 +41 +80 -54 -51 +24 -48 +13 +61 -99 +60 -2 +16 -66 -30 +24 +88 +5 -77 +13 +3 +16 -69 -60 +26 +51 +16 -13 +71 -9 -2 +51 +72 After: -98 -92 -86 -86 -84 -80 -72 -72 -68 -66 -64 -60 -60 -56 -54 -48 -40 -34 -30 -26 -20 -10 -4 -2 -2 +0 +14 +16 +16 +16 +24 +24 +26 +30 +36 +60 +60 +70 +72 +78 +80 +84 +86 +88 +83 +71 +63 +61 +51 +51 +49 +41 +39 +33 +25 +13 +13 +5 +3 +3 -3 -9 -13 -17 -21 -31 -49 -51 -51 -55 -69 -71 -73 -77 -77 -79 -87 -95 -97 -99 

此代码在我的SOQ (堆栈溢出问题)存储库中的GitHub上可用,作为doc / qsort子目录中的文件oddascevendesc.c (现在用词不当)。