本文共 13036 字，大约阅读时间需要 43 分钟。

#include 
   
    #include
    
     using namespace std;template
     
      inline void swap(E A[], int i, int j) {
   	E temp = A[i];	A[i] = A[j];	A[j] = temp;}template 
      
       void insertsort(E A[], int n,int count1[],int count2[]) {
    // Insertion Sort	int k[10] = {
    0,1,2,3,4,5,6,7,8,9 };	int s=0;	for (int i = 1; i < n; i++) // Insert i’th record	{
   		for (int j = i; j > 0 ; j--)		{
   			count1[0]++;			if ((A[j] < A[j - 1]))			{
   				swap(A, j, j - 1);				count2[0]++;			}			else {
   				break;			}			//s = k[j];		}				/*if (s > 0) {			count1[0]++;		}*/	}}template 
       
        void bubblesort(E A[], int n, int count1[], int count2[]) {
    // Bubble Sort	for (int i = 0; i < n - 1; i++) // Bubble up i’th record		for (int j = n - 1; j > i; j--)		{
   			count1[0]++;			if (A[j] < A[j - 1])			{
   				swap(A, j, j - 1);				count2[0]++;			}		}}template 
        
         void selectsort(E A[], int n, int count1[], int count2[]) { // Selection Sort for (int i = 0; i < n - 1; i++) { // Select i’th record int lowindex = i; // Remember its index for (int j = n - 1; j > i; j--) // Find the least value { count1[0]++; if (A[j] < A[lowindex]) { lowindex = j; // Put it in place count2[0]++; } swap(A, i, lowindex); } }}template 
         
          void inssort2(E A[], int n, int incr, int count1[], int count2[]) { for (int i = incr; i < n; i += incr) { for (int j = i; j >= incr ; j -= incr) { count1[0]++; if ((A[j] < A[j - incr])) { swap(A, j, j - incr); count2[0]++; } else { break; } } }}template 
          
           void shellsort(E A[], int n, int count1[], int count2[]) { // Shellsort for (int i = n / 2; i > 2; i /= 2) // For each increment for (int j = 0; j < i; j++) // Sort each sublist inssort2
           
            (&A[j], n - j, i, count1, count2); inssort2
            
             (A, n, 1, count1, count2);}template 
             
              void mergesort(E A[], E temp[], int left, int right, int count1[], int count2[]) { if (left == right) return; // List of one element int mid = (left + right) / 2; mergesort
              
               (A, temp, left, mid, count1, count2); mergesort
               
                (A, temp, mid + 1, right, count1, count2); for (int i = left; i <= right; i++) // Copy subarray to temp temp[i] = A[i]; // Do the merge operation back to A int i1 = left; int i2 = mid + 1; for (int curr = left; curr <= right; curr++) { if (i1 == mid + 1) // Left sublist exhausted A[curr] = temp[i2++]; else if (i2 > right) // Right sublist exhausted A[curr] = temp[i1++]; else if (temp[i1]< temp[i2]) A[curr] = temp[i1++]; else A[curr] = temp[i2++]; count2[0]++; count1[0]++; }}template 
                
                 inline int partition(E A[], int l, int r, E& pivot, int count1[], int count2[]) { do { // Move the bounds inward until they meet while (A[++l] < pivot); // Move l right and while ((l < r) && (pivot < A[--r])); // r left swap(A, l, r); // Swap out-of-place values count2[0]++; count1[0]++; } while (l < r); // Stop when they cross return l; // Return first position in right partition}template 
                 
                  void qsort(E A[], int i, int j, int count1[], int count2[]) { // Quicksort if (j <= i) return; // Don’t sort 0 or 1 element int pivotindex = (i+j)/2; swap(A, pivotindex, j); // Put pivot at end // k will be the first position in the right subarray int k; k= partition
                  
                   (A, i - 1, j, A[j],count1, count2); swap(A, k, j); // Put pivot in place count2[0]++; count1[0]++; qsort
                   
                    (A, i, k - 1,count1, count2); qsort
                    
                     (A, k + 1, j,count1, count2);}template 
                     
                      class HeapSort { public: void AdjustDown(int* A, int root, int n) { int parent = root; int child = parent * 2 + 1; // 左孩子 while (child < n) { if ((child + 1) < n && A[child + 1] > A[child]) { ++child; } if (A[child] > A[parent]) { swap(A[child], A[parent]); parent = child; child = parent * 2 + 1; } else break; } } int* heapSort(int* A, int n, int count1[], int count2[]) { // write code here assert(A); // 找到倒数第一个非叶子节点----- 建大堆 for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(A, i, n); count1[0]++;//建大堆好像只涉及交换？ } int end = n - 1; while (end > 0) { swap(A[0], A[end]); count2[0]++; count1[0]++; AdjustDown(A, 0, end); // end其实就是不算后面的一个元素，原因是最后一个节点已经是最大的 end--; } return A; }};int maxbit(int data[], int n){ int d = 1; //保存最大的位数 int p = 10; for (int i = 0; i < n; ++i) { while (data[i] >= p) { p *= 10; ++d; } } return d;}void radixsort(int data[], int n,int count1[],int count2[]) //基数排序{ int d = maxbit(data, n); int tmp[100]; int count[10]; //计数器 int i, j, k; int radix = 1; for (i = 1; i <= d; i++) //进行d次排序 { for (j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for (j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; count1[0]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; count2[0]++; } for (j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; }}int main(){ int count1[1] = { 0 }; int count2[1] = { 0 }; int b[5] = { 1,2,3,4,5 }; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; insertsort(b, 5,count1,count2); //HeapSort
                      
                        b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下插入排序比较次数为：" << count1[0] << endl; cout << "最优条件下插入排序交换次数为：" << count2[0] << endl; int a[5] = { 1,3,2,5,4 }; count1[0] = 0 ; count2[0] = 0 ; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; insertsort(a, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下插入排序比较次数为：" << count1[0] << endl; cout << "一般条件下插入排序交换次数为：" << count2[0] << endl; int c[5] = { 5,4,3,2,1 }; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; insertsort(c, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下插入排序比较次数为：" << count1[0] << endl; cout << "最差条件下插入排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; bubblesort(b, 5, count1, count2); //HeapSort
                       
                         b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下冒泡排序比较次数为：" << count1[0] << endl; cout << "最优条件下冒泡排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; bubblesort(a, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下冒泡排序比较次数为：" << count1[0] << endl; cout << "一般条件下冒泡排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; bubblesort(c, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下冒泡排序比较次数为：" << count1[0] << endl; cout << "最差条件下冒泡排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; selectsort(b, 5, count1, count2); //HeapSort
                        
                          b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下选择排序比较次数为：" << count1[0] << endl; cout << "最优条件下选择排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; selectsort(a, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下选择排序比较次数为：" << count1[0] << endl; cout << "一般条件下选择排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; selectsort(c, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下选择排序比较次数为：" << count1[0] << endl; cout << "最差条件下选择排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; shellsort(b, 5, count1, count2); //HeapSort
                         
                           b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下shell排序比较次数为：" << count1[0] << endl; cout << "最优条件下shell排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; shellsort(a, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下shell排序比较次数为：" << count1[0] << endl; cout << "一般条件下shell排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; shellsort(c, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下shell排序比较次数为：" << count1[0] << endl; cout << "最差条件下shell排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; int temp[5]; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; mergesort(b, temp,0,4, count1, count2); //HeapSort
                          
                            b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下归并排序比较次数为：" << count1[0] << endl; cout << "最优条件下归并排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; mergesort(a, temp, 0, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下归并排序比较次数为：" << count1[0] << endl; cout << "一般条件下归并排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; mergesort(c, temp, 0, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下归并排序比较次数为：" << count1[0] << endl; cout << "最差条件下归并排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; HeapSort
                           
                             s; s.heapSort(b, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下堆排序比较次数为：" << count1[0] << endl; cout << "最优条件下堆排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; s.heapSort(a, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下堆排序比较次数为：" << count1[0] << endl; cout << "一般条件下堆排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; s.heapSort(c, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下堆排序比较次数为：" << count1[0] << endl; cout << "最差条件下堆排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; a[i] = i + 1; c[i] = i + 1; } for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; qsort(b,0, 4, count1, count2); //HeapSort
                            
                              b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下快速排序比较次数为：" << count1[0] << endl; cout << "最优条件下快速排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; qsort(a, 0, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下快速排序比较次数为：" << count1[0] << endl; cout << "一般条件下快速排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; qsort(c, 0, 4, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下快速排序比较次数为：" << count1[0] << endl; cout << "最差条件下快速排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { b[i] = i + 1; c[i] = -i + 5; } a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 5; a[4] = 4; for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; radixsort(b, 5, count1, count2); //HeapSort
                             
                               b; //b.heapSort(a, 4); for (int i = 0; i < 5; i++) { cout << b[i] << " "; } cout << endl; cout << "最优条件下基数排序比较次数为：" << count1[0] << endl; cout << "最优条件下基数排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; radixsort(a, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << a[i] << " "; } cout << endl; cout << "一般条件下基数排序比较次数为：" << count1[0] << endl; cout << "一般条件下基数排序交换次数为：" << count2[0] << endl; count1[0] = 0; count2[0] = 0; for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; radixsort(c, 5, count1, count2); for (int i = 0; i < 5; i++) { cout << c[i] << " "; } cout << endl; cout << "最差条件下基数排序比较次数为：" << count1[0] << endl; cout << "最差条件下基数排序交换次数为：" << count2[0] << endl; system("pause");}
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

结果如下

转载地址：http://dvcki.baihongyu.com/