首页 > 代码库 > 算法导论 第8章 线性时间排序
算法导论 第8章 线性时间排序
合并排序和堆排序的时间复杂度为O(nlgn),插入排序和冒泡排序的时间复杂度为O(n^2),快速排序的时间复杂度在平均情况下是O(nlgn),这些排序算法都是通过对元素进行相互比较从而确定顺序的,因此都叫比较排序。
比较排序可以看做是决策树(一个满二叉树),因为每一次比较都是一个分支。n个元素的序列,其排序的结果有 n! 种可能(n个元素的全排),所以这个决策树有 n! 个叶子结点,假设树的高度为h,则有:n! <= 2^h,所以h >= lg(n!) = Ω(nlgn)。一次比较排序就是从决策树的根节点走到叶节点,所以比较排序的时间复杂度为Ω(nlgn)。
而计数排序、基数排序和桶排序都是非比较排序,其时间复杂度为O(n),但是这三种排序算法都不是原地排序,占用内存空间较多,而比较排序算法大多都是原地排序。
/* * 算法导论 第八章 线性时间排序 * 计数排序、基数排序和桶排序 */ #include <iostream> #include <cmath> #include <vector> #include <ctime> using namespace std; void printArray(int arr[], int len, char *str) { cout << str << endl; for (int i=0; i<len; i++) { cout << arr[i] << " "; } cout << endl; } int* countingSort(int *arr, int len, int k); int* radixSort(int *arr, int len, int d); int getDigit(int num, int d); int* bucketSort(int *arr, int len, int maxNum); int main() { int len = 30; int k = 10; srand(time(NULL)); int *arr = new int[len]; for (int i=0; i<len; i++) { arr[i] = rand() % k; } //计数排序 printArray(arr, len, "计数排序前数组"); int *result = countingSort(arr, len, k); printArray(result, len, "计数排序后数组"); delete[] result; //基数排序 for (int i=0; i<len; i++) { arr[i] = 100 + rand() % 500; } printArray(arr, len, "基数排序前数组"); result = radixSort(arr, len, 3); printArray(result, len, "基数排序后数组"); delete[] result; //桶排序 for (int i=0; i<len; i++) { arr[i] = rand() % 100; } printArray(arr, len, "桶排序前数组"); result = bucketSort(arr, len, 100); printArray(result, len, "桶排序后数组"); delete[] result; return 0; } /* * 计数排序 * 时间复杂度为O(n+k) * 使用计数排序需要在所有元素都在一个小的范围内,即k远小于n * 在k=O(n)时,时间复杂度为O(n) */ int* countingSort(int *arr, int len, int k) { int *numCount = new int[k](); int *result = new int[len]; //numCount中存储等于i的元素个数 for (int i=0; i<len; i++) { numCount[arr[i]]++; } //numCount中存储小于等于i的元素个数 for (int i=1; i<k; i++) { numCount[i] += numCount[i-1]; } //从后至前依次对元素进行排序,保证稳定性,也可以从前往后,但是排序就不稳定了 for (int i=len-1; i>=0; i--) { result[numCount[arr[i]]-1] = arr[i]; numCount[arr[i]]--; } delete[] numCount; return result; } /* * 基数排序 * 是建立在计数排序的基础之上的,计数排序的稳定性很重要 * 否则基数排序就会出错,例如数组[27, 15, 43, 42],如果子排序过程不稳定 * 则结果就为[15, 27, 43, 42] * 时间复杂度为O(d*(n+k)),在d为常数,k=O(n)时,时间复杂度为O(n) */ int* radixSort(int *arr, int len, int d) { int *A = new int[len]; for (int i=0; i<len; i++) A[i] = arr[i]; for (int j=0; j<d; j++) { int k = 10; int *numCount = new int[k](); int *result = new int[len]; //numCount中存储等于i的元素个数 for (int i=0; i<len; i++) { numCount[getDigit(A[i], j)]++; } //numCount中存储小于等于i的元素个数 for (int i=1; i<k; i++) { numCount[i] += numCount[i-1]; } //从后至前依次对元素进行排序,保证稳定性,也可以从前往后,但是排序就不稳定了 for (int i=len-1; i>=0; i--) { result[numCount[getDigit(A[i], j)]-1] = A[i]; numCount[getDigit(A[i], j)]--; } delete[] A; delete[] numCount; A = result; } return A; } int getDigit(int num, int d) { return (num % (int)pow(10.0, d+1)) / pow(10.0, d); } /* * 桶排序 * 在输入符合均匀分布时,桶排序的效果较好 * 将各个元素分布在n个桶中,每个桶内再使用插入排序 * 只要各个桶的尺寸的平方和与总的元素数呈线性关系 * 则其时间复杂度就为O(n) */ int* bucketSort(int *arr, int len, int maxNum) { //建立n个桶 vector<int> *result = new vector<int>[len]; //将各个元素分布到各个桶内 for (int i=0; i<len; i++) { result[(int)((arr[i]/(double)maxNum)*len)].push_back(arr[i]); } for (int i=0; i<len; i++) { int n = result[i].size(); //插入排序 for (int j=1; j<n; j++) { int k = j - 1; int key = result[i][j]; while (k>=0 && result[i][k]>key) { result[i][k+1] = result[i][k]; k--; } result[i][k+1] = key; } } //合并各个桶中的元素 for (int i=0, j=0; j<len; j++) { int length = result[j].size(); for (int k=0; k<length; k++) { arr[i++] = result[j][k]; } } delete[] result; return arr; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。