quicksort.cpp

来自「比较各种排序的算法间的运行效率 自己写的不太完善」· C++ 代码 · 共 47 行

void quicksort(int *a, int n, int &contrastNum, int &moveNum)
{
     int i, j;
     int temp;
    
     if(n<=1)    return;
    
     i = 0;
     j = n-1;
     
     while(i<j)
     {
       while(a[i]<=a[j]&&i<j)     
       {
         contrastNum++;
         j--;
       }
       if(i<j)
       {
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
         moveNum+=3;
         i++;
       }
       else  break;
       while(a[j]>=a[i]&&i<j)     
       {
         contrastNum++;
         i++;
       }
       if(i<j)
       {
         temp = a[j];
         a[j] = a[i];
         a[i] = temp;
         moveNum+=3;
         j--;
       }
       else  break;
     }
     
     quicksort(a,i,contrastNum,moveNum);
     quicksort(a+i+1,n-1-i,contrastNum,moveNum);
}