请问这是直接插入排序吗？
有人能解答一下吗，请问这是直接插入排序吗？感觉像是冒泡排序，这是我自己写的，刚学习不太懂
void InsertSort(ElemType A[], int len) {
int i, j;
ElemType insertVal;
for (j = 1; j < len; j++) {
insertVal = A[j];
for (i = j - 1; i >= 0; i--) {
if (A[i] > insertVal) {
A[i + 1] = A[i];
A[i] = insertVal;
}
}
}
}
和下面的直接插入排序有什么区别？
void InsertSort(ElemType *A, int len) {
int i, j;
ElemType insertVal;
for (j = 1; j < len; j++) {
insertVal = A[j];
for (i = j - 1; i >= 0; i--) {
if(A[i] > insertVal){
A[i + 1] = A[i];
}
else {
break;
}
}
A[i + 1] = insertVal;
}
}
是直接插入排序，第二段显然效率更高。你的代码有无用功。因为数组是有序的，所以一旦不符合排序规则，就不用继续向下比较了
chatgpt:
这两个函数都是直接插入排序的实现，只不过实现细节上有所不同。
第一个函数的实现方式是，从第二个元素开始向后遍历，将当前元素存储在临时变量insertVal中，并在当前元素的前面的已排序子序列中进行遍历，将所有大于insertVal的元素都向后移动一位，直到找到insertVal的插入位置，然后将insertVal插入到该位置。
而第二个函数的实现方式是，从第二个元素开始向后遍历，将当前元素存储在临时变量insertVal中，并在当前元素的前面的已排序子序列中进行遍历，将所有大于insertVal的元素都向后移动一位，直到找到insertVal的插入位置，然后将insertVal插入到该位置。不同之处在于，第二个函数在内层循环中加了一个break语句，一旦找到一个小于等于insertVal的元素就会退出循环，而不是一直遍历到头，这样可以提高效率。
两个函数的时间复杂度都是O(n^2)，但第二个函数的常数项要比第一个函数小，因此实际运行速度可能会更快。
这是直接插入排序，特征就是每次在待排的里面找到一个最小的，和第一个元素交换
冒泡是反复交换相邻的
- 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/369012
- 你也可以参考下这篇文章：电脑麦克风没有声音怎么办？如何恢复？(电脑麦克风没声音的解决方法)
- 除此之外, 这篇博客: 什么是可变参数列表？以及可变参数列表是如何实现的？中的 2、那么通过一个简单的函数，详细了解一下具有可变参数列表的函数时如何实现函数功能的 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
#include<stdio.h> #include<stdarg.h> int average(int n, ...) //该函数的功能为：求出任意个数参数的平均值 { int i = 0; int sum = 0; va_list arg; //即：char* arg; va_start(arg, n); //即：arg = (char*)&n + 4; //初始化arg为位置参数列表中的第一个参数的地址 for(i=0; i<n; i++) { sum += va_arg(arg, int); //即： sum += (*(int *)(arg += 4) - 4); //此时已经将arg重新赋值为可变参数列表中第二个参数的地址， //但是此处保留的仍然是上一个参数的地址，然后对保留地址进行 //强制类型转换之后解以用得到内容(参数) } return sum/n; va_end(arg); //即：arg = char* 0; //把arg置为NULL } int main() { int a = 10; int b = 20; int c = 30; int avg1 = average(2, a, b); int avg2 = average(3, a, b,c); printf("avg1 = %d\n",avg1); printf("avg2 = %d\n",avg2); return 0; }上述代码的执行结果：
。可以看到函数中定义出了几个之前未见过的符号，我们转到定义看看到底是什么：
typedef char * va_list; //类型重定义：将char* 定义为va_list #define va_start _crt_va_start #define va_arg _crt_va_arg #define va_end _crt_va_end //这三个都是#define 定义的符号，不清楚是什么，再次转到定义： #define _crt_va_start(ap,v) ( ap = (va_list)_ADDRESSOF(v) + _INTSIZEOF(v) ) #define _crt_va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) #define _crt_va_end(ap) ( ap = (va_list)0 ) //原来是三个宏，对其中不明白的符号再次转到定义： #define _ADDRESSOF(v) ( &(v) ) #define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) ) //仍然是两个宏哦，这时候先进行替换，方便理解：
va_list arg; 相当于 char* arg; //arg是个字符指针呀
va_start(arg, n); 相当于 _crt_va_start(arg, n)；相当于(arg = (va_list)_ADDRESSOF(n) + _INTSIZEOF(n))
相当于 (arg = (char*)&n + ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
其中 ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) ) ;求出n的字节数，然后向上取整为4的倍数（换句话说： _INTSIZEOF(n)整个做的事情就是将n的长度化为int长度的整数倍）
所以在上述代码中相当于 arg = (char*)&n + 4;
//初始化arg为位置参数列表中的第一个参数的地址（如调用这个函数时用的参数为（int 3, 1,2,6），那么此时arg指向的是1所在的地址）
va_arg(arg, int); 相当于 _crt_va_arg(arg,int)
相当于 ( *(int *)((arg += _INTSIZEOF(int)) - _INTSIZEOF(int)) )
所以在上述代码中相当于 *(int *)(arg += 4) - 4;
//此时已经将arg重新赋值为可变参数列表中第二个参数的地址，但是此处保留的仍然是上一个参数的地址，然后对保留地址进行强制类型转换之后解以用得到内容(参数)
va_end(arg); 相当于 (arg = (va_list)0)
所以在上述代码中相当于 arg = char* 0; //把arg置为NULL
回到原来代码中进行替换。
为了更好的理解，我们把该程序的反汇编拷贝出来解析一下：（仅以int avg1 = average(2, a, b);本次调用为例）
int main() //调用main函数之前已经调用了其他函数 { 01154770 push ebp //将当前ebp的地址压栈到当前的栈顶，每次压栈esp都更新 01154771 mov ebp,esp //将当前的ebp移动到当前esp的位置处 01154773 sub esp,0FCh //将esp向低地址处移动OFCh，为main()开辟空间 01154779 push ebx //将寄存器ebx压入栈顶 0115477A push esi //将寄存器esi压入栈顶 0115477B push edi //将寄存器edi压入栈顶 0115477C lea edi,[ebp-0FCh] //将为main开辟空间时的esp的地址加载进入edi中 01154782 mov ecx,3Fh //ecx中放入3Fh 01154787 mov eax,0CCCCCCCCh //eax中放入0CCCCCCCCh 0115478C rep stos dword ptr es:[edi] //从edi中所存的地址处开始，用0CCCCCCCCh始化3Fh次 0115478E mov ecx,offset _FC008D77_test@c (0115C003h) 01154793 call @__CheckForDebuggerJustMyCode@4 (01151212h) int a = 10; 01154798 mov dword ptr [a],0Ah //创建变量，dword ptr [a]中放入0Ah int b = 20; 0115479F mov dword ptr [b],14h //创建变量，dword ptr [b]中放入14h int c = 30; 011547A6 mov dword ptr [c],1Eh //创建变量，dword ptr [c]中放入1Eh int avg1 = average(2, a, b); //调用函数前先进行传参（参数列表中从右向左） 011547AD mov eax,dword ptr [b] //eax中放入dword ptr [b]的内容 011547B0 push eax //调用average函数前将要用的形参放入寄存器并压栈 011547B1 mov ecx,dword ptr [a] //eax中放入dword ptr [b]的内容 011547B4 push ecx //调用average函数前将要用的形参放入寄存器并压栈 011547B5 push 2 //将参数2也压栈 011547B7 call _average (01151398h) //开始调用average函数(将此地址进行压栈/保护现场) 011547BC add esp,0Ch //esp回到原来的位置，将开辟的栈帧回收 011547BF mov dword ptr [avg1],eax //将eax中存的平均值放入avr1中准备打印 int average(int n, ...) { 01151810 push ebp 01151811 mov ebp,esp 01151813 sub esp,0E4h 01151819 push ebx 0115181A push esi 0115181B push edi 0115181C lea edi,[ebp-0E4h] 01151822 mov ecx,39h 01151827 mov eax,0CCCCCCCCh 0115182C rep stos dword ptr es:[edi] //average()函数的栈帧开辟以及初始化过程，同main() 0115182E mov ecx,offset _FC008D77_test@c (0115C003h) 01151833 call @__CheckForDebuggerJustMyCode@4 (01151212h) int i = 0; 01151838 mov dword ptr [i],0 //创建局部变量i并初始化为0； int sum = 0; 0115183F mov dword ptr [sum],0 //创建局部变量sum并初始化为0； va_list arg; va_start(arg, n); 01151846 lea eax,[ebp+0Ch] //将当前的ebp+0Ch处的地址存放到eax中 01151849 mov dword ptr [arg],eax //将eax中的内容赋值给arg for (i = 0; i < n; i++) 0115184C mov dword ptr [i],0 //进入循环，先把i用0赋值 01151853 jmp average+4Eh (0115185Eh) //跳转到0115185Eh处，执行eax,dword ptr [i] 01151855 mov eax,dword ptr [i] //由0115187Bh跳转过来 01151858 add eax,1 //执行++ 0115185B mov dword ptr [i],eax //并重新赋值给i,继续进行循环 0115185E mov eax,dword ptr [i] //由01151853h跳转过来，将此时的i加载到eax中 01151861 cmp eax,dword ptr [n] //eax的值与变量n的值进行比较 01151864 jge average+6Dh (0115187Dh) { sum += va_arg(arg, int); //即： sum += (*(int *)(arg += 4) - 4); 01151866 mov eax,dword ptr [arg] 01151869 add eax,4 0115186C mov dword ptr [arg],eax //此时arg存放的是下一个参数(第3个参数)的地址 0115186F mov ecx,dword ptr [arg] 01151872 mov edx,dword ptr [sum] 01151875 add edx,dword ptr [ecx-4] //sum的值加上一次arg所指地址处的内容(第2个参数) 01151878 mov dword ptr [sum],edx //将求的和继续放在sum中 } 0115187B jmp average+45h (01151855h) //跳转到0115185Eh处，执行准备执行i++ return sum / n; 0115187D mov eax,dword ptr [sum] //将for循环结束之后的sum放入eax中 01151880 cdq 01151881 idiv eax,dword ptr [n] //用eax中的数值除以变量n的内容，得到平均值 01151884 jmp average+7Dh (0115188Dh) va_end(arg); //即：arg = char* 0; //把arg置为NULL 01151886 mov dword ptr [arg],0 } 0115188D pop edi 0115188E pop esi 0115188F pop ebx //弹出栈顶的各种寄存器 01151890 add esp,0E4h //回收为average开辟的栈帧 01151896 cmp ebp,esp 01151898 call __RTC_CheckEsp (0115121Ch) 0115189D mov esp,ebp 0115189F pop ebp 011518A0 ret //最终将栈顶的元素取出作为一个地址跳转到该地址处回到main()函数）再以一个简单的图表示一下：
int avg1 = average(2, a, b); 该语句调用average() 函数时，其参数列表中有三个参数，而且是从右向左依次压栈的。
因为参数列表中最左侧的参数表示的就是该参数之后参数的个数，所以压栈顺序它在函数栈帧的最上方。当调用函数时，读取这个参数就能在此基础上明确参数的总个数，在利用for循环和arg指针就能准确的完成该函数的功能。
所以average(); 函数不管有几个参数都可以按照上面的函数栈帧的运行规律正确读取参数个数并成功完成功能。
- 您还可以看一下 AI100讲师老师的朋友圈爆款背后的计算机视觉技术与应用课程中的 朋友圈爆款背后的计算机视觉技术与应用小节, 巩固相关知识点