我有一个排序2d数组的任务，但对我来说真的很难。我不知道自己在哪里犯错。
最好使用while循环而不是for循环
这是任务：
输入尺寸为n的方阵。
主对角线以下的元素按升序排序。
主对角线上方的元素按降序排序。
主要对角线元素排序：
第一个偶数按升序排列。
然后按降序排列奇数。
排序前的矩阵：
1 5 4 7 2
4 8 5 9 0
2 7 6 5 3
3 1 7 4 9
2 5 1 7 3
排序后的矩阵：
4 9 9 7 5
1 6 5 5 4
1 2 8 3 2
2 3 4 3 0
5 7 7 7 1
这是代码：
#include <stdio.h>
#include <stdlib.h>
int main () {
int n, i, j, a, k, l, o;
int m[50][50];
printf ("Enter n of square matrix : \n");
scanf ("%d", &n);
printf ("Enter rows and columns numbers n :\n");
i = 0;
while (i < n) {
j = 0;
while (j < n) {
scanf ("%d", &m[i][j]);
j++;
}
i++;
}
printf ("Matrix before sorting \n");
i = 0;
while (i < n) {
j = 0;
while (j < n) {
printf ("%d ", m[i][j]);
j++;
}
printf ("\n");
i++;
}
printf ("Matrix after sorting \n");
i = 0;
while (i < n) {
j = 0;
while (j < n) {
if (i < j) {
k = j + 1;
while (k < (n - 1)) {
if (m[i][k] < m[i][k + 1]) {
a = m[i][k];
m[i][k] = m[i][k + 1];
m[i][k + 1] = a;
}
k++;
}
}
else if (i > j) {
l = i + 1;
while (l < (n - 1)) {
if (m[l][j] > m[l + 1][j]) {
a = m[l][j];
m[l][j] = m[l + 1][j];
m[l + 1][j] = a;
}
l++;
}
}
else {
if (m[i][j] % 2 == 0 && m[i + 1][j + 1] % 2 == 0) {
if (m[i][j] > m[i + 1][j + 1]) {
a = m[i][j];
m[i][j] = m[i + 1][j + 1];
m[i + 1][j + 1] = a;
}
}
if (m[i][j] % 2 != 0 && m[i + 1][j + 1] % 2 != 0) {
if (m[i][j] < m[i + 1][j + 1]) {
a = m[i][j];
m[i][j] = m[i + 1][j + 1];
m[i + 1][j + 1] = a;
}
}
}
j++;
}
i++;
}
i = 0;
while (i < n) {
j = 0;
while (j < n) {
printf ("%d ", m[i][j]);
j++;
}
printf ("\n");
i++;
}
return 0;
}
于2018年2月2日更改
我需要编写简单的代码，而没有size_t，buffer和指针等内容。
我做了一些代码，但是当我使用奇数个矩阵时，它将无法正常工作（例如5x5），我不知道我在哪里犯错。
#include <stdio.h>
#include <stdlib.h>
int main()
{
static int a[500][500];
int i,j,l,k,m,b,n,t,d,c;
printf("Unesite n kvadratne matrice : \n");
scanf("%d" , &n);
printf("Matrica pre sortiranja \n \n");
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n ; j++)
{
scanf("%d",&a[ i ][ j ]);
}
}
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
if ( i > j ) // ispod dijagonale
{
for ( l = i ; l < n ; l++)
{
for ( k = j ; k < l ; k++ )
{
if ( a[ i ][ j ] > a[ l ][ k ] && k < l )
{
t = a[ i ][ j ];
a[ i ][ j ] = a[ l ][ k ];
a[ l ][ k ] = t ;
}
}
}
}
if ( i < j ) // iznad dijagonale
{
for ( m = i ; m < n ; m++)
{
for ( b = j ; b < n ; b++)
{
if ( a[ i ][ j ] < a[ m ][ b ] && m < b )
{
t = a[ i ][ j ];
a[ i ][ j ] = a[ m ][ b ];
a[ m ][ b ] = t ;
}
}
}
}
if ( i == j ) // dijagonala
{
for (d = i ; d < n ; d++)
{
for ( c = d + 1 ; c < n ; c++)
{
if ( a[ d ] [ d ] % 2 != 0 && a[ c ] [ c]%2 == 0 )
{
t = a[ d ] [ d ] ;
a[ d ] [ d ] = a[ c ] [ c] ;
a[ c ] [ c] = t ;
}
}
}
for (d = i ; d < n ; d++)
{
for ( c = d + 1 ; c < n ; c++)
{
if ( a[ d ][ d ] %2 == 0 && a[ c ][ c ] %2 ==0
&& a[ d ][ d ] > a [ c ][ c ])
{
t = a[ d ] [ d ] ;
a[ d ] [ d ] = a[ c ] [ c] ;
a[ c ] [ c] = t ;
}
else if ( a[ d ][ d ] %2 != 0 && a[ c ][ c ] %2
!=0 && a[ d ][ d ] < a [ c ][ c ])
{
t = a[ d ] [ d ] ;
a[ d ] [ d ] = a[ c ] [ c] ;
a[ c ] [ c] = t ;
}
}
}
}
}
}
printf("Posle sortiranja : \n");
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n;j++)
{
printf(" %d ",a[i][j]);
}
printf("\n \n");
}
return 0;
}
最佳答案
这是一个有趣的问题。正如我在comment中概述的那样，我认为该解决方案必须通过三个单独的排序操作来解决：
对角线排序
排序上三角
排序下三角
这些操作发生的顺序无关紧要。确实，如果要与线程并行运行这三种类型，则可以这样做。
对角线排序的诀窍是编写一个比较函数，以确保所有偶数都在所有奇数之前（因此，每个偶数都被认为小于任何奇数），但是当比较两个偶数时，它们将被排序升序，而比较两个奇数时，它们按降序排序。 cmp_aeod()函数（升序为奇数降序）可以实现此目的。
可以仅使用cmp_asc()和cmp_dsc()函数之一，但是同时拥有这两个函数则更直接。 (x > y) - (x < y)习惯用法总是进行两次比较，但是如果x大于y，则第一项为1，第二项为0，结果为1。如果x小于y，则第一项为0，第二项为1，结果为-1。当然，如果x等于y，则两个术语均为0，结果也为0。
排序三角形的关键是要注意排序算法适用于连续的数组，但是三角形中的数据不是连续的。给出的解决方案是将三角形中的元素从0编号为m，其中m = (n * (n - 1)) / 2，假定方阵是n乘以n。然后，代码需要能够识别matrix中的哪些索引以访问相应的元素编号，并且此映射由三角排序函数中的ut或lt矩阵完成。我无法计算出一个非迭代公式来将三角形中的序列号转换为行/列对，因此创建了映射矩阵。这给出了辅助存储的大小为O（N2）。
使用的排序算法是简单的二次排序；您可以根据需要将其更改为更复杂的算法（快速排序等）。
/*
** + Enter a square matrix of dimensions n .
** + Elements below main diagonal sort in ascending order.
** + Elements above main diagonal sort in descending order.
** + Elements on main diagonal sort :
** - first even numbers in ascending order.
** - then odd numbers in descending order.
*/
static inline int cmp_asc(int x, int y) { return (x > y) - (x < y); }
static inline int cmp_dsc(int x, int y) { return (x < y) - (x > y); }
static inline int cmp_eaod(int x, int y)
{
int px = x & 1;
int py = y & 1;
if (px != py)
return px - py;
if (px == 1)
return cmp_dsc(x, y);
return cmp_asc(x, y);
}
#include <stdio.h>
static void print_matrix(const char *tag, size_t r, size_t c, int matrix[r][c])
{
printf("%s:\n", tag);
for (size_t i = 0; i < r; i++)
{
for (size_t j = 0; j < c; j++)
printf("%3d", matrix[i][j]);
putchar('\n');
}
}
static void sort_diagonal(size_t n, int matrix[n][n])
{
for (size_t i = 0; i < n; i++)
{
for (size_t j = i + 1; j < n; j++)
{
if (cmp_eaod(matrix[i][i], matrix[j][j]) > 0)
{
int t = matrix[i][i];
matrix[i][i] = matrix[j][j];
matrix[j][j] = t;
}
}
}
}
/*
** D0 U0 U1 U2 U3
** L0 D1 U4 U5 U6
** L1 L2 D3 U7 U8
** L3 L4 L5 D4 U9
** L6 L7 L8 L9 D5
**
** D0 = (0, 0); U0 = (0, 1); U1 = (0, 2); U2 = (0, 3); U3 = (0, 4);
** L0 = (1, 0); D1 = (1, 1); U4 = (1, 2); U5 = (1, 3); U6 = (1, 4);
** L1 = (2, 0); L2 = (2, 1); D2 = (2, 2); U7 = (2, 3); U8 = (2, 4);
** L3 = (3, 0); L4 = (3, 1); L5 = (3, 2); D3 = (3, 3); U9 = (3, 4);
** L6 = (4, 0); L7 = (4, 1); L8 = (4, 2); L9 = (4, 3); D4 = (4, 4);
*/
/*
** It is probably best to create an array that does the mapping from an
** index to the row/column, with one such mapping for the lower
** triangle; one for the upper triangle.
*/
static void sort_lt(size_t n, int matrix[n][n])
{
size_t m = (n * (n - 1)) / 2;
int lt[m][2];
size_t r = 1;
size_t c = 0;
for (size_t i = 0; i < m; i++)
{
lt[i][0] = r;
lt[i][1] = c++;
if (c == r)
{
r++;
c = 0;
}
}
//print_matrix("LT map", m, 2, lt);
for (size_t i = 0; i < m; i++)
{
size_t xi = lt[i][0];
size_t yi = lt[i][1];
for (size_t j = i + 1; j < m; j++)
{
size_t xj = lt[j][0];
size_t yj = lt[j][1];
if (cmp_asc(matrix[xi][yi], matrix[xj][yj]) > 0)
{
int t = matrix[xi][yi];
matrix[xi][yi] = matrix[xj][yj];
matrix[xj][yj] = t;
}
}
}
}
static void sort_ut(size_t n, int matrix[n][n])
{
size_t m = (n * (n - 1)) / 2;
int ut[m][2];
size_t r = 0;
size_t c = 0;
for (size_t i = 0; i < m; i++)
{
ut[i][0] = r;
ut[i][1] = ++c;
if (c == n - 1)
{
r++;
c = r;
}
}
//print_matrix("UT map", m, 2, ut);
for (size_t i = 0; i < m; i++)
{
size_t xi = ut[i][0];
size_t yi = ut[i][1];
for (size_t j = i + 1; j < m; j++)
{
size_t xj = ut[j][0];
size_t yj = ut[j][1];
if (cmp_dsc(matrix[xi][yi], matrix[xj][yj]) > 0)
{
int t = matrix[xi][yi];
matrix[xi][yi] = matrix[xj][yj];
matrix[xj][yj] = t;
}
}
}
}
static void test_matrix(const char *tag, size_t n, int matrix[n][n])
{
char buffer[64];
snprintf(buffer, sizeof(buffer), "Matrix %s (%zux%zu) - before", tag, n, n);
print_matrix(buffer, n, n, matrix);
//print_matrix("Before sorting diagonal", n, n, matrix);
sort_diagonal(n, matrix);
//print_matrix("After sorting diagonal", n, n, matrix);
sort_lt(n, matrix);
//print_matrix("After sorting lower triangle", n, n, matrix);
sort_ut(n, matrix);
//print_matrix("After sorting upper triangle", n, n, matrix);
snprintf(buffer, sizeof(buffer), "Matrix %s (%zux%zu) - after", tag, n, n);
print_matrix(buffer, n, n, matrix);
}
int main(void)
{
int matrix1[5][5] =
{
{ 1, 5, 4, 7, 2 },
{ 4, 8, 5, 9, 0 },
{ 2, 7, 6, 5, 3 },
{ 3, 1, 7, 4, 9 },
{ 2, 5, 1, 7, 3 },
};
test_matrix("SAMPLE1", 5, matrix1);
// gen_matrix -i -n matrix2 -r 10 -c 10 -L 10 -H 99
int matrix2[10][10] =
{
{ 87, 32, 98, 58, 60, 71, 46, 81, 70, 14, },
{ 22, 92, 15, 98, 51, 26, 94, 67, 46, 56, },
{ 71, 89, 86, 16, 20, 89, 97, 89, 45, 92, },
{ 63, 13, 76, 19, 75, 19, 66, 89, 58, 41, },
{ 82, 68, 75, 26, 58, 20, 89, 87, 65, 66, },
{ 74, 83, 68, 92, 10, 98, 90, 21, 39, 63, },
{ 24, 65, 23, 68, 62, 44, 48, 22, 27, 59, },
{ 26, 27, 71, 71, 51, 31, 43, 69, 92, 10, },
{ 54, 19, 41, 50, 10, 89, 42, 52, 94, 54, },
{ 42, 50, 79, 48, 77, 18, 29, 40, 61, 63, },
};
test_matrix("SAMPLE 2", 10, matrix2);
return 0;
}
运行时，输出为：
Matrix SAMPLE1 (5x5) - before:
1 5 4 7 2
4 8 5 9 0
2 7 6 5 3
3 1 7 4 9
2 5 1 7 3
Matrix SAMPLE1 (5x5) - after:
4 9 9 7 5
1 6 5 5 4
1 2 8 3 2
2 3 4 3 0
5 7 7 7 1
Matrix SAMPLE 2 (10x10) - before:
87 32 98 58 60 71 46 81 70 14
22 92 15 98 51 26 94 67 46 56
71 89 86 16 20 89 97 89 45 92
63 13 76 19 75 19 66 89 58 41
82 68 75 26 58 20 89 87 65 66
74 83 68 92 10 98 90 21 39 63
24 65 23 68 62 44 48 22 27 59
26 27 71 71 51 31 43 69 92 10
54 19 41 50 10 89 42 52 94 54
42 50 79 48 77 18 29 40 61 63
Matrix SAMPLE 2 (10x10) - after:
48 98 98 97 94 92 92 90 89 89
10 58 89 89 87 81 75 71 70 67
10 13 86 66 66 65 63 60 59 58
18 19 22 92 58 56 54 51 46 46
23 24 26 26 94 45 41 39 32 27
27 29 31 40 41 98 26 22 21 20
42 42 43 44 48 50 87 20 19 16
50 51 52 54 61 62 63 69 15 14
65 68 68 68 71 71 71 74 63 10
75 76 77 79 82 83 89 89 92 19
“ SAMPLE1-之前”数据对应于问题中的输入，而“ SAMPLE 1-之前”数据对应于所需的输出。较大的矩阵结果似乎也符合要求。
我首先开发了对角线排序，因为它到目前为止是最简单的。偶数升序，奇数降序是我之前解决的问题。然后，我开发了一种三角形排序，并对其进行了调试。然后将第二个三角形排序非常简单。确保我具有良好的柔性矩阵打印功能也有帮助。在开发过程中的某个时间点，所有使用了注释的调用。
计时测试
随着矩阵的增长，所示的“就地排序”代码变得非常慢。还有一种替代方法-将数据从矩阵中复制到一维向量中；排序向量；将数据复制回矩阵。我做了一些计时测试。矩阵大小为10x10时，时间是可比的（上面显示的基本排序代码为15µs；使用提取，快速排序，插入的代码为12µs）。当矩阵大小为20x20时，性能强烈支持提取，快速排序，插入：172µs对32µs有利于快速排序，而对于900x900，基本排序对快速排序的支持为285s对0.054s。差异的增长速度快于二次排序所能解释的。问题是获取要排序的元素的访问路径非常复杂。用于创建
lt和ut矩阵的代码仍然有用。 lt和ut矩阵告诉您从哪个单元格收集数据以对三角形进行排序（提取数据的顺序并不重要，因为无论如何都要对它进行排序），而且（关键地）告诉您每个元素在已排序数据中的放置位置。您可以在GitHub的SOQ中找到我的代码（堆栈
溢出问题）存储库中
src/so-4829-1562
子目录。 （请注意，目前，该代码使用VLA进行中间矩阵处理；在Mac上，它的崩溃速度约为1000x1000。我需要对其进行更改，以在排序代码和数据生成代码中使用动态内存分配。它可能会同样，我不认为两次硬件刷新之间有足够的时间在10000x10000大小的矩阵上使用基本排序，尽管我认为快速排序代码仍然可以使用。）
另一个有趣的测试是将“基本排序”改编为在对三角形排序时使用提取，二次排序，插入。我很确定它会大大超过“基本排序”代码，尽管随着数组变得更大，它仍然会输给O（NlogN）快速排序代码。与分拣时间相比，复印时间可以忽略不计。
使用
qsort()等/* SO 4829-1562 */
#include "time.sort2d-31.h"
#include "emalloc.h"
/*
** + Enter a square matrix of dimensions n .
** + Elements below main diagonal sort in ascending order.
** + Elements above main diagonal sort in descending order.
** + Elements on main diagonal sort :
** - first even numbers in ascending order.
** - then odd numbers in descending order.
*/
/* Variation 4: Use system qsort() and common code to coordinate sorting of triangles */
/* Avoids two matrices lt and ut, thereby reducing the extra data space needed. */
static inline int cmp_asc(int x, int y) { return (x > y) - (x < y); }
static inline int cmp_dsc(int x, int y) { return (x < y) - (x > y); }
static inline int cmp_eaod(int x, int y)
{
int px = x & 1;
int py = y & 1;
if (px != py)
return px - py;
if (px == 1)
return cmp_dsc(x, y);
return cmp_asc(x, y);
}
static int qs_cmp_int_asc(const void *v1, const void *v2)
{
int i1 = *(const int *)v1;
int i2 = *(const int *)v2;
return cmp_asc(i1, i2);
}
static int qs_cmp_int_dsc(const void *v1, const void *v2)
{
int i1 = *(const int *)v1;
int i2 = *(const int *)v2;
return cmp_dsc(i1, i2);
}
static int qs_cmp_int_eaod(const void *v1, const void *v2)
{
int i1 = *(const int *)v1;
int i2 = *(const int *)v2;
return cmp_eaod(i1, i2);
}
static void sort_diagonal(size_t n, int matrix[n][n])
{
int data[n];
for (size_t i = 0; i < n; i++)
data[i] = matrix[i][i];
qsort(data, n, sizeof(data[0]), qs_cmp_int_eaod);
for (size_t i = 0; i < n; i++)
matrix[i][i] = data[i];
}
/*
** D0 U0 U1 U2 U3
** L0 D1 U4 U5 U6
** L1 L2 D3 U7 U8
** L3 L4 L5 D4 U9
** L6 L7 L8 L9 D5
**
** D0 = (0, 0); U0 = (0, 1); U1 = (0, 2); U2 = (0, 3); U3 = (0, 4);
** L0 = (1, 0); D1 = (1, 1); U4 = (1, 2); U5 = (1, 3); U6 = (1, 4);
** L1 = (2, 0); L2 = (2, 1); D2 = (2, 2); U7 = (2, 3); U8 = (2, 4);
** L3 = (3, 0); L4 = (3, 1); L5 = (3, 2); D3 = (3, 3); U9 = (3, 4);
** L6 = (4, 0); L7 = (4, 1); L8 = (4, 2); L9 = (4, 3); D4 = (4, 4);
*/
typedef void (*Copier)(int *val1, int *val2);
static void copy_a_to_b(int *val1, int *val2) { *val2 = *val1; }
static void copy_b_to_a(int *val1, int *val2) { *val1 = *val2; }
static void copy_lt_data(size_t n, int matrix[n][n], int vector[], Copier copy)
{
size_t m = (n * (n - 1)) / 2;
size_t r = 1;
size_t c = 0;
for (size_t i = 0; i < m; i++)
{
(*copy)(&matrix[r][c++], &vector[i]);
if (c == r)
{
r++;
c = 0;
}
}
}
static void copy_ut_data(size_t n, int matrix[n][n], int vector[], Copier copy)
{
size_t m = (n * (n - 1)) / 2;
size_t r = 0;
size_t c = 0;
for (size_t i = 0; i < m; i++)
{
(*copy)(&matrix[r][++c], &vector[i]);
if (c == n - 1)
{
r++;
c = r;
}
}
}
typedef void (*Mapper)(size_t n, int matrix[n][n], int vector[], Copier copy);
typedef int (*Comparator)(const void *v1, const void *v2);
static void sort_triangle(size_t n, int matrix[n][n], Mapper mapper, Comparator cmp)
{
size_t m = (n * (n - 1)) / 2;
int *data = MALLOC(m * sizeof(*data));
(*mapper)(n, matrix, data, copy_a_to_b);
qsort(data, m, sizeof(data[0]), cmp);
(*mapper)(n, matrix, data, copy_b_to_a);
FREE(data);
}
void quick_sort(size_t n, int matrix[n][n])
{
sort_diagonal(n, matrix);
sort_triangle(n, matrix, copy_lt_data, qs_cmp_int_asc);
sort_triangle(n, matrix, copy_ut_data, qs_cmp_int_dsc);
}
我还对时序测试进行了汇总-源代码请参见GitHub。结果是：
Basic sort (10x10) - elapsed: 0.000010
Clean sort (10x10) - elapsed: 0.000008
Quick sort (10x10) - elapsed: 0.000015
Basic sort (20x20) - elapsed: 0.000153
Clean sort (20x20) - elapsed: 0.000112
Quick sort (20x20) - elapsed: 0.000026
Basic sort (30x30) - elapsed: 0.000800
Clean sort (30x30) - elapsed: 0.000645
Quick sort (30x30) - elapsed: 0.000060
Basic sort (40x40) - elapsed: 0.002661
Clean sort (40x40) - elapsed: 0.002057
Quick sort (40x40) - elapsed: 0.000106
Basic sort (50x50) - elapsed: 0.006347
Clean sort (50x50) - elapsed: 0.005038
Quick sort (50x50) - elapsed: 0.000175
Basic sort (60x60) - elapsed: 0.014120
Clean sort (60x60) - elapsed: 0.009732
Quick sort (60x60) - elapsed: 0.000258
Basic sort (70x70) - elapsed: 0.023101
Clean sort (70x70) - elapsed: 0.016593
Quick sort (70x70) - elapsed: 0.000360
Basic sort (80x80) - elapsed: 0.035169
Clean sort (80x80) - elapsed: 0.027466
Quick sort (80x80) - elapsed: 0.000445
Basic sort (90x90) - elapsed: 0.053590
Clean sort (90x90) - elapsed: 0.039012
Quick sort (90x90) - elapsed: 0.000665
Basic sort (100x100) - elapsed: 0.074192
Clean sort (100x100) - elapsed: 0.053694
Quick sort (100x100) - elapsed: 0.000797
Basic sort (200x200) - elapsed: 0.656721
Clean sort (200x200) - elapsed: 0.478688
Quick sort (200x200) - elapsed: 0.002313
Basic sort (300x300) - elapsed: 2.826153
Clean sort (300x300) - elapsed: 2.126663
Quick sort (300x300) - elapsed: 0.004871
Basic sort (400x400) - elapsed: 8.384908
Clean sort (400x400) - elapsed: 6.374244
Quick sort (400x400) - elapsed: 0.008324
Basic sort (500x500) - elapsed: 22.083337
Clean sort (500x500) - elapsed: 16.124325
Quick sort (500x500) - elapsed: 0.014953
Basic sort (600x600) - elapsed: 43.233985
Clean sort (600x600) - elapsed: 31.362548
Quick sort (600x600) - elapsed: 0.019563
Basic sort (700x700) - elapsed: 85.463261
Clean sort (700x700) - elapsed: 60.488744
Quick sort (700x700) - elapsed: 0.027003
Basic sort (800x800) - elapsed: 148.358024
Clean sort (800x800) - elapsed: 102.991679
Quick sort (800x800) - elapsed: 0.038143
Basic sort (900x900) - elapsed: 253.434539
Clean sort (900x900) - elapsed: 150.658682
Quick sort (900x900) - elapsed: 0.045815
Quick sort (10x10) - elapsed: 0.000007
Quick sort (20x20) - elapsed: 0.000025
Quick sort (30x30) - elapsed: 0.000057
Quick sort (40x40) - elapsed: 0.000104
Quick sort (50x50) - elapsed: 0.000196
Quick sort (60x60) - elapsed: 0.000245
Quick sort (70x70) - elapsed: 0.000397
Quick sort (80x80) - elapsed: 0.000435
Quick sort (90x90) - elapsed: 0.000538
Quick sort (100x100) - elapsed: 0.000676
Quick sort (200x200) - elapsed: 0.002780
Quick sort (300x300) - elapsed: 0.005868
Quick sort (400x400) - elapsed: 0.009393
Quick sort (500x500) - elapsed: 0.016258
Quick sort (600x600) - elapsed: 0.024982
Quick sort (700x700) - elapsed: 0.031137
Quick sort (800x800) - elapsed: 0.042561
Quick sort (900x900) - elapsed: 0.052450
Quick sort (1000x1000) - elapsed: 0.061720
Quick sort (2000x2000) - elapsed: 0.229984
Quick sort (3000x3000) - elapsed: 0.480724
Quick sort (4000x4000) - elapsed: 0.826916
Quick sort (5000x5000) - elapsed: 1.308370
Quick sort (6000x6000) - elapsed: 1.890218
Quick sort (7000x7000) - elapsed: 2.559171
Quick sort (8000x8000) - elapsed: 3.346258
Quick sort (9000x9000) - elapsed: 4.359553
Quick sort (10000x10000) - elapsed: 5.345243
Quick sort (20000x20000) - elapsed: 22.189061
Quick sort (30000x30000) - elapsed: 51.385711
Quick sort (40000x40000) - elapsed: 97.543689
Quick sort (50000x50000) - elapsed: 177.373366
Quick sort (60000x60000) - elapsed: 315.083561
Quick sort (70000x70000) - elapsed: 476.135379
Quick sort (80000x80000) - elapsed: 756.888114
Quick sort (90000x90000) - elapsed: 1002.540185
在非常小的尺寸（10x10或更小）下，
qsort()代码可能比其他代码慢一些-差异很小（几微秒），但相当一致。当您达到20x20时，qsort()代码会持续更快，并且差异会越来越大。请注意，用于O（NlogN）或O（N2）的大小N对应于矩阵大小的平方-因此要在20x20矩阵中排序的数据量是要处理的数据量的四倍。以10x10矩阵排序。基本排序或“干净排序”的性能非常差，以至于90k x 90k矩阵都不用考虑，但是qsort()代码对它进行排序的时间与其他人对900进行排序所花费的时间相当x 900矩阵（大小的1 / 10,000）。修复添加的代码2018-02-02
在2018-02-02上添加到问题中的代码是一种以不同方式解决问题的好尝试。
如OP所述，有时它无法正确排序数据。
问题是下三角形中的代码
这是固定的代码，因此它可以在以前使用的两个样本矩阵上产生正确的输出。
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
static int a[500][500];
int i, j, l, k, m, b, n, t, d, c;
printf("Unesite n kvadratne matrice:\n");
scanf("%d", &n);
printf("Matrica pre sortiranja\n\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
printf("%3d", a[i][j]);
printf("\n");
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i > j) // ispod dijagonale (LT)
{
int s = j + 1; // JL
for (l = i; l < n; l++)
{
//for (k = j; k < l; k++) // OP
for (k = s; k < l; k++) // JL
{
//printf("a[%d][%d] = %d <=> a[%d][%d] %d\n", // JL
// i, j, a[i][j], l, k, a[l][k]); // JL
//if (a[i][j] > a[l][k] && k < l) // OP
if (a[i][j] > a[l][k]) // JL
{
t = a[i][j];
a[i][j] = a[l][k];
a[l][k] = t;
}
}
s = 0; // JL
}
}
if (i < j) // iznad dijagonale (UT)
{
int s = j + 1; // JL
for (m = i; m < n; m++)
{
//for (b = j; b < n; b++) // OP
for (b = s; b < n; b++) // JL
{
//printf("a[%d][%d] = %d <=> a[%d][%d] %d\n", // JL
// i, j, a[i][j], m, b, a[m][b]); // JL
//if (a[i][j] < a[m][b] && m < b) // OP
if (a[i][j] < a[m][b]) // JL
{
t = a[i][j];
a[i][j] = a[m][b];
a[m][b] = t;
}
}
s = m + 2; // JL
}
}
if (i == j) // dijagonala
{
for (d = i; d < n; d++)
{
for (c = d + 1; c < n; c++)
{
if (a[d][d] % 2 != 0 && a[c][c] % 2 == 0)
{
t = a[d][d];
a[d][d] = a[c][c];
a[c][c] = t;
}
}
}
for (d = i; d < n; d++)
{
for (c = d + 1; c < n; c++)
{
if (a[d][d] % 2 == 0 && a[c][c] % 2 == 0
&& a[d][d] > a[c][c])
{
t = a[d][d];
a[d][d] = a[c][c];
a[c][c] = t;
}
else if (a[d][d] % 2 != 0 && a[c][c] % 2
!= 0 && a[d][d] < a[c][c])
{
t = a[d][d];
a[d][d] = a[c][c];
a[c][c] = t;
}
}
}
}
}
}
printf("Posle sortiranja:\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
printf("%3d", a[i][j]);
printf("\n");
}
return 0;
}
被注释掉的打印操作对于了解问题所在至关重要。
样品输出
该程序是
sort2d-mk2-73。$ sort2d-mk2-73 < example-2.in
Unesite n kvadratne matrice:
Matrica pre sortiranja
87 32 98 58 60 71 46 81 70 14
22 92 15 98 51 26 94 67 46 56
71 89 86 16 20 89 97 89 45 92
63 13 76 19 75 19 66 89 58 41
82 68 75 26 58 20 89 87 65 66
74 83 68 92 10 98 90 21 39 63
24 65 23 68 62 44 48 22 27 59
26 27 71 71 51 31 43 69 92 10
54 19 41 50 10 89 42 52 94 54
42 50 79 48 77 18 29 40 61 63
Posle sortiranja:
48 98 98 97 94 92 92 90 89 89
10 58 89 89 87 81 75 71 70 67
10 13 86 66 66 65 63 60 59 58
18 19 22 92 58 56 54 51 46 46
23 24 26 26 94 45 41 39 32 27
27 29 31 40 41 98 26 22 21 20
42 42 43 44 48 50 87 20 19 16
50 51 52 54 61 62 63 69 15 14
65 68 68 68 71 71 71 74 63 10
75 76 77 79 82 83 89 89 92 19
$ sort2d-mk2-73 < example-1.in
Unesite n kvadratne matrice:
Matrica pre sortiranja
1 5 4 7 2
4 8 5 9 0
2 7 6 5 3
3 1 7 4 9
2 5 1 7 3
Posle sortiranja:
4 9 9 7 5
1 6 5 5 4
1 2 8 3 2
2 3 4 3 0
5 7 7 7 1
$
为了进行比较，生成了问题（
sort2d-mk2-67）中发布的代码：$ sort2d-mk2-67 < example-2.in
Unesite n kvadratne matrice :
Matrica pre sortiranja
Posle sortiranja :
48 98 98 97 94 92 92 90 89 66
10 58 89 89 89 87 81 75 70 63
10 13 86 71 67 66 65 60 59 56
18 19 22 92 58 58 54 51 46 46
23 24 26 29 94 45 41 39 32 27
26 27 31 40 41 98 26 22 21 20
42 42 43 44 48 50 87 20 19 16
50 51 52 54 61 62 63 69 15 14
65 68 68 68 71 71 71 76 63 10
74 75 77 79 82 83 89 89 92 19
$ sort2d-mk2-67 < example-1.in
Unesite n kvadratne matrice :
Matrica pre sortiranja
Posle sortiranja :
4 9 9 7 5
1 6 5 5 3
1 2 8 4 2
2 3 5 3 0
4 7 7 7 1
$
sort2d-mk2-67.c和sort2d-mk2-73.c之间的变化之一是压缩打印。另一个更改是在排序操作之前和之后打印矩阵。在较小的矩阵中，您可以看到第1行第4列（从0开始）中的
3应该是第2行第3列中的4。同样，第3行第2列中的
5应该是第4行第1列中的4。固定代码可以。
我尚未对该代码进行基准测试（尚未）。
关于c - 在C中对2D数组(矩阵)进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48291562/