单纯形算法的c语言源代码

template<class Elem> 
int Partition (Elem R[], int low, int high) { 
// 交换记录子序列R[low..high]中的记录，使 
// 枢轴记录到位，并返回其所在位置，此时， 
// 在它之前（后）的记录均不大（小）于它 
 R[0] = R[low]; 
          // 用子表的第一个记录作枢轴记录 
 pivotkey = R[low].key;    // 枢轴记录关键字 
 while (low<high) { 
            // 从表的两端交替地向中间扫描 
while(low<high&& R[high].key>=pivotkey) 
  --high; 
R[low] = R[high]; 
      // 将比枢轴记录小的记录移到低端 
while (low<high && R[low].key<=pivotkey) 
  ++low; 
R[high] = R[low]; 
      // 将比枢轴记录大的记录移到高端 
 } 
 R[low] = R[0];             // 枢轴记录到位 
 return low;             // 返回枢轴位置 
} // Partition 
[III]快速排序 
在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。  快速排序的算法描述如下: 
template<class Elem> 
void QSort (Elem R[], int low, int high) { 
 // 对记录序列R[low..high]进行快速排序 
 if (low < high-1) {             // 长度大于1 
pivotloc = Partition(L, low, high); 
            // 将L.r[low..high]一分为二 
QSort(L, low, pivotloc-1); 
// 对低子表递归排序，pivotloc是枢轴位置 
QSort(L, pivotloc+1, high); 
                  // 对高子表递归排序 
 } 
} // QSort 

template<class Elem> 
void QuickSort(Elem R[],  int n) { 
 // 对记录序列进行快速排序 
  QSort(R, 1, n); 
} // QuickSort 
快速排序的时间分析 
 假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间 
T(n) = Tpass(n)+T(k-1)+T(n-k) 
其中 Tpass(n)为对n个记录进行一次划分所需时间，若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同，由此可得快速排序所需时间的平均值为： 

         
设 Tavg(1)≤b 
则可得结果 
       
通常，快速排序被认为是在所有同数量级O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。 
为避免出现这种情况，需在进行快排之前，进行“予处理”，即：比较 R(s).key, R(t).key和R[?(s+t)/2?.key，然后取关键字为“三者之中”的记录为枢轴记录。 
三． 选择排序：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度; 
[I]简单选择排序 
 假设排序过程中，待排记录序列的状态为： 
并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列。 
简单选择排序的算法描述如下： 
template<class Elem> 
void SelectSort (Elem R[], int n ) { 
 // 对记录序列R[1..n]作简单选择排序。 
 for (i=1; i<n; ++i) { 
          // 选择第i小的记录，并交换到位 
j = SelectMinKey(R, i);        
      // 在R[i..n]中选择key最小的记录 
if (i!=j) R←→R[j]; 
                  // 与第i个记录交换 
 } 
} // SelectSort 
时间性能分析 
  对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为 
         
移动记录的次数，最小值为0, 最大值为3(n-1) 
[II]堆排序 
  堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。 
堆的定义: 
 堆是满足下列性质的数列{r1, r2, …，rn}： 
         或    
若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。 
由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。 
 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是： 
 先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。 
 所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。 
堆排序的算法如下所示： 
template<class Elem> 
void HeapSort ( Elem R[], int n ) { 
 // 对记录序列R[1..n]进行堆排序。 
 for ( i=n/2; i>0; --i ) 
                    // 把R[1..n]建成大顶堆 
   HeapAdjust ( R, i, n ); 
 for ( i=n; i>1; --i ) { 
R[1]←→R;            
        // 将堆顶记录和当前未经排序子序列 
        // R[1..i]中最后一个记录相互交换 
HeapAdjust(R, 1, i-1);              
        // 将R[1..i-1] 重新调整为大顶堆 
 } 
} // HeapSort 
其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。 
Template<class Elem> 
void HeapAdjust (Elem R[], int s, int m) { 
 // 已知R[s..m]中记录的关键字除R.key之 
 // 外均满足堆的定义，本函数调整R 的关 
 // 键字，使R[s..m]成为一个大顶堆（对其中 
 // 记录的关键字而言） 
 rc = R; 
 for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选 
if ( j<m && R[j].key<R[j+1].key )  ++j; // j为key较大的记录的下标 
   if ( rc.key >= R[j].key )  break; // rc应插入在位置s上 
   R = R[j];  s = j; 
   } 
   R = rc; // 插入 
} // HeapAdjust 
堆排序的时间复杂度分析： 
1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1); 
2．对n个关键字，建成深度为h(=?log2n?+1)的堆，所需进行的关键字比较的次数至多为4n; 
3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过 
2(?log2(n-1)?+ ?log2(n-2)?+ …+log22)<2n(?log2n?) 
因此，堆排序的时间复杂度为O(nlogn) 
四．归并排序：是通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。 
  在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 
归并为一个有序序列。 
“归并”算法描述如下： 
template<class Elem> 
void Merge (Elem SR[], Elem TR[], int i, int m, int n) { 
 // 将有序的SR[i..m]和SR[m+1..n]归并为 
 // 有序的TR[i..n] 
 for (j=m+1, k=i;  i<=m && j<=n;  ++k)    
 {        // 将SR中记录由小到大地并入TR 
   if (SR.key<=SR[j].key)  TR[k] = SR[i++]; 
   else TR[k] = SR[j++]; 
 } 
 if (i<=m) TR[k..n] = SR[i..m]; 
              // 将剩余的SR[i..m]复制到TR 
 if (j<=n) TR[k..n] = SR[j..n]; 
               // 将剩余的SR[j..n]复制到TR 
} // Merge 
归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。 
 这是一种自顶向下的分析方法： 
如果记录无序序列R[s..t]的两部分R[s..?(s+t)/2?]和R[?(s+t)/2+1..t?分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。 
template<class Elem> 
void Msort ( Elem SR[], Elem TR1[], int s, int t ) { 
 // 将SR[s..t]进行2-路归并排序为TR1[s..t]。 
 if (s==t)  TR1 = SR; 
 else { 
m = (s+t)/2; 
 // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] 
Msort (SR, TR2, s, m); 
  // 递归地将SR[s..m]归并为有序的TR2[s..m] 
Msort (SR, TR2, m+1, t); 
 //递归地SR[m+1..t]归并为有序的TR2[m+1..t] 
Merge (TR2, TR1, s, m, t); 
 // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] 
 } 
} // MSort 
   
template<class Elem> 
void MergeSort (Elem R[]) { 
 // 对记录序列R[1..n]作2-路归并排序。 
  MSort(R, R, 1, n); 
} // MergeSort 

 容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。