算法导论 第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; ilen; 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; ilen; i++)
	{
		arr[i] = rand() % k;
	}

	//计数排序
	printArray(arr, len, "计数排序前数组");
	int *resu<  = countingSort(arr, len, k);
	printArray(resu< , len, "计数排序后数组");
	delete[] resu< ;

	//基数排序
	for (int i=0; ilen; i++)
	{
		arr[i] = 100 + rand() % 500;
	}
	printArray(arr, len, "基数排序前数组");
	resu<  = radixSort(arr, len, 3);
	printArray(resu< , len, "基数排序后数组");
	delete[] resu< ;

	//桶排序
	for (int i=0; ilen; i++)
	{
		arr[i] = rand() % 100;
	}
	printArray(arr, len, "桶排序前数组");
	resu<  = bucketSort(arr, len, 100);
	printArray(resu< , len, "桶排序后数组");
	delete[] resu< ;

	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 *resu<  = new int[len];
	
	//numCount中存储等于i的元素个数
	for (int i=0; ilen; i++)
	{
		numCount[arr[i]]++;
	}

	//numCount中存储小于等于i的元素个数
	for (int i=1; ik; i++)
	{
		numCount[i] += numCount[i-1];
	}

	//从后至前依次对元素进行排序,保证稳定性,也可以从前往后,但是排序就不稳定了
	for (int i=len-1; i=0; i--)
	{
		resu< [numCount[arr[i]]-1] = arr[i];
		numCount[arr[i]]--;
	}

	delete[] numCount;
	return resu< ;
}

/*
 *	基数排序
 *	是建立在计数排序的基础之上的,计数排序的稳定性很重要
 *	否则基数排序就会出错,例如数组[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; ilen; i++)
		A[i] = arr[i];
	for (int j=0; jd; j++)
	{
		int k = 10;
		int *numCount = new int[k]();
		int *resu<  = new int[len];

		//numCount中存储等于i的元素个数
		for (int i=0; ilen; i++)
		{
			numCount[getDigit(A[i], j)]++;
		}

		//numCount中存储小于等于i的元素个数
		for (int i=1; ik; i++)
		{
			numCount[i] += numCount[i-1];
		}

		//从后至前依次对元素进行排序,保证稳定性,也可以从前往后,但是排序就不稳定了
		for (int i=len-1; i=0; i--)
		{
			resu< [numCount[getDigit(A[i], j)]-1] = A[i];
			numCount[getDigit(A[i], j)]--;
		}
		delete[] A;
		delete[] numCount;
		A = resu< ;
	}
	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个桶
	vectorint *resu<  = new vectorint[len];
	//将各个元素分布到各个桶内
	for (int i=0; ilen; i++)
	{
		resu< [(int)((arr[i]/(double)maxNum)*len)].push_back(arr[i]);
	}

	for (int i=0; ilen; i++)
	{
		int n = resu< [i].size();
		//插入排序
		for (int j=1; jn; j++)
		{
			int k = j - 1;
			int key = resu< [i][j];
			while (k=0  resu< [i][k]key)
			{
				resu< [i][k+1] = resu< [i][k];
				k--;
			}
			resu< [i][k+1] = key;
		}
	}
	//合并各个桶中的元素
	for (int i=0, j=0; jlen; j++)
	{
		int len >h = resu< [j].size();
		for (int k=0; klen >h; k++)
		{
			arr[i++] = resu< [j][k];
		}
	}

	delete[] resu< ;
	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; ilen; 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; ilen; 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; ilen; 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; ilen; i++)
	{
		counts[getCntKey(arr[i], arg)]++;
	}

	for (int i=1; ik; 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; ilen; 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 *resu<  = new int[len];
	for (int i=p; i=r; i++)
	{
		resu< [i-p] = arr[i];
	}

	int k = 10;
	
	for (int i=0; idigitCnt; i++)
	{
		countSort(resu< , len, k, getDigit, i);
	}

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

	delete[] resu< ;
}

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; ilen; 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 **resu<  =new char*[len];

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

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

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

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

	delete[] counts;
	delete[] resu< ;
}

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


最新回复(0)
/jishutwjRtttgAhZXnU4KlgYNmFVFnpjsjNyacEFsmisD4CY_3D4858387
8 简首页