[ACM ] 10327

[ohya0524 (歐爺)]

        ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
             ( 未必需要依照此格式，文章條理清楚即可 )

題號：10327


遇到的問題:

(此題以AC)
本來小弟我是用bubble sort但是方法沒效率,
所以被老師要求要想出Ｏ(nlogn)的方法,
所以上網找到有人用merge sort,搞了半天終於ac...
但是我不太會解釋耶...
所以想請教各位版上大大要如何解釋在merge裡紀錄次數的方式


有問題的code： (請善用置底文的標色功能)


#include <stdio.h>
#include <stdlib.h>
int ans;
void merge(int *data, int *left, int *right, int x, int y)
{
    int i,j,k,d;
    i=j=k=d=0;

    while (i<x && j<y)
    {
       if(left[i]>right[j])
       {
         data[k++]=right[j++];  d++;
       }
       else
       {
         data[k++]=left[i++];  ans+=d;
       }
    }
    while (i<x)
    {
        data[k++]=left[i++];  ans+=d;
    }
    while (j<y)
    {
        data[k++]=right[j++];
    }
}
int mergesort( int *data , int n)
{
    int x,y,i,j,left[n>>1],right[n-(n>>1)];

    if (n<=1)  return 0;
    x=n/2;  y=n-x;

    for (i=0;i<x;i++)
      left[i]=data[i];

    for (i=0;i<y;i++)
      right[i]=data[x+i];

    mergesort(left,x);
    mergesort(right,y);
    merge(data,left,right,x,y);
}


int main(void)
{
  int i, n, data[1000];

  while(scanf("%d",&n)==1)
  {
    for (i=0;i<n;i++)
      scanf("%d",&data[i]);

    ans=0;
    mergesort(data, n);
    printf("Minimum exchange operations : %d\n",ans);
  }

}
補充說明：

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.117.180.29
推 VictorTom:去查 sorting algorithm 的 時間複雜度 看看, 會介紹這
→ VictorTom:些東西怎麼算:)
→ ohya0524:我想問的是ans的記錄方式  也就是相鄰兩元素的交換次數
推 VictorTom:你要算的應該不是交換次數, 而且element compare的次數
→ ohya0524:那d這變數要如何解釋呢
推 VictorTom:ㄟ~~d這個變數是你自己定義的, 怎麼解釋要問你拿它來幹
→ VictorTom:麻呀@_@"
推 andyisman:逆序數對