yuzh的博客

❤ ECUST ❤

0%

发表于 更新于 Valine：

不出现歧义的情况下编出来的码长度最短

让出现次数多的字符编码最短

每次合并最小的两个，即生成一个父节点，使得父节点的值为两个子节点的值之和

hoffman

发表于 Valine：

下方所有除使用STL库外的所有排序算法调用方法都是qsort(a,0,n-1);

初级排序算法

冒泡排序

1
2
3
4
5
6
7
8
9
10
void bubblesort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		for(int j=i+1;j<=right;j++)
		{
			if(arr[i]>arr[j]) swap(arr[i],arr[j]);
		}
	}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
void selectionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int min=i; 
		for(int j=i+1;j<=right;j++)
		{
			if(arr[j]<arr[min]) min=j;
		}
		swap(arr[i],arr[min]);
	}
}

插入排序

同整理扑克牌，依次将每个元素插入到前面有序的部分。

1
2
3
4
5
6
7
8
9
10
11
void insertionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int cnt=arr[i];
		for(int j=i-1;j>=left && cnt<=arr[j];j--)
		{
			swap(arr[j],arr[j+1]);
		}
	}
}

优化：可以利用折半查找的方法找到插入的位置，即折半插入排序

希尔排序

通过给定间隔h，使得原来的数组被切分为更小的数组，进而提升插入排序效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shellsort(int* arr, int left, int right)
{
	int h=1;
	while(h<(right-left+1)/3) h=h*3+1;
	while(h>=1)
	{
		for(int i=left;i<(right-left+1)/h;i++)
		{
			int cnt=arr[i];
			for(int j=i-h;j>=left && cnt<=arr[j];j-=h)
			{
				swap(arr[j],arr[j+h]);
			}
		}
		h/=3; 
	}
}

进阶排序算法

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(int* arr, int left, int mid, int right)
{
	int aux[10000], i=left, j=mid+1;
	for(int k=left;k<=right;k++) aux[k]=arr[k];
	for(int k=left;k<=right;k++)
	{
		if(i>mid) arr[k]=aux[j++];
		else if(j>right) arr[k]=aux[i++];
		else if(aux[j]<aux[i]) arr[k]=aux[j++];
		else arr[k]=aux[i++];
	}
}

void mergesort(int* arr, int left, int right)
{
	if(left<right)
	{
		int mid=(right+left)/2;
		mergesort(arr,left,mid);
		mergesort(arr,mid+1,right);
		merge(arr,left,mid,right);
	}
}

快速排序

  • partition函数：以当前给定集合的第一个元素pivot作为基准，比其小的放在左边，比其大的放在右边
  • 随后对pivot左右的数组分别进行排序，直至left=right结束分治

手写快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int partition(int* arr, int left, int right)
{
	int pivot=arr[left];
	while(left<right)
	{
		while(left<right && arr[right]>=pivot)
			right--;
		arr[left]=arr[right];
		
		while(left<right && arr[left]<=pivot)
			left++;
		arr[right]=arr[left];
	}
	arr[left]=pivot; //arr[right]=pivot;
	return left;
}

void qsort(int* arr, int left, int right)
{
	if(left<right)
	{
		int pivot=partition(arr,left,right);
		qsort(arr,left,pivot-1);
		qsort(arr,pivot+1,right);
	}
}

STL sort

排序规则

1
2
3
4
5
//调用：sort(a,a+n,cmp);
bool cmp(int a, int b)
{
	return a<b;
}

发表于 Valine：

安装方法

把keygen和另外两个文件放到ExtFS的安装目录下

打开keygen，先点击Patch RSA 2048，选择安装目录下的Paragon ExtFS for Windows.exe

再次点击 Patch RSA 2048，选择安装目录下的extservice.exe

点击Generate让生成注册码，keygen会自动破解并重启ExtFS的服务。

下载链接

点此进入官网下载主程序

点此下载Patch

发表于 更新于 Valine：

Queue

基本操作

  1. 入队(push):在队列末尾加入一个元素，例如:q.push(x)

  2. 出队(pop):删除/弹出队列第一个元素，即队首元素，例如:q.pop()

  3. 访问队首元素(front):返回队列第一个元素，例如:q.front()

  4. 访问队尾元素(back):返回队列最后一个元素，即队尾元素，例如:q.back()

  5. 判断队列空(empty):判断队列是否为空，如果空，则返回true，否则返回false，例如:q.empty()

  6. 访问队列中元素的个数(size):返回队列元素个数，例如:q.size()