c - 使用 C 的插入排序

Question

目标:使用插入排序对指针数组进行降序排序。在对指针数组进行排序的同时，指针指向的数组也会随之排序。

void insert(int **table, int row)

{

//  Local Declaration

    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

return;

}

示例输出:

Before insertion sort:

1 -66

2 51 0

3 68 61 37

4 91 80 31 -9

5 59 42 -15 -19 -75

After insertion sort:

5 -66 -59 134218571 4132481 0

4 51 0 31 131357707

3 68 61 37

2 91 80

1 59

我应该为每个数组创建一个副本，当我使用插入排序时交换数组还是有更有效的方法来完成任务？

完整程序:

/*********************************************************************************
** CIS 15BG                                                           Winter, 2013
***************
**
** Homework 3:
**        Pointers, Dynamic Allocation of Memory, Ragged Arrays, and Sorting
**
**********************************************************************************

  This program creates a dynamic table that can store a ragged 2D array
  of integers, sorts each row then rearranges them by length

***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef _MSC_VER
#include <crtdbg.h>  // needed to check for memory leaks (Windows only!)
#endif

#define MEM_ERROR printf("Not enough memory\n")

int** getRow(int *row);
void valiRow(int *row);
void getSize(int **table, int row);
int  valiSize(int size);
void fillTable(int **table, int row);
void bubble(int **table, int row);
void insert(int **table, int row);
void save(int **table, int row);

int main (void)
{
    //  Local Declaration
    int **table;
    int row;

    //  Statement
    table = getRow(&row);
    getSize(table, row);
    fillTable(table, row);
    bubble(table, row);
    insert(table, row);

    #ifdef _MSC_VER
    printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Memory Leak\n");
    #endif
    return 0;

}// main

/* getRow */
int** getRow(int *row)
{
    //  Local Declaration
    int **table;

    //  Statement
    printf("Please enter the number of rows (1-10): ");
    scanf("%d", &*row);

    valiRow(&*row);

    table =(int**)calloc(*row+1, sizeof(int));
    if(table == NULL)
        MEM_ERROR, exit(100);

    return table;
}

/* valiRow */
void valiRow(int *row)
{
    //  Statement
    while(*row > 10 || *row < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a number between (1-10): ");
        scanf("%d", &*row);
    }

    return;
}
/* getSize */
void getSize(int **table, int row)
{
    //  Local Declaration
    int i, size;

    //  Statement
    for(i = 0; i < row; i++)
    {
        printf("<ROW %2d> Please enter a size (1-15): ", i + 1);
        scanf("%d", &size);

        size = valiSize(size);

        table[i] = (int*)calloc(size + 1, sizeof(int));
        table[i][0] = size;
    }

    if(table == NULL)
        MEM_ERROR, exit(101);

    return;
}

/* valiSize */
int valiSize(int size)
{
    //  Statement
    while(size > 15 || size < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a valid size (1-15): ");
        scanf("%d", &size);
    }

    return size;
}

/* fillTable */
void fillTable(int **table, int row)
{
    //  Local Declaration
    int random, i, j;

    //  Statement
    srand(time(NULL));
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < (table[i][0]) + 1; j++)
        {
            random = -99 + rand() % 199;
            table[i][j + 1] = random;
        }
    }

    return;
}

/* bubble */
void bubble(int **table, int row)
{
    //  Local Declaration
    int current, last, walker, temp;
    int i, j;
    //  Statment

    for(i = 0; i < row; i++)
    {
        last = table[i][0];
        for(current = 1; current < last; current++)
        {
            for(walker = last; walker > current; walker--)
            {
                if(table[i][walker] > table[i][walker - 1])
                {
                    temp = table[i][walker];
                    table[i][walker] = table[i][walker - 1];
                    table[i][walker - 1] = temp;
                }
            }
        }
    }

    return;
}

/* insert */
void insert(int **table, int row)
{
    //  Local Declaration
    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

    return;
}

Answer 1

您应该在插入函数中交换指针交换第一个元素的值(大小)并不意味着交换数组的剩余元素。

void insert(int **table, int row)
{
    //  Local Declaration
    int *temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = table[current];
        walker = current - 1;
        while(walker >= 0 && *temp > *table[walker])
        {
            table[walker + 1] = table[walker];
            walker--;
        }
        table[walker + 1] = temp;
    }

    return;
}