算法导论 第8章 线性时间排序（计数排序、基数排序、桶排序）

时间：2021-12-30 17:08:46

合并排序和堆排序的时间复杂度为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;
}

习题 8-3 排序不同长度的数据项

/*
 *算法导论 习题8-3.a
 *首先利用计数排序对数组按位数排序
 *然后再利用基数排序对各不同分组排序
 *时间复杂度为O(n)
 */

#include <iostream>
#include <ctime>
using namespace std;

typedef int (*getCountKey)(int, int);
void countSort(int *arr, int len, int k, getCountKey getCntKey, int arg=0);
void radixSort(int *arr, int p, int r, int digitCnt);
int getDigit(int num, int d);
int getDigitCnt(int num, int arg=0);
void printArray(int arr[], int len, char *str)
{
cout << str << endl;
for (int i=0; i<len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}


int main()
{
int arr[] = {12, 8, 99, 90, 10, 3, 6, 7, 122, 100, 1000, 1340, 1200, 1802};

int len = sizeof(arr) / sizeof(arr[0]);
int k = 1;
for (int i=0; i<len; i++)
{
int temp = getDigitCnt(arr[i]);
if (temp > k)
{
k = temp;
}
}
k++;
printArray(arr, len, "原数组");
countSort(arr, len, k, getDigitCnt);
printArray(arr, len, "计数排序后");

int digitCount = getDigitCnt(arr[0]);
int pos = 0;
for (int i=0; i<len; i++)
{
int cnt = getDigitCnt(arr[i]);
if (cnt != digitCount)
{
radixSort(arr, pos, i-1, digitCount);
pos = i;
digitCount =cnt;
} else if (i == len-1) {
radixSort(arr, pos, len-1, digitCount);
}
}
printArray(arr, len, "基数排序后");

return 0;
}

void countSort(int *arr, int len, int k, getCountKey getCntKey, int arg)
{
int *arr1 = new int[len];
int *counts = new int[k]();

for (int i=0; i<len; i++)
{
counts[getCntKey(arr[i], arg)]++;
}

for (int i=1; i<k; i++)
{
counts[i] += counts[i-1];
}

for (int i=len-1; i>=0; i--)
{
arr1[counts[getCntKey(arr[i], arg)]-1] = arr[i];
counts[getCntKey(arr[i], arg)]--;
}

for (int i=0; i<len; i++)
{
arr[i] = arr1[i];
}

delete[] counts;
delete[] arr1;
}

void radixSort(int *arr, int p, int r, int digitCnt)
{
int len = r-p+1;
int *result = new int[len];
for (int i=p; i<=r; i++)
{
result[i-p] = arr[i];
}

int k = 10;

for (int i=0; i<digitCnt; i++)
{
countSort(result, len, k, getDigit, i);
}

for (int i=p; i<=r; i++)
{
arr[i] = result[i-p];
}

delete[] result;
}

int getDigit(int num, int d)
{
return (num % (int)pow(10.0, d+1)) / pow(10.0, d);
}

int getDigitCnt(int num, int arg)
{
num = num / 10;
int digitCnt = 1;
while (num)
{
num /= 10;
digitCnt++;
}
return digitCnt;
}

/*
 *算法导论 习题8-3.b
 *首先利用计数排序对数组按首位排序
 *然后数组根据字符串的首位不同而分组，
 *各不同分组再递归的根据次高位计数排序
 *但是必须注意在排序过程中不断去掉长度较小的字符串
 *时间复杂度为O(n)
 */

#include <iostream>
#include <ctime>
#include <cstring>
using namespace std;

typedef int (*getCountKey)(char*, int);
void countSort(char **str, int start, int end, int k, getCountKey getKey, int arg);
int getLetterPos(char* str, int arg);
void stringSort(char **str, int start, int end, int index);

void printArray(char** arr, int len, char *str)
{
cout << str << endl;
for (int i=0; i<len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}


int main()
{
char* str[] = {"fwse", "asd", "bes", "a", "ce", "hed", "wdr", "ccw", "cs", "cfe", "acb", "bb", "bbb"};
int len = 13;
printArray(str, len, "原字符串数组");
stringSort(str, 0, len-1, 0);
printArray(str, len, "排序后字符串数组");
return 0;
}

void stringSort(char **str, int start, int end, int index)
{
if (start == end)
return;
int k = 'a'+26-'A'+1;

//首先根据首字母计数排序
countSort(str, start, end, k, getLetterPos, index);

int pos = start;
char letter = str[start][index];
for (int i=start; i<=end; i++)
{
char temp = str[i][index];
if (letter != temp && letter != '\0')
{//出现新的分组，并且字符串还没结束的继续递归排序
stringSort(str, pos, i-1, index+1);
pos = i;
letter = temp;
}
}
if (letter != '\0')
stringSort(str, pos, end, index+1);
}

void countSort(char **str, int start, int end, int k, getCountKey getKey, int arg)
{
int len = end-start+1;
int *counts = new int[k]();
char **result =new char*[len];

for (int i=start; i<=end; i++)
{
counts[getKey(str[i], arg)]++;
}

for (int i=1; i<k; i++)
{
counts[i] += counts[i-1];
}

for (int i=end; i>=start; i--)
{
result[counts[getKey(str[i], arg)]-1] = str[i];
counts[getKey(str[i], arg)]--;
}

for (int i=0; i<len; i++)
{
str[i+start] = result[i];
}

delete[] counts;
delete[] result;
}

int getLetterPos(char* str, int arg)
{
return str[arg] == '\0' ? 0 : str[arg]-64;
}


标签：

相关文章