发表更新算法导论3 分钟读完 (大约412个字)

桶排序问题与解决

问题描述

看到书上的案例图，觉得是用链表+数组实现，于是一开始参考数据结构老师ppt。但发现实现不了（详见桶排序问题）。
后来想结构直接用二维数组算了。
本来对B[i]数据排序，想用QuickSort，但发现如果是数组B[i][1]至B[i][k]排序，原算法改动较大，遂作罢。

阅读更多
发表更新算法导论2 分钟读完 (大约301个字)

桶排序问题

问题描述

在用Bucket sort的时候，试了一下用链表数组的结构。
编译通过了，但是不知道为什么next指针用不了。

代码

1
2
3
4
5
6
7
8
typedef double ElemType;
typedef ElemType* Array;
typedef struct CTNode{
	ElemType data;
	struct CTNode *next;
}*ChildPtr;
typedef ChildPtr CTBox;
typedef CTBox* CTree;
阅读更多
发表更新算法导论4 分钟读完 (大约626个字)

基数排序问题与解决

问题描述

因为引理中提到，

对于n位数，单位数的最大值为k，若稳定排序需要Θ(k+n)时间，则Radix sort需要Θ(d(k+n))时间。

因此一开始想用Counting sort来进行一位的排序。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Array stableSort(Array A, int n, int d){
	int k = 10;//因为排序的是位，最大值直接定为9 
	Array B = (ElemType*)malloc(k * sizeof(ElemType));
	Array C = (ElemType*)malloc(n * sizeof(ElemType));
	Array D = getSubArray(A, n, d); //第d位的数 
	for(int i = 0; i < k; i++){
		B[i] = 0;
	}
	for(i = 0; i < n; i++){
		B[D[i]]++;
	}
	for(i = 1; i < k; i++){
		B[i] += B[i - 1];
	}
	for(i = 0; i < n; i++){
		B[D[i]]--;
		C[B[D[i]]] = A[i];
	}
	return A;
}
阅读更多
发表更新算法导论16 分钟读完 (大约2361个字)

算法导论笔记

第1章

算法介绍

第2章

  • 用扑克牌举例，介绍了一种插入排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void InsertSort(ElemType *A){
    	printf("length:%d\n", length);
    	for(int j = 1; j < MAXSIZE; j++){
    		int i = j - 1;
    		int tmp = A[j];
    		while(tmp < A[i] && i >= 0){
    			A[i + 1] = A[i];
    			i--;
    		}
    		A[i + 1] = tmp;
    	}
    }
  • 简单介绍了时间复杂度的计算
阅读更多
关注我

分类

标签

C#1
C++6
DataBase7
Django1
Java8
JavaScript1
Lombok1
MyBatis1
MySQL2
Python1
Spring4
c++2
git2
maven1
nexo1
计网1

最新文章

归档

×