转载

算法导论(第三版)Problems2(归并插入排序、数列逆序计算）

讨论内容不说明，仅提供相应的程序。

2.1:归并插入排序θ(nlgn)

void mergeInsertionSort(int a[], int l, int r, int k) {  int m;  if(r-l+1 > k)  {   m = (l + r) / 2;   mergeInsertionSort(a, l, m, k);   mergeInsertionSort(a, m+1, r, k);   merge(a, l, m, r);  }  else if(l < r)   insertSort(a, l, r); } void insertSort(int a[], int l, int r) {  int i, j, key;  j = l;  for(i=l+1; i<=r; i++)   if(a[i] < a[j]) j = i;  if(j > l)  {   key = a[j];   a[j] = a[l];   a[l] = key;  }  for(i=l+2; i<=r; i++)  {   key = a[i];   for(j=i-1; key<a[j]; j--) a[j+1] = a[j];   a[j+1] = key;  } } void merge(int a[], int l, int m, int r) {  int i, j, k;  int n1 = m - l + 1;  int n2 = r - m;  int lArray[n1+1], rArray[n2+1];  int max = 1000;  for(i=0; i<n1; i++) lArray[i] = a[l+i];  for(i=0; i<n2; i++) rArray[i] = a[m+i+1];  lArray[n1] = max;  rArray[n2] = max;  i = 0;  j = 0;  for(k=l; k<=r; k++)  {   if(lArray[i] <= rArray[j])   {    a[k] = lArray[i];    ++i;   }   else   {    a[k] = rArray[j];    ++j;   }  } }

View Code

2.2:冒泡排序

void bubbleSort(int a[], int n) {  int i, j, tmp;  for(i=0; i<n-1; i++)   for(j=n-1; j>i; j--)    if(a[j] < a[j-1])    {     tmp = a[j];     a[j] = a[j-1];     a[j-1] = tmp;    } }

View Code

2.3: 多项式计算方法(θ(n))

int horner(int a[], int x, int n) {  int i, sum=a[n-1];  for(i=n-2; i>=0; i--) sum = a[i] + x * sum;  return sum; } int polynominal(int a[], int x, int n) {  int i, xArray[n], sum=0;  xArray[0] = 1;  for(i=1; i<n; i++) xArray[i] = x * xArray[i-1];  for(i=0; i<n; i++) sum = sum + a[i] * xArray[i];  return sum; }

View Code

2.4：计算数列的逆序θ(nlgn)

int mergeCount(int a[], int l, int r) {  int m;  if(l < r)  {   m = (l + r) / 2;   return mergeCount(a, l, m) + mergeCount(a, m+1, r) + merge(a, l, m, r);  }  return 0; } int merge(int a[], int l, int m, int r) {  int i, j, k, cnt=0;  int n1 = m - l + 1;  int n2 = r - m;  int lArray[n1+1], rArray[n2+1];  int max =10000;  for(i=0; i<n1; i++) lArray[i] = a[l+i];  for(j=0; j<n2; j++) rArray[j] = a[m+1+j];  lArray[n1] = max;  rArray[n2] = max;  i = 0;  j = 0;  for(k=l; k<=r; k++)   if(lArray[i] <= rArray[j])   {    a[k] = lArray[i];    ++i;   }   else   {    a[k] = rArray[j];    cnt += (m + j - k + 1);    ++j;   }  return cnt; }