内部排序的性能分析：函数调用的问题？在主函数中用一种方法排序后，排好序的顺序表被带回主函数，再用另一种方法排序等于没用了

Question

原先用的void insertsort（Sqlist &L），改成void insertsort（Sqlist L）还是不行，形参不是传值调用主函数不会改变嚒？

已经测试排序的代码没有问题，单独使用一种方法没有问题，几种同时使用才会出问题，

第一行：随机生成的顺序表

第二行：Insert排序后的顺序表

第三行：比较次数，移动次数

第四行：Shell排序前的顺序表

第五行：Shell排序后的顺序表

可以看出shell根本不需要排序，移动次数为0......

代码太长截取一部分有用的：

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int  Position;
typedef int  ElemType;
typedef int Status;
int compare1=0,compare2=0,compare3=0,compare4=0,compare5=0,compare6=0;//比较次数
int move1 = 0, move2 = 0, move3 = 0, move4 = 0, move5 = 0, move6 = 0;//移动次数
ElemType*p, *q;
#define LIST_INIT_SIZE 100     
#define LISTINCREMENT 10   
#define OK 1;
#define TRUE 1;
#define FALSE 0;
#define ERROR 0;
#define OVERFLOW -2;
/*①SqList.h线性表的动态分配顺序存储结构*/
typedef struct
{
    int key;
}lkey;
typedef  struct
{
    lkey *elem;      
    int length;          
    int listsize; 
}SqList;

/*②顺序表基本操作接口定义*/
//操作结果：构造一个空的线性表
Status InitList_Sq(SqList &L);
//操作结果：在L中第i个元素之前插入新的元素e,L的长度加1
Status ListInsert_Sq(SqList &L, int i, ElemType e); 
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType));
//将元素e的值打印出来
Status visit_sp(ElemType e);
//直接插入排序
void InsertSort(SqList L);
//希尔排序
void ShellSort(SqList L, int dlta[], int t);
void Shell(SqList L, int dk);//一趟希尔插入排序 
//起泡排序
void BubbleSort(SqList L);
//快速排序
void QuickSort(SqList L);
void Quick(SqList L, int low, int high);
int QsortPartion(SqList L, int low, int high);//一趟快速排序
//简单选择排序
void SelectSort(SqList L);
//堆排序
void HeapSort(SqList L);
void HeapAdjust(SqList L, int s, int m);//建大顶堆函数  


//随机生成数构造线性表
Status InitList_Sq(SqList &L)
{
    int i;
    L.elem = (lkey*)malloc(LIST_INIT_SIZE * sizeof(lkey));
    if (!L.elem)exit(-2);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;    
    //srand((unsigned)time(NULL));
    for (i = 1; i < 15; i++)
    {       
        L.elem[i].key = rand() % 100 + 1;
        ListInsert_Sq(L, i, L.elem[i].key);
    }
    return OK;
    /*请参考课本上的算法2.3*/
}
//在L中第i个元素之前插入新的元素e,L的长度加1
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
    if (i<1 || i>L.length + 1)
        return ERROR;
    if (L.length >= L.listsize)
    {
        lkey*newbase = (lkey*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(lkey));
        if (!newbase)return ERROR;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    q = &(L.elem[i - 1].key);
    for (p = &(L.elem[L.length - 1].key); p >= q; --p)
        *(p + 1) = *p;
    *q = e;
    ++L.length;
    return OK;
    /*请参考课本上的算法2.4*/
}
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType))
{
    int i;
    for (i = 1; i <= L.length; i++)
        (*visit)(L.elem[i - 1].key);
    printf("\n");
    return OK;
}
//将元素e的值打印出来
Status visit_sp(ElemType e)
{
    printf("%d  ", e);
    return OK;
}

//直接插入排序
void InsertSort(SqList L)
{
    int compare1 = 0, move1 = 0;
    int i=0, j=0;
    lkey rc;
    for (i = 1; i<L.length; ++i)//从第二个开始
    {
        compare1++;
        if (L.elem[i].key < L.elem[i - 1].key)
        {
            move1 += 2;
            rc = L.elem[i];
            L.elem[i] = L.elem[i - 1];
            for (j = i - 2; j >= 0 && rc.key < L.elem[j].key; --j)//从i-2个开始
            {
                compare1++;
                L.elem[j + 1] = L.elem[j];
                move1++;                
            }
            L.elem[j + 1] = rc;
            move1 += 3;
        }
    }
    ListTraverse_Sq(L,visit_sp);
    printf("%d %d\n", compare1, move1);
}

//希尔排序
void ShellSort(SqList L, int dlta[], int t) 
{
    ListTraverse_Sq(L, visit_sp);
    int k;  
    for (k = 0; k < t; k++)
        Shell(L, dlta[k]);
    ListTraverse_Sq(L, visit_sp);
    printf("%d %d\n", compare2, move2);
}
void Shell(SqList L, int dk)//一趟希尔插入排序 
{
    lkey rc;
    int j;
    for (int i = dk; i < L.length; i++)
    {
        compare2++;
        if (L.elem[i].key < L.elem[i - dk].key)//比较i和i-dk
        {
            rc = L.elem[i];
            move2++;
            for (j = i - dk; j >= 0 && (rc.key < L.elem[j].key); j -= dk)//[6]和[3]，[0]比较
            {
                compare2++;
                L.elem[j + dk] = L.elem[j];//记录后移，查找插入位置  
                move2++;
            }
            L.elem[j + dk] = rc;//插入  
            move2++;
        }
    }
}
int main()
{
    SqList L;
    int i;
    int dita[3] = { 5,3,1 }, t = 3;
    for (i = 0; i <= 5; i++)
    {
        printf("当前随机数为：\n");
        InitList_Sq(L);
        ListTraverse_Sq(L, visit_sp);   
        InsertSort(L);
        ShellSort(L, dita, t);
        //BubbleSort(L);
        //QuickSort(L);
        //SelectSort(L);
        //HeapSort(L);
        /*printf("------|-比较次数-||-移动次数-|\n");       
        printf("Insert|   %d     ||   %d     |\n", compare1, move1);
        printf("Shell |   %d     ||   %d     |\n", compare2, move2);
        printf("Bubble|   %d     ||   %d     |\n", compare3, move3);
        printf("Quick |   %d     ||   %d     |\n", compare4, move4);
        printf("Select|   %d     ||   %d     |\n", compare5, move5);
        printf("Heap  |   %d     ||   %d     |\n", compare6, move6);*/
    }
    system("pause");
    return 0;
}

Answer 1

https://wenku.baidu.com/view/30b5b0bf162ded630b1c59eef8c75fbfc77d9496.html