存档在 ‘算法分析’ 分类

选择类排序

2012年3月17日

选择类排序的基本思想是每一趟在n-(i-1)个待排序的记录中选取一个关键字最小的记录作为有序序列中的第i个记录。常用的选择类排序法有简单选择排序和堆排序。

1.简单选择排序

简单选择排序是对选择类排序基本思想的直接实现。在第一趟排序中,从第一个记录开始在待排序的n个记录中选择一个最小的记录,并和第一个记录作交换;在第二趟排序中,从第二个记录开始从待排序的n-1个记录中选择一个最小的记录,并和第二个记录做交换。依次类推,第i趟排序过程即从第i个元素开始在待排序的n-(i-1)个元素中选择一个最小的记录,并和第i个记录作交换。

void selectSort(int *r, int length)
{
	int i, j, k, n;

	n = length;

	for ( i = 1; i <= n - 1; i++) {
		k = i;

		for ( j = i + 1; j <= n; j++)
			if (r[j] < r[k])
				k = j;
		if ( k != i) {
			r[0] = r[i];
			r[i] = r[k];
			r[k] = r[0];
		}
	output(r, length);
	}
}

在具体实现时,外部循环用来控制总的排序趟数,而内部循环用于在剩余待排序记录中挑选一个最小的记录。在每一趟排序中,使用k记录最小记录的索引。

2.堆排序

堆排序将一维的待排序记录按照完全二叉树的形式进行组织,并利用完全二叉树中父节点和孩子节点之间的关系来选择记录,最终达到排序的目的。堆排序只是利用了完全二叉树的特性,待排序记录仍然采用一维数组进行存储,而非采用树的存储结构。 堆排序的算法思想是将待排序的记录r[1,n]看作是一棵完全二叉树,将记录1作为完全二叉树的根节点,记录中的其他元素依次逐层从左至右顺序排序。首先将该完全二叉树调整为大根堆(最终排列成递减序列),也就是创建堆的过程;接着,将根元素从二叉树中移除并作为有序记录集合中的第一个元素,同时再次调整该二叉树让其形成另一个大根堆。不断重复上述过程直到该完全二叉树为空。实现代码如下:

void heapSort(int *r, int length)
{
	int i, n;
	int t;

	create_heap(r, length);

	n = length;

	for ( i = n; i >= 2; i--) {
		t = r[1];
		r[1] = r[i];
		r[i]= t;
		adjust_heap(r, 1, i - 1);
		output(r, length);
	}
}

在具体的实现堆排序时,通常是将堆顶元素和堆尾元素进行交换,再次调整剩余待排序的元素形成堆。第i趟排序是将堆顶元素r[1]和堆尾元素r[n-i+1]进行交换,此时序列r中后i个元素是有序的。

堆的创建就是自底向上逐层调整该完全二叉树的子树。对于n个元素的记录来说,先将以第n/2个元素为根的子树调整为大根堆,再将以n/2-1个元素为根的子树调整为大根堆,按照逐层自底向上的顺序,直到根节点。

void create_heap(int *r, int length)
{
	int i, n;

	n = length;

	for ( i = n / 2; i >= 1; i--)
		adjust_heap(r, i, n);
}

整个堆排序的核心算法是调整堆,其中r[k,m]是一个以k元素为根的完全二叉树,该算法将此二叉树调整为堆。具体实现时,用r[0]备份当前二叉树的根元素,用j表示i元素的左孩子。算法中使用循环不断将二叉树调整为堆,它首先确定i节点的两个孩子中的较大值,再进一步判断是否需要与根节点进行交换。如果根节点大于i节点较大的那个孩子节点j,整个调整过程结束,因为此时该二叉树就是一个堆。否则将这个较大值的孩子j移到节点i处,接下来以j为根节点继续如上考察它的两个孩子节点的大小。

void adjust_heap(int *r, int k, int m)
{
	int i, j, t;
	int finished;

	r[0] = r[k];
	i = k;
	j = 2 * i;

	finished = 0;

	while (j <= m && !finished) {
		if (j < m && r[j] < r[j + 1])
			j++;
		if (r[0] >= r[j])
			finished = 1;
		else {
			r[i] = r[j];
			i = j;
			j = 2 * i;
		}
	}

	r[i] = r[0];
}

整个调整堆的过程是由根节点逐步向下筛选的过程。

交换类排序

2012年3月16日

交换类排序的基本思想是通过交换逆序元素而最终达到所有元素有序,这里的逆序是个广义概念,如果按照降序排序,那么前小后大的相邻元素就为逆序。常见的交换类排序方法有冒泡排序和快速排序。

1.冒泡排序

冒泡排序法的思想比较简单,依次扫描待排序的序列,并且从第一个元素开始比较相邻两个元素之间的大小,如果逆序则交换。假如有一个记录序列r[1,length],以升序为例,在第i趟排序过程中需要对前length-(i-1)个元素进行逆序交换,最终这些记录中的最大元素将被交换到序列中第length-(i-1)这个位置上。

void bubbleSort(int *r, int length)
{
	int n, change;
	int i, j, k;

	n = length;
	change = 1;

	for ( i = 1; i <= n - 1 && change; i++) {
		change = 0;
		for ( j = 1; j <= n - i; j++)
			if (r[j] > r[j + 1]) {
				r[0] = r[j];
				r[j] = r[j + 1];
				r[j + 1] = r[0];
				change = 1;
			}
		output(r, length);
	}
}

对于n个元素的序列来说,整个冒泡排序最多进行n-1趟。这里还特别的增加了一个标志位change,只要做了逆序交换change就为真,如果某一趟中没有做任何交换,说明序列已经有序,则change为假,此时整个排序可以提前停止。

2.快速排序

冒泡算法中对相邻元素的交换一次只能消除一个逆序,如果通过交换两个不相邻的元素能一次消除多个逆序,则会增加整个排序的速度。快速排序就是基于这样的目的,在一次交换中可以消除多个逆序。

快速排序的基本思想是在待排序记录中选择一个记录作为标准,将大于该标准的所有元素移到该标准之后,将小于该标准的所有元素移到该标准之前。最终将待排序的记录分成两个子序列,而标准元素插入到两个子序列之间,上述过程为一趟快速排序过程。接下来再对两个子序列进行快速排序,不断的分割子表,直到子表长度不超过1为止,此时所有的记录都是有序的。

根据上述分析,可以通过递归来实现快速排序法。quickPass()用于一趟快速排序,并且返回标准元素的位置pos。

void quickSort(int *r, int low, int high, int length)
{
	int pos;


	if (low < high) {
		pos = quickPass(r, low, high);
		quickSort(r, low, pos - 1, length);
		quickSort(r, pos + 1, high, length);
		output(r, length);
	}
}

quickPass()用于实现一趟快速排序,一趟快速排序结束的条件是low不小于high。可以看到快速排序中是将low和high两个不相邻位置的元素进行交换。

int quickPass(int *r, int left, int right) 
{
	int low, high;

	low = left;
	high = right;
	r[0] = r[low];

	while (low < high) {
		while (low < high && r[high] >= r[0])
			high--;
		if (low < high) {
			r[low] = r[high];
			low++;
		}

		while (low < high && r[low] <= r[0])
			low++;
		if (low < high) {
			r[high] = r[low];
			high--;
		}
	}

	r[low] = r[0];
	return low;
}

这里也用到了r[0],用它来存储标准元素,当一趟快速排序完成后,将标准元素插入low所指位置。

插入类排序

2012年3月15日

插入类排序的基本思路是在一个已经排好序的子记录上,每一步将下一个待排序的记录插入到已经排好序的记录子集中,直到将所有待排序记录全部插入为止。

1.直接插入排序

直接插入排序是最基本的插入排序算法,它的一趟操作是将第i个记录插入到前面i-1个已经排好序的记录中,在查找记录i的插入位置时,也在进行元素的移动。假设有一个待排序队列r[1,length],则整个排序过程需要n-1次趟。直接插入算法的实现如下:

void insSort(int *r, int length)
{
	int i, j;

	printf("Sorting:\n");
	for ( i = 2; i <= length; i++) {
		r[0] = r[i];
		j = i - 1;

		while (r[0] < r[j]) {
			r[j + 1] = r[j];
			j--;
		}

		r[j + 1] = r[0];

		output(r, length);
	}
}

具体实现时,用一维数组来存储待排序的序列,其中0号元素备份待插入的记录。

2.折半插入排序

折半插入排序法与直接插入法类似,区别在于确定元素i插入的位置时利用折半查找法。每一趟排序的过程是先用折半查找法确定插入位置,再逐个进行元素的移动。

void binSort(int *r, int length)
{
	int i, j;
	int low ,high, mid;

	printf("Sorting:\n");
	for ( i = 2; i <= length; i++) {
		r[0] = r[i];
		low = 1;
		high = i - 1;

		while (low <= high) {
			mid = (low + high) / 2;
			if (r[0] < r[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}

		for (j = i - 1; j >= low; j--) 
			r[j + 1] = r[j];
		r[high + 1] = r[0];
		output(r, length);

	}
}

与直接插入法类似,数组r中的0号元素也备份了待插入的元素i。当确定了记录i的位置时,此时存在low=high+1这样的关系,接下来将low到i-1之间的元素都后移一位,最终记录i刚好插入空出来的位置中。

3.希尔排序

整个希尔排序的过程由若干次希尔插入组成,具体次数由增量数组delta中的元素个数n确定。在每一次的希尔插入算法中,将待排序的记录序列分成d个稀疏子序列,每个稀疏子序列中元素之间的间隔正好为d。希尔插入算法就是将每一个子序列都按照直接插入法排列成有序,从而使得整个序列基本有序。上述过程会重复n次,就是希尔排序算法的整个过程。

void shellSort(int *r, int length, int *delta, int n)
{
	int i;
	for ( i = 0; i < n; i++) {
		shellInsert(r, length, delta[i]);
	}
}

第i趟希尔排序中,每个稀疏子序列中元素的间隔由delta[i]决定。但希尔算法的最后一趟排序,元素的间隔必需是1。因为最后一次希尔排序就相当于直接插入排序,但是此时整个记录序列已经几乎有序,因此移动的次数会大大减少。

void shellInsert(int *r, int length, int d)
{
	int i, j;
	int k;
	
	for (i = 1 + d; i <= length; i++) {
		if (r[i] < r[i - d]) {
			r[0] = r[i];
			
			for (j = i - d; j > 0 && r[0] < r[j]; j -= d) {
				r[j + d] = r[j];
			}
			r[j + d] = r[0];
		}
	}
	output(r, length);
}

虽然希尔插入算法中需要依次将d个子序列排成有序,但是实际的实现过程却从第一个子序列的第二个记录(d+1)开始依次遍历整个序列,因为每个序列中的元素都是由间隔d控制的,因此就相当于每个子序列各自排序。内部的for循环相当于对每个子序列进行直接插入排序,从当前的记录i(保存在r[0]中)开始,依次扫描当前子序列之前的元素(每个元素的间隔为d,因此每次循环j都减少d)以确保插入何时的位置。

本文所涉及的排序算法源码可以在这里下载。

分治算法之快速排序

2011年5月4日

快速排序算法也是基于分治思想的一种排序算法,它的基本操作即为比较-交换。

快速排序算法的基本思想是从待排序的序列中选取一个比较标准K(通常选取第一个元素),然后将其余元素依次跟K进行比较。在比较的过程中将大于K的元素移到K的后面,将小于K的元素移到K的前面,最后的结果是将原始序列分为两个子序列,而K元素则恰好位于两个子列中间。上述过程称为一趟快速排序,接下来依次为两个子序列进行快速排序,依次递归。当子序列的长度小于1时,递归停止。此时,原始序列已经成为一个有序的序列了。

根据上面的思想,快速排序算法的代码实现如下所示。quickSort函数对原始序列递归进行快速排序,每次排序时先通过partiton函数得到序列中p到r元素间的分界点q,然后再分别对两个子序列p到q-1和q+1到r进行快速排序。

void quickSort(int *a, int p, int r)
{
	if (p < r) {
		int q = partition(a, p, r);
		quickSort(a, p, q - 1);
		quickSort(a, q + 1, r);
	}
}

partition函数是快速排序算法的关键。该函数选取待排序序列的第一个元素作为基准,通过反复的比较-交换将p到r之间的元素分成两组子序列,一组子序列的元素全部小于x,另一组子序列的元素全部大于x。

在具体的比较-交换过程中,设置两个记录点low和high,并在初始时将基准保存到x中。然后不断进行下面两种扫描:

1.将high从右至左扫描,直到a[high] < x为止,由于此时的a[high]是第一个小于基准x的元素,因此将a[high]和x交换。

2.将low从左至右扫描,直到a[low] >= x为止,由于此时的a[low]是第一个不小于基准x的元素,因此将a[low]和x交换。

当low小于high时会一直持续上述两种扫描,否则称其完成了一次划分过程。每一次的划分过程就会得到分界位置,返回为quickSort函数。

int partition(int *a, int p, int r)
{
	int x, low, high;

	x = a[p];
	low = p;
	high = r;

	while (low < high) {
		while (low < high && a[high] >= x)
			high--;
		if (low < high) {
			a[low] = a[high];
			a[high] = x;
			low++;
		}
		output_data(a, n);

		while (low < high && a[low] < x)
			low++;
		if (low < high) {
			a[high] = a[low];
			a[low] = x;
			high--;
		}
		output_data(a, n);
	}
	a[low] = x;
	return low;
}

在partition函数中,选择第一个元素p作为基准可以保证该函数正常退出。如果选取最后一个元素r作为基准,而该元素又恰好是最大元素,那么partition函数就会返回r,这使得quickSort无限递归下去。完整的代码可在这里下载

分治算法之合并排序

2011年4月13日

分治算法的基本思想是将一个规模为n的问题分解成k个规模较小的子问题,这些子问题相互独立并且与原问题相同。先递归的解决这些子问题,然后再将各个子问题的解合并到原问题的解当中。

合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的两个子集合合并成一个排好序的集合。合并排序算法可递归的伪代码表达如下:

void mergeSort(int *a, int left, int right)
{
	int i;
	if (left < right) {
		i = (left + right) / 2;
		mergeSort(a, left, i);
		mergeSort(a, i + 1, right);
		merge(a, b, left, i, right);
		copy(a, b, left, right);
	}
}

在mergeSort函数内,不断的进行递归调用以缩小问题规模;merge函数用于将两个排好序的子序列合并成一个大的有序序列,并存储在数组b中;最后利用copy函数将b数组的序列再重新拷贝到数组a中,完成合并排序。

上述的mergeSort函数中,递归调用是整个算法的关键步骤。mergeSort函数不断的平分待排序的数列集合,如果当前数列集合两端的序号分别为left和right,那么平分后的两个数列集合序号分别是left到i和i+1到right。这种不断平分并递归的结果是使得当前的待排序集合中只剩下一个元素,接着再进行两两子序列集合的合并。

正如上面所说的,这些待合并的子序列都已排好序。并且最初一批待合并的子序列集合中只有一个元素,合并后元素数量为2,再次合并为4,依次类推。

根据上述的描述,我们可以将递归形式的合并排序算法改进成非递归的形式。在上述递归形式中,我们是从整个序列出发,逐渐平分再递归。而非递归形式的排序算法则先让整个序列中相邻的元素两两进行排序,形成n/2个长度为2的已排好序的子序列。接着再将它们排成长度为4的子序列,以此类推。该算法结束结束时是将两个已经排好序的子序列排成一个有序序列。

根据上面的思路,非递归形式的合并算法可参考如下代码。mergeSort函数依次对整个待排序的序列中长度为1、2、4、8的子序列进行排序。s即为当前正进行排序的子序列集合的元素个数。

void mergeSort(int a[], int n)
{
	int *b = NULL;
	int s = 1;
	int count = 1;

	b = (int *)malloc(sizeof(int) * n);
	while (s < n) {
		printf("sort %d:\n", count++);
		mergePass(a, b, s, n);
		s += s;
		printf("sort %d:\n", count++);
		mergePass(b, a, s, n);
		s += s;
	}
	free(b);
}

mergePass函数的作用是大小为s的相邻子序列。通过while循环将整个序列分成n/s个大小为s的子序列,由于这写子序列内部已经排好序,则调用merge函数直接进行合并即可。

void mergePass(int x[], int y[], int s, int n)
{
	int i = 0;
	int j;

	while (i < n - 2 * s) {
		merge(x, y, i, i + s - 1, i + 2 * s -1);
		i = i + 2 * s;
	}

	if (i + s < n)
		merge(x, y, i, i + s - 1, n - 1);
	else
		for (j = i; j <= n - 1; j++)
			y[j] = x[j];

	for (i = 0; i < n; i++)
		printf("%d ", y[i]);
	printf("\n");
}

merge函数的作用是合并两个相邻的子序列,这两个子序列的序号分别为l到m和m+1到r。

void merge(int c[], int d[], int l, int m, int r) 
{
	int i, j, k;
	
	i = l;
	j = m + 1;
	k = l;
	while ((i <= m) && (j <= r))
		if (c[i] <= c[j])
			d[k++] = c[i++];
		else 
			d[k++] = c[j++];
	
	int q;
	if (i > m)
		for (q = j; q <= r; q++)
			d[k++] = c[q];
	else
		for (q = i; q <= m; q++)
			d[k++] = c[q];
}

以上就是合并算法的核心函数,完整代码可以从这里下载

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key