日志标签 ‘快速排序’

交换类排序

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所指位置。

分治算法之快速排序

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无限递归下去。完整的代码可在这里下载

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