我在一次采访中被问到这个问题。我得到一个随机数的二维数组(数字可以重复),我需要对它们进行行和列的排序,即所有的行和列都应该排序。谁能解释一下如何有效地做到这一点(最小时间和空间复杂度)。如果您可以提供 C 或 C++ 代码,那将非常有帮助
问问题
9901 次
2 回答
2
我的想法是二维数组(在某些情况下)可以被视为一维数组,因为它的内存存储。如果没有,您可以将其复制到一维数组中,编写一个自定义排序函数,该函数使用将索引从一维转换为二维的函数。
这是一个使用函数 qsort 的示例:
#include <stdio.h>
#include <stdlib.h>
int matrix[4][4];
void print_matrix() {
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int compar(const void *a, const void *b) {
int ia = *((int*)a);
int ib = *((int*)b);
return ia - ib;
}
int main() {
int i, j;
// Init of a 2D array with random numbers:
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
matrix[i][j] = random() % 10;
}
}
// Before:
printf("Before:\n");
print_matrix();
// This array can be considered as a big 1D array.
qsort(matrix, 16, sizeof(int), compar);
// After:
printf("After:\n");
print_matrix();
return 0;
}
输出:
Before:
3 6 7 5
3 5 6 2
9 1 2 7
0 9 3 6
After:
0 1 2 2
3 3 3 5
5 6 6 6
7 7 9 9
编辑: OP要求我避免使用qsort ...所以这里有一个能够对二维数组进行排序的快速排序:
#include <stdio.h>
#include <stdlib.h>
void print_matrix(int **matrix, int rows, int cols) {
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
void swap(int *a, int *b) {
int buf = *a;
*a = *b;
*b = buf;
}
int partition(int **a, int l, int r, int c) {
int i;
// Left pivot
int pivot_val = a[l/c][l%c];
// Move pivot to end
swap(&a[l/c][l%c], &a[r/c][r%c]);
// If <= to the pivot value, swap
int j = l;
for (i = l; i < r; i++) {
if (a[i/c][i%c] <= pivot_val) {
swap(&a[i/c][i%c], &a[j/c][j%c]);
j++;
}
}
// Move pivot to its place.
swap(&a[j/c][j%c], &a[r/c][r%c]);
return j;
}
void quicksort_r(int **a, int l, int r, int c) {
if (l < r) {
int pivot = partition(a, l, r, c);
quicksort_r(a, l, pivot-1, c);
quicksort_r(a, pivot+1, r, c);
}
}
void quicksort(int **a, int rows, int cols) {
quicksort_r(a, 0, rows * cols - 1, cols);
}
int main() {
int i, j;
int rows = 5;
int cols = 4;
int **matrix = malloc(sizeof(int*) * rows);
// Init of a 2D array with random numbers:
for (i = 0; i < rows; i++) {
matrix[i] = malloc(sizeof(int) * cols);
for (j = 0; j < cols; j++) {
matrix[i][j] = random() % 10;
}
}
// Before:
printf("Before:\n");
print_matrix(matrix, rows, cols);
quicksort(matrix, rows, cols);
// After:
printf("After:\n");
print_matrix(matrix, rows, cols);
return 0;
}
这使:
Before:
3 6 7 5
3 5 6 2
9 1 2 7
0 9 3 6
0 6 2 6
After:
0 0 1 2
2 2 3 3
3 5 5 6
6 6 6 6
7 7 9 9
Edit2:后来我意识到方阵还有另一个明显的解决方案:
我们来看第一个例子:
0 1 2 2
3 3 3 5
5 6 6 6
7 7 9 9
还有:
0 3 5 7
1 3 6 7
2 3 6 9
2 5 6 9
但对于第二个例子也是:
0 0 1 2
2 2 3 3
3 5 5 6
6 6 6 6
7 7 9 9
和:
0 2 3 6
0 2 5 6
1 3 5 6
2 3 6 6
7 7 9 9
这意味着也许我们可以做一个能够给出所有解决方案的专门算法,或者一个试图最小化移动次数的算法,我不知道。事实上,这是一个非常有趣的问题。
于 2013-07-05T08:49:58.190 回答
0
尝试使用和调整这个......
void sort(int MyArray[8][8])
{
for(int ir=0;ir<8;ir++)
{
for(int ic=0;ic<8;ic++)
{
for(int jr=0;jr<8;jr++)
{
for(int jc=0;jc<8;jc++)
{
if(MyArray[ir][jr]>MyArray[ic][jc])
{
int temp=MyArray[ir][jr];
MyArray[ir][jr]=MyArray[ic][jc];
MyArray[ic][jc]=temp;
}
}
}
}
}
}
这是一个简单的冒泡排序。它有效地运行在 O(n^4) 上,您可以通过编写诸如快速排序之类的算法来提高效率。我从未见过甚至想过尝试对二维数组进行快速排序。这并不容易。您可以尝试将所有内容添加到单个数组中,对其进行快速排序并将所有内容复制回二维数组中。但是数组必须非常大才能更有效......如果有人在这里为二维数组提供快速排序或合并排序算法。他应该得到一枚勋章!那是铁杆
于 2013-07-05T08:27:05.297 回答