本文共 3785 字，大约阅读时间需要 12 分钟。
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) { // Insertion Sort for (int i = 1; i < n; i++) // Insert i’th record for (int j = i; (j > 0)&&(A[j] void bubblesort(E A[], int n) { // Bubble Sort for (int i = 0; i < n - 1; i++) // Bubble up i’th record for (int j = n - 1; j > i; j--) if (A[j] < A[j - 1]) swap(A, j, j - 1);}template void selectsort(E A[], int n) { // 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 if (A[j]< A[lowindex]) lowindex = j; // Put it in place swap(A, i, lowindex); }}template void inssort2(E A[], int n, int incr) { for (int i = incr; i < n; i += incr) for (int j = i; (j >= incr) && (A[j] void shellsort(E A[], int n) { // 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); inssort2 (A, n, 1);}template void mergesort(E A[], E temp[], int left, int right) { if (left == right) return; // List of one element int mid = (left + right) / 2; mergesort (A, temp, left, mid); mergesort (A, temp, mid + 1, right); 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++]; }}template inline int partition(E A[], int l, int r, E& pivot) { 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 } while (l < r); // Stop when they cross return l; // Return first position in right partition}template void qsort(E A[], int i, int j) { // Quicksort if (j <= i) return; // Don’t sort 0 or 1 element int pivotindex = findpivot(A, i, j); swap(A, pivotindex, j); // Put pivot at end // k will be the first position in the right subarray int k = partition (A, i - 1, j, A[j]); swap(A, k, j); // Put pivot in place qsort (A, i, k - 1); qsort (A, k + 1, j);}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) { // write code here assert(A); // 找到倒数第一个非叶子节点----- 建大堆 for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(A, i, n); } int end = n - 1; while (end > 0) { swap(A[0], A[end]); 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 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]++; } 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]--; } for (j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; }}int
转载地址：http://bvcki.baihongyu.com/