排序算法--交换排序

          前面学习了内排序里面的插入排序，插入排序包含直接插入排序，二分插入排序和希尔排序，其中希尔排序的速度通常比较快。这篇博客，主要介绍排序算法中的交换排序。主要介绍冒泡排序和快速排序。

        交换排序的基本思想是两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

 

1.冒泡排序

  

基本思想        通过无序区中相邻记录的关键字间的比较和位置交换，使关键字最小的记录如气泡一样逐渐往上"漂浮"直至“水面”

 

具体操作

          整个算法从最下面开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得一趟冒泡排序后，关键字最小的记录到达最上端。接着，再在剩下的记录中找关键字次小的记录，并把它换到第二个位置上。以此类推，一直到所有记录都有序为止。

 

示意图

 实现代码

 

//冒泡排序
void BubbleSort(int a[],int len)
{
	int i,j,temp;
	bool change;//判断是否已经排好序

	for(i=0;i<len-1;i++)
	{
		change=false;
		for(j=len-1;j>i;j--)
		{
			if(a[j]<a[j-1])//两两比较
			{
				temp=a[j];
				a[j]=a[j-1];
				a[j-1]=temp;
				change=true;//有交换为true
			}
		
		}
		//没进行交换，说明已经排好序，结束算法
		if(!change)
		 break;
	}

	//输出结果
	for(int i=0;i<10;i++)
		cout<<a[i]<<"  ";
}

 

 

效率分析

        可以看出，若表的初始状态是正序的，则一趟扫描即可完成，所需的关键字比较和记录移动都是最小值。即冒泡排序的最好时间复杂度为O(n)；若初始表是反序，则需要进行n-1趟排序，这种情况最糟，此时时间复杂度为O(n^2)。

         冒泡排序的平均时间复杂度为O(n^2),由于冒泡排序的记录移动较多，所以平均时间性能比直接排序要差。冒泡排序只使用了几个辅助变量，与问题规模n无关，故辅助空间复杂度为O(1)，是就地排序。冒泡排序当关键字相等时，没有交换它们的位置，所以是稳定排序。

 

2.快速排序

       快速排序采用的思想是分治思想。是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。

 

基本思想

     1）选择一个基准元素,通常选择第一个元素(可以以任意元素为基准)。

 

     2）通过一趟排序将待排序的记录分割成独立的两部分，其中前面一部分记录的元素值均比基准元素值小。后面一部分记录的元素值比基准值大。

 

     3）此时基准元素在其排好序后的正确位置

 

     4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

 

 

实现代码

 

主要是从右往左找第一个小于基准的元素，把它放到前面部分的前面。从左往右找第一个大于基准的元素，把它放到后面部分的后面。

 

void QuickSort(int a[],int start,int end)//a[start]至a[end]进行快速排序
{
	int temp;
	
	int i=start,j=end;
	if(j>i)//至少存在2个元素
	{
		temp=a[i];//等于当前快排区间的第一个元素

		while(i!=j)
		{
			//从后向前找到第一个小于temp的元素
			while(j>i&&a[j]>temp)
				j--;
			a[i]=a[j];

			//从前往后找到第一个大于temp的元素
			while(i<j&&a[i]<temp)
				i++;
			a[j]=a[i];

		}
		a[i]=temp;

		QuickSort(a,start,i-1);//对左区间递归排序

		QuickSort(a,i+1,end);//对右区间递归排序
	}
}

 

效率分析

        快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键字有序或基本有序时， 则每次选取的基准都是当前关键字中的最大值或最小值，则快速排序所需要的比较次数反而增多了。脱变成冒泡排序了。在最好情况下，每次选择的基准都是当前无序区的"中值"记录。使划分的结果是基准左右两个无序子区间长度大致相等。

        快速排序最坏情况的时间复杂度为O(n^2),最好时间复杂度为O(nlog2(n))。快速排序的空间复杂度为O(log2(n))。另外，快速排序是不稳定排序。

评论

1 楼 fggsgigomkg 2015-04-05  

关注楼主的排序算法，很不错