内嵌汇编与C/C++实现的冒泡排序,快速排序算法排序500W个数据对比

浏览数：60 / 时间：2015年06月08日

内嵌汇编是微软为了提高程序的直接操作硬件能力,以及实现大任务程序效率的提高,而嵌入在VC中的,他不依赖于汇编器对内嵌汇编代码进行汇编,这些内嵌汇编代码由C编译器内部实现,可以使程序好像自陷到汇编状态一样。这意味着你如果在C/C++程序中使用了 inline asm进行汇编那么就注定无法跨平台的，对于没有汇编基础的同学是需要去学习下王爽的8086汇编程序设计。,因为有些时候C++程序员是不得不懂这些东西的 ,否则你永远无法知道编译器为你的函数做了什么,.你还有哪些地方需要优化, 不管处于什么目的我感觉作为C++程序员是需要懂得的。

身边的一位大哥给我讲,用汇编不一定会比C/C++要快这一点我很同意。所以说程序的效率不单单是所操作的语言层次决定,更多的是程序编写者的代码的质量的高低决定。

内嵌汇编在C/C++中通过

实际发现 500W条数据排序结果如下:

算法名称内嵌汇编算法时间 C/C++算法时间

冒泡排序 5W数据慢的要死 5W数据慢的要死

快速排序 600ms左右 500ms左右

------------------为啥会出现快速排序算法,汇编出来的结果还没有C/C++效率高呢,原因就是我写的内嵌汇编没有编译器自动生成的效率高.

也就是代码质量不高的缘故。。~~

_asm
{
   ...
}
_asm  ....

引入汇编代码,可以使程序自陷入汇编状态,MMX汇编指令被大量应用于处理媒体引用中。。

下面是冒泡排序代的内嵌汇编实现函数:

时间复杂度 最好  T(n)=O(n)~O(n*n)  稳定算法

#define SIZE   10  
void SortBubble(int arr[],int sizen)
{
	int   *p;  
	p=arr-1;   //&a[0]-1 
	__asm  
	{  
		mov   esi,p;  
		mov   ecx,sizen;  
_outter:  
		mov   edx,ecx;
_inner:  
		cmp edx,ecx    ;去掉相等情况
		jz  _exchange_no
		mov   eax,[esi+ecx*4];  ;在函数内部不可以直接通过数组下标获取传递的数组 只能通过指针 进行寻址
		mov   ebx,[esi+edx*4 ];  
		cmp   eax,ebx;  
		jnb   _exchange_no;  
		mov   [esi+ecx*4],ebx;   ;交换连个元素 
		mov   [esi+edx*4],eax;  
_exchange_no:  
		dec   edx;  
		jnz   _inner;  
		loop   _outter;  
	}  
}

冒泡排序结果如图

用内嵌汇编实现快速排序算法

//堆栈中 内存地位先存  栈由高地址向低地址延伸 
//esp -xxx
//注意参数名字不要和内嵌汇编 关键字冲突
void  QuickSortAsm(int arr[],int lowIndex,int highIndex)
{  
    int*p=arr;  //为了寻址方便
    int  begin; //
    int  end; //
    __asm
    {  
        //;mov eax,[ebp+16] 堆栈高地址向低
       //使用寄存器 
       mov   eax,lowIndex  ;index first
       mov   ebx,highIndex ;index last
       cmp   eax,ebx  ;退程序  
       jg    _exit_func  
       mov   esi,p         ;存储数组地址-1用于寻址使用
       mov   edx,[esi+4*eax]          ;存放key
_outer:cmp   eax,ebx           ; 如果index first >index end 
       jnb   _endLable         ;  不符合条件退出                        
_find1: cmp   eax,ebx           ;进入第一层循环
       jnb   _inner1           ;条件1
       ;从后寻找第一个小于key的值 
       cmp   [esi+4*ebx],edx  ;从后面开始比较数组元素和edx
       jb    _inner1          ;找出右边第一个小于key的数组元素
       sub   ebx,1            ;last index -1  last=last-1
       jmp  _find1            ;跳转到循环头
_inner1:
       mov ecx,[esi+4*ebx]    ;找到小于交换值 
       mov [esi+4*eax],ecx
_find2: cmp   eax,ebx           ;进入第一层循环
        jnb   _inner2           ;条件1
        ;从后寻找第一个小于key的值 
        cmp   [esi+4*eax],edx  ;从左边找第一个大于key的元素 
        jg    _inner2          ;针对有符号数
        add   eax,1            ;first index+1  
        jmp  _find2            ;跳转到循环头
_inner2:
       mov ecx,[esi+4*eax]     ;将第一个大于的 和 轴交换
       mov [esi+4*ebx],ecx
       jmp _outer;
_endLable:
       mov [esi+4*eax],edx  ;轴复位  
       ///进行递归   参数自由向左
       mov  begin,eax ;
       mov  end,ebx   
    }
//  QuickSortAsm(arr,lowIndex,begin-1);
//     QuickSortAsm(arr,begin+1,highIndex);
    _asm
    {
        mov    ecx,begin  ; 递归1
        sub    ecx,1      ;index -1 
        push   ecx        ;
        mov    edx,lowIndex ;  
        push   edx  
        mov    eax,arr
        push   eax  
        call        QuickSortAsm
        add         esp,0Ch    ;堆栈平衡
        mov         ecx,highIndex  ;递归2
        push        ecx  
        mov         edx,begin  
        add         edx,1  
        push        edx  
        mov         eax,arr  
        push        eax  
        call        QuickSortAsm 
        add         esp,0Ch   ;恢复堆栈

    }
_exit_func: 
    return ;
}

如图

冒泡排序算法的C/C++实现:

// 时间复杂度 最好  T(n)=O(n)~O(n*n)  稳定算法   
void  SortBubbleC(int arr[],int sizen)
{
     bool flag=true ;//若无交换 直接退出
     int tem;
     for(int i=0;i<sizen-1&flag;i++)
     {   
         flag=false ;
         for(int j=0;j<sizen-i-1;j++) //内序冒泡
         {   
             if(arr[j]>arr[j+1])
             {   
                 flag=true ;
                 tem=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=tem;
               
             }
         }
  
     }
}

如图

C/C++快速排序算法的实现

//C/C++的快速排序 
void  QuickSortC(int arr[],int low,int high)
{
    if(low>high)
		return ;
	int begin=low ,end=high,key=arr[low];
	while(begin<end)
	{
		while(begin<end&&arr[end]>=key)
			--end;
		arr[begin]=arr[end];
		while(begin<end&&arr[begin]<=key)
			++begin;
		arr[end]=arr[begin];
	}
	arr[begin]=key ;
	QuickSortC(arr,0,begin-1);
	QuickSortC(arr,begin+1,high);
}