ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 交换排序

交换排序

原创 Linux操作系统 作者:diy_os 时间:2016-01-20 15:15:42 0 删除 编辑
交换排序是一类借助“交换"进行排序的方法,其主要思想是:在待排序序列中选两个记录,将它们的关键码进行比较,如果反序则交换它们的位置。下面主要介绍交换排序中的冒泡排序和快速排序方法。
冒泡排序(Bubble Sort):
是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。冒泡排序可以说是最简单的排序方法了,详细可以参考百度百科。下面简单的给出代码:
#include<iostream>
using namespace std;
void bubbleSort(int *a, int n);
void bubbleSort(int *a, int n) {
	int i, j, temp;
	for (j = 0; j < n - 1; j++)
		for (i = 0; i < n - 1 - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				temp = a[i];
				a[i] = a[i + 1];
				a[i + 1] = temp;
			}
		}
        }
int main() {
	int arry[] = { 11,5,2,1,10,4,6,8,7 };
	int length = sizeof(arry) / sizeof(int);
	bubbleSort(arry, length);
	for (int i = 0; i <length; i++) {
		cout << arry[i] << " ";
	}
	cout << endl;
}

快速排序(Quicksort):

快速排序是对冒泡排序的一种改进,冒泡排序中记录的比较和移动的比较是在相邻位置进行的,记录每次交换只能后移一个位置,所以总的比较次数较多。但是快速排序中,,记录的比较和移动是从两端向中间进行的,关键码较大的记录一次就能从前面移动到后面,关键码较小的同样也能一次性移动到前面,这样总的比较次数大大减少。

快速排序的过程步骤为:(摘自维基百科:点击打开链接

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

1.从数列中挑出一个元素,称为"基准"(pivot)
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
图示该过程:


给出该算法的代码:

#include<iostream>
using namespace std;
void quickSort(int *arry,int,int length);
void quickSort(int *arry, int low, int high) {

	if (low >= high) {
		return;
	}
	int flag = arry[low];//取数组的第一个元素作为"轴值"
	int last = high;  //这里注意,需要对函数常数参数进行保存,在递归中需要用到。在进行第一次排序后,low和high的值都改变且相等。
	int first = low;
	while (low < high) {

		while (low < high&&arry[high] >=flag) {

			--high;
		}
		arry[low] = arry[high];
 while (low < high&&arry[low] <= flag) {

			++low;
		}
		arry[high] = arry[low];
	}
	        arry[low] = flag;//第一次排序后,把flag赋值给"轴值"
		quickSort(arry, first,low-1);//递归
		quickSort(arry, low + 1, last);
}
int main(){
	int arry[] = {23,13,49,6,31,19,28};
	int length = sizeof(arry) / sizeof(int);
	quickSort(arry,0,length-1);
	for (int i = 0; i < length; i++) {
		cout << arry[i] << " ";
	}
	cout << endl;
} 


快速排序需要找出一个"轴值",第一次排序目的是把小于轴值的放在其左边,大于轴值的放在其右边,然后再对轴值的左右两部分再进行上一步的排序,重复第一步的工作,所以用递归算法来解决该问题。
由于快速排序经常用到,对它的理解十分重要,更多请参考点击打开链接



来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1979604/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 插入排序
下一篇: 二叉排序树
请登录后发表评论 登录
全部评论

注册时间:2014-12-11

  • 博文量
    159
  • 访问量
    982620