日志标签 ‘堆排序’

选择类排序

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];
}

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

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