首页 C&C++ 数据结构与算法分析

# 设我们交换元素 A [i] 和 A [i+k], 它们最初是无序的。证明去掉的逆序最少为 1 个最多为 2k-1 个

若 N=1, 则只存在一个逆序数。
若 N=K, 则 A [i] 和 A [i+k] 各存在 K-1 的逆序数，且有一个重复，即 (A [i],A [i+k]), 总共 2K-1 个。
所以去掉的逆序最少为 1 个最多为 2k-1 个。

# 下述两种对图 7 一 4 所编写的希尔排序例程的修改影响最坏情形的运行时间吗？

# a. 如果 lncrement 是偶数，则在第 2 行前从减 1。

不会，希尔排序的一个重要特性是增量之间最好不要有公因子，即增量之间互素，原始增量排序 (Hk=N/2,Hk−1=Hk/2H_k=N/2,H_{k-1}=H_k/2) 减一依旧有公因子，如 1，3，9，15..., 所以运行时间不变。

# b. 如果 lncrernent 是偶数，则在第 2 行前往 lncrement 加 1。

会，新的增量排序互素，如 1，3，5，7，9...，所以运行时间较原始增量排序小。

# 不使用递归如何实现归并排序？

一开始我想到的用栈模拟递归过程，但答案说的是从头开始由长度为 1 的顺串逐渐合并，不得不说这个思路真的牛逼，最起码我没想到。

归并排序非递归
void Mergesort( ElementType A[ ], int N )
{
     ElementType *TmpArray;
     int SubListSize, Part1Start, Part2Start, Part2End;
     TmpArray = malloc( sizeof( ElementType ) * N );
     for( SubListSize = 1; SubListSize < N; SubListSize *= 2 )
     {
          Part1Start = 0;
          while( Part1Start + SubListSize < N - 1 )
          {
               Part2Start = Part1Start + SubListSize;
               Part2End = min( N, Part2Start + SubListSize - 1 );
               Merge( A, TmpArray, Part1Start, Part2Start, Part2End );
               Part1Start = Part2End + 1;
          }
     }
}

# 对于本章中快速排序的实现方法，当所有的关键都相等时它的运行时间多少？

O(log⁡N\log{}{N})

# 假设我们改变分割策略使得当找到一个与枢纽元相同的关键字 i 和 j 都不停止。当所有关键字都相等时，为了保证快速排序正常工作，需要对程序做哪些修改。

i 和 j 加一个哨兵，哨兵值等于关键字值，当 i 和 j 等于关键字值时，触发哨兵自动停止。类似想 i 停止而 j 不停止，就只对 i 加哨兵即可。

说是这么说，可我没实际写过，多少难有可信度。

# 设我们选择中间的关键字作为枢纽元，这是否使得快速排序将不可能需要二次时间？

若每次中间的关键字恰好是排序后的第一位或最后一位，那就是最坏情形 O (N2N^2)，每次都要比较 N 次。

# 构造 20 个元素的一个排列使得对于三数中值分割且截止为 3 的快速排序，该排列尽可能地差。

同上题只要每次中间的关键字恰好是排序后的第一位或最后一位，那这个情形就是最坏情形，比如 20, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 10, 2, 12, 6, 14, 1, 16, 8, 18。

# 编写一个程序实现选择算法

我没理解这个题目的意思，书上不是有例程吗？

/*Place the kth smallest element in the kth position.*/
/*Beacause arrays start at 0, this will be index k-1.*/
void QSelect(int A[],int k,int Left,int Right)
{
  int i,j;
  int Pivot;
  if(Left+Cutoff<=Right)
  {
    Pivot = Median3(A,Left,Right);
    i = Left;j = Right-1;
    for(;;)
    {
      while(A[++i]<Pivot){}
      while(A[--j]>Pivot){}
      if(i<j)
        Swap(&A[i],&A[j]);
      else
        break;
    }
    Swap(&A[i],&A[Right-1]);//Restore Pivot
    
    if(k<=i)
      QSelect(A,k,Left,i-1);
    else if(k>i+1)
      QSelect(A,k,i+1,Right);
  }
  else//Do an Insertion Sort on the subarray
    InsertSort(A+Left,Right-Left+1);
}
# 求解下列递推关系：T(N)=(1/N)[∑i=0N−1T(i)]+cN,T(0)=0T(N) = (1/N)[ {\textstyle \sum_{i=0}^{N-1}T(i)} ]+cN,T(0)=0。
T(N)=(1/N)[∑i=1N−1T(i)]+cN,T(0)=0T(N) = (1/N)[ {\textstyle \sum_{i=1}^{N-1}T(i)} ]+cN,T(0)=0
两边乘于 N，有
NT(N)=[∑i=1N−1T(i)]+cN2NT(N) = [ {\textstyle \sum_{i=1}^{N-1}T(i)} ]+cN^2
让N=N+1N=N+1，有
(N+1)T(N+1)=[∑i=1NT(i)]+c(N+1)2(N+1)T(N+1) = [ {\textstyle \sum_{i=1}^{N}T(i)} ]+c(N+1)^2
两式相减，得
(N+1)T(N+1)−NT(N)=T(N)+2cN+c(N+1)T(N+1) -NT(N) = T(N) + 2cN + c
化简得T(N+1)=T(N)+2cN+cT(N+1) = T(N) + 2cN + c
使用叠缩求和并忽略不必要得常数项 c
T(N)=T(N−1)+2c(N−1)NT(N)=T(N-1)+\frac{2c(N-1)}{N}
T(N−1)=T(N−2)+2c(N−2)N−1T(N-1)=T(N-2)+\frac{2c(N-2)}{N-1}
......
......
T(2)=T(1)+2c∗12T(2)=T(1)+\frac{2c*1}{2}
T(1)=T(0)+2c∗01T(1)=T(0)+\frac{2c*0}{1}
T(0)=0T(0)=0
最终求得T(N)=T(0)+2c∑i=1Ni−1i≈0+2cNT(N)=T(0)+2c {\textstyle \sum_{i=1}^{N}\frac{i-1}{i} } \approx 0+2cN
所以T(N)=O(N)T(N)=O(N)。
# 设给定 N 个排过序的元素，后面跟有f(N)f(N) 个随机顺序得元素。如果f(N)f(N) 是下列情况，那么如何将全部排序？
# f(N)=O(1)f(N)=O(1)
先分割一定次数，后比较插入，毕竟只有一个元素。
# f(N)=O(log⁡N)f(N)=O(\log{}{N})
使用堆排序较好。
# f(N)=O(N)f(N)=O(\sqrt{N})
使用归并排序较好。
# f(N)f(N) 得多大使得全部数据仍然能够以 O (N) 时间排序
f(N)=O(Nlog⁡N)f(N)=O(\frac{N}{\log{}{N}})。
假设使用归并排序。
对于f(N)f(N)，有O(f(N))=O(f(N)log⁡f(N))=O(N)O(f(N))=O(\frac{f(N)}{\log{}{f(N)}})=O(N)
则对于N+f(N)N+f(N) 得最后一趟，有O(N+f(N))=O(N)+O(N)=O(N)O(N+f(N))=O(N)+O(N)=O(N)
# 证明：在 N 个元素排过序的表中找出一个元素 X 的任何算法都需要Ω(log⁡N)\Omega(\log{}{N}) 次比较。
使用书中引理 7.2：具有 L 片树叶得二叉树得深度至少是log⁡N\log{}{N}
可知在 N 个元素排过序的表中找出一个元素 X 的任何算法都需要Ω(log⁡N)\Omega (\log{}{N}) 次比较。
用定理打败定理.jpg
# 利用 Stirling 公式N!≈(N/e)N2πNN!\approx (N/e)^N\sqrt{2\pi N } 给出log⁡N!\log{}{N!} 得精确估计。
log⁡N!=log⁡(N/e)N2πN=log⁡(N/e)N+log⁡2πN\log{}{N!}=\log{}{(N/e)^N\sqrt{2\pi N }}=\log{}{(N/e)^N}+\log{}{\sqrt{2\pi N }}
忽略log⁡2πN\log{}{\sqrt{2\pi N }}, 则
log⁡N!≈NlogN−Nlog\log{}{N!}\approx Nlog{}{N}-Nlog{}
# 证明，使用桶式排序把具有范围1≤key≤M1\le key\le M 内的整数关键字的 N 个元素排序需要时间 O (M 十 N)。
O (N) 次元素插入，O (M) 用于检查所放桶得位置，总计 O (M 十 N)。
# 设有 N 个元素的数组只包含两个不同的关键字 true 和 false。给出一个 O (N) 得算法，重新排列这些元素使得所有的元素都排在 true 的元素的前面。你只能使用常数附加空间。
假设存在第 N+1 个元素 Maybe，该元素false<Maybe<truefalse< Maybe <true, 把该元素作为枢纽元进行快速排序，只需要一轮，即 O (N)。
同理，对于含有三个值 false、Maybe、true 的排序，同样假设存在第 N+1 个元素 ProbablyFalse，把该元素作为枢纽元进行快速排序，只需要两轮，第一轮false<ProbablyFalse<Maybefalse< ProbablyFalse <Maybe，第二轮Maybe<ProbablyFalse<trueMaybe< ProbablyFalse <true, 即 O (2N)。
# 给出一个算法用 7 次比较将 5 个元素排序
假设实际结果是a1>a2>a3>a4>a5a_1>a_2>a_3>a_4>a_5。
首先比较a1a_1、a2a_2, 得到a1>a2a_1>a_2, 再比较a3a_3、a4a_4 得到a3>a4a_3>a_4, 一共两次。
让a1a_1 与a3a_3、a4a_4 得到a1>a3>a4a_1>a_3>a_4, 一共一次。
让a5a_5 与a1a_1、a3a_3、a4a_4 得a1>a3>a4>a5a_1>a_3>a_4>a_5 一共三次。
最后让a2a_2 与a1a_1、a3a_3、a4a_4、a5a_5 得到a1>a2>a3>a4>a5a_1>a_2>a_3>a_4>a_5，一共一次，总和一共七次，这算是比较理想得情况了。
# 写出一个有效的希尔排序算法并比较当使用下列增量序列时的性能
# a. 希尔的原始序列
// Incremental sort is N/2 
void ShellSort(int A[],int N)
{
    int tmp;
    int i,j;
    for(int Increment=N/2;Increment> 0; Increment /=2)
    {
        for(i = Increment;i<N;i++)
        {
            tmp = A[i];
            for(j=i;j>Increment;j-=Increment)
            {
                if(tmp<A[j-Increment])
                  A[j] = A[j-Increment];
                else
                  break;
                A[j] = tmp;
            }
        }
    }
}
# b.Hibbard 的增量
#define Increment_len (10)
// generate Hibbard incremental sequence and fixed quantity is 10
static int* Hibbard()
{
  int* H = malloc(Increment_len*sizeof(int));
  if(H!= NULL)
  {
    H[0] = 1;
    for(int i=1; i<Increment_len; i++)
      H[i] = 2*H[i-1]+1;
  }
  else 
    return NULL;
  return H;
}
// Use Hibbard incremental sequence to sort
void ShellSort_Hibbard(int A[],int N)
{
  int tmp;
  int i,j;
  int* Increment = Hibbard();
  for(int k=9;k>=0;k--)
  {
    for(i = Increment[k];i<N;i++)
    {
      tmp = A[i];
      for(j = i;j>Increment[k];j-=Increment[k])
      {
        if(tmp<A[j-Increment[k]])
          A[j] = A[j-Increment[k]];
        else
          break;
        A[j] = tmp;
      }
    }
  }
  free(Increment);
}
# c.Knuth 的增量：hi=1/2(3i+1)h_i=1/2(3^i+1)
// generate Knuth incremental sequence and fixed quantity is 10
static int* Knuth()
{
  int* H = malloc(Increment_len*sizeof(int));
  if(H!= NULL)
  {
    H[0] = 1;
    for(int i=1; i<Increment_len; i++)
     H[i] = 3*H[i-1] + 1;
  }
  else
   return NULL;
  
  return H;
}
// Use Knuth incremental sequence to sort
void ShellSort_Knuth(int A[],int N)
{
  int tmp;
  int i,j;
  int* Increment = Knuth();
  for(int k=9;k>=0;k--)
  {
    for(i = Increment[k];i<N;i++)
    {
      tmp = A[i];
      for(j = i;j>Increment[k];j-=Increment[k])
      {
        if(tmp<A[j-Increment[k]])
          A[j] = A[j-Increment[k]];
        else
          break;
        A[j] = tmp;
      }
    }
  }
  free(Increment);
}
# d.Gonnet 的增量：ht=[N2.2]h_t=[\frac{N}{2.2}], 而hk=[hk+12.2]h_k=[\frac{h_{k+1}}{2.2}],(若h2=2h_2=2 则h1=1h_1=1)
// generate Gonnet incremental sequence and fixed quantity is 10
static int* Gonnet(N)
{
  int* H = malloc(Increment_len*sizeof(int));
  if(H!= NULL)
  {
    H[9] = N/2.2;
    for(int i=8; i>=0; i--)
      H[i] = H[9]/2.2;
  }
  else
   return NULL;
  
  return H;
}
// Use Gonnet incremental sequence to sort
void ShellSort_Gonnet(int A[],int N)
{
  int tmp;
  int i,j;
  int* Increment = Gonnet(N);
  for(int k=9;k>=0;k--)
  {
    for(i = Increment[k];i<N;i++)
    {
      tmp = A[i];
      for(j = i;j>Increment[k];j-=Increment[k])
      {
        if(tmp<A[j-Increment[k]])
          A[j] = A[j-Increment[k]];
        else
          break;
        A[j] = tmp;
      }
    }
  }
  free(Increment);
}
# e.Sedgewick 的增量
// generate Sedgewick incremental sequence and fixed quantity is 10
// Sedgewick incremental sequence is hi=max(9∗4^j−9∗2^j+1,4^j−3∗2^j+1)
static int* Sedgewick()
{
  int* H = malloc(Increment_len*sizeof(int));
  if(H!= NULL)
  {
    int a,b;
    H[0] = 1;
    for(int i=1;i<Increment_len;i++)
    {
      a = 9*pow(4,i)-9*pow(2,i)+1;
      b = pow(4,i)-3*pow(2,i)+1;
      H[i] = a>b?a:b;
    }
  }
  else
   return NULL;
  
  return H;
}
// Use Sedgewick incremental sequence to sort
void ShellSort_Sedgewick(int A[],int N)
{
  int tmp;
  int i,j;
  int* Increment = Sedgewick();
  for(int k=9;k>=0;k--)
  {
    for(i = Increment[k];i<N;i++)
    {
      tmp = A[i];
      for(j = i;j>Increment[k];j-=Increment[k])
      {
        if(tmp<A[j-Increment[k]])
          A[j] = A[j-Increment[k]];
        else
          break;
        A[j] = tmp;
      }
    }
  }
  free(Increment);
}
# 实现优化的快速排序算法
我寻思着想优化只能选最优得枢纽元和优先小区间排序优化了，但我不想写，就贴个例程得了。
// the mian function is Qsort() and Median3().
void QuickSort(int A[],int N)
{
  Qsort(A,0,N-1);
}
// returns median of left, Center, and Right
// order these and hide the pivot
static int Median3(int A[],int Left,int Right)
{
  int Center = (Left + Right) / 2;
  if(A[Left]>A[Center])
    Swap(&A[Left],&A[Center]);
  if(A[Left]>A[Right])
    Swap(&A[Left],&A[Right]);
  if(A[Center]>A[Right])
    Swap(&A[Center],&A[Right]);
  // Invariant: A[Left] <= A[Center] <= A[Right]
  Swap(&A[Center],&A[Right-1]);//hide pivot
  return A[Right-1];//return pivot
}
#define Cutoff (3)
static void Qsort(int A[], int Left, int Right)
{
  int i,j;
  int Pivot;
  if(Left+Cutoff<=Right)
  {
    Pivot = Median3(A, Left, Right);
    i = Left;j = Right-1;
    for(;;)
    {
      while(A[++i]<Pivot){}
      while(A[--j]>Pivot){}
      if(i<j)
        Swap(&A[i], &A[j]);
      else
        break;
    }
    Swap(&A[i], &A[Right-1]);//restore pivot
    Qsort(A,Left,i-1);
    Qsort(A,i+1,Right);
  }
  else //Do an insertion sort on the subarray
    InsertSort(A+Left,Right-Left+1);
}
# 编写一个例程读人两个用字母表示的文件并将它们合并到一起，形成第三个也是用字母表示的文件
就是满大街飞的合并文件的做法
#include <stdio.h>
#include <stdlib.h>
int main()
{
  // Open two files to be merged
  FILE *fp1 = fopen("file1.txt", "rb");
  FILE *fp2 = fopen("file2.txt", "rb");
  // Open file to store the result
  FILE *fp3 = fopen("file3.txt", "wb");
  char c;
  if (fp1 == NULL || fp2 == NULL || fp3 == NULL)
  {
    puts("Could not open files");
    exit(0);
  }
  // Copy contents of first file to file3.txt
  while ((c = fgetc(fp1)) != EOF)
      fputc(c, fp3);
  // Copy contents of second file to file3.txt
  while ((c = fgetc(fp2)) != EOF)
      fputc(c, fp3);
  printf("Merged file1.txt and file2.txt into file3.txt");
  fclose(fp1);
  fclose(fp2);
  fclose(fp3);
  return 0;
}
# 证明：任何基于比较的排序算法都需要平均O(Nlog⁡N)O(N\log{}{N}) 次比较。
比较次数可以转换为求叶子总深度可求得。
假设总共有 L 片树叶，左子树叶子数量为LLL_L, 右子树叶子数量为LRL_R。
则左子树树叶叶子总深度LL(1+log⁡LL)L_L(1+\log{}{L_L}), 右子树树叶叶子总深度LR(1+log⁡LR)L_R(1+\log{}{L_R})。
那么总的树叶叶子总深度为LRlog⁡LR+LLlog⁡LL+LL_R\log{}{L_R}+L_L\log{}{L_L}+L。
由不等式定理可以求得
LRlog⁡LR+LLlog⁡LL+L≥L/2log⁡L/2+L≥L+L(log⁡L−1)≥Llog⁡LL_R \log{}{L_R}+L_L\log{}{L_L}+L\ge L/2\log{}{L/2}+L\ge L+L(\log{}{L}-1) \ge L\log{}{L}。
所以任何基于比较的排序算法都需要平均O(Nlog⁡N)O(N\log{}{N}) 次比较，证毕。
# 提出一种算法，只用两盘磁带对一个大型文件进行排序。
将大型文件按一定规律在两个磁盘分成若干顺串，其中第一个磁盘为11、222^2、242^4、26....22i2^6....2^{2i}, 第二个磁盘11、212^1、232^3、25....22i−12^5....2^{2i-1}，最后剩余得放在最后指向得磁盘。
从第二个磁盘开始与第一个磁盘进行归并排序，并放在第一磁盘中；
之后第一个磁盘开始与第二个磁盘进行归并排序，并放在第二磁盘中，循坏上面两步直到合并完全。