`
hm4123660
  • 浏览: 282417 次
  • 性别: Icon_minigender_1
  • 来自: 广州
博客专栏
Dea4ce76-f328-3ab2-b24a-fb268e1eeb75
数据结构
浏览量:69994
社区版块
存档分类
最新评论

排序算法--交换排序

阅读更多

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

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

 

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))。另外,快速排序是不稳定排序。

  • 大小: 50.7 KB
  • 大小: 117.6 KB
  • 大小: 40.5 KB
3
1
分享到:
评论
1 楼 fggsgigomkg 2015-04-05  
关注楼主的排序算法,很不错

相关推荐

    最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构

    冒泡排序算法是一种简单的排序算法,它的工作原理是通过不断地比较相邻元素,并交换它们以达到排序的目的。冒泡排序算法的时间复杂度为O(n^2),因此它适合小规模的数据排序。 2.选择排序算法 选择排序算法也是一种...

    java排序算法-大全.rar

    1. **冒泡排序**:冒泡排序是一种简单直观的排序算法,通过不断交换相邻的错误顺序元素来逐步完成排序。它重复地走访过要排序的元素,依次比较每一对相邻元素,如果它们的顺序错误就把它们交换过来。走访元素的工作...

    C语言排序算法---冒泡排序法

    冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的...

    排序算法 - Axb的自我修养1

    【排序算法概述】 排序算法是计算机科学中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定标准(如升序或降序)排列。排序算法的效率对程序的性能有着显著影响,尤其是在处理大量数据时。虽然...

    FPGA并行快速排序算法-位宽可设

    在本文中,我们将深入探讨基于FPGA的并行快速排序算法,特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据,并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题: 一、快速排序算法...

    排序算法 -- 插入排序

    **插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法对大数据量的处理效率较低,但对于小规模数据或者部分有序的...

    排序算法--免费

    在计算机科学领域,排序算法是数据处理的核心技术之一,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)排列。本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序...

    详解Java常用排序算法-选择排序

    详解Java常用排序算法-选择排序 选择排序(Selection Sort)是一种简单的排序算法,它的基本思想是每次从待排序的元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的元素排完。 选择...

    排序算法 -- 冒泡排序

    冒泡排序是一种基础且经典的排序算法,它的基本思想是通过不断地交换相邻的逆序元素,使得每一轮排序后,最大的元素“浮”到数组的末尾。这个过程就像水底下的气泡逐渐升至水面一样,因此得名“冒泡排序”。 在Java...

    简单排序算法--类的简单使用

    在编程领域,排序算法是计算机科学中的基础概念,它用于对一组数据进行排列,以便于检索、分析或处理。在本主题中,我们将探讨如何使用C++类来实现不同的排序算法,并理解类在实现这些算法时的角色。我们将重点关注...

    排序算法-插入排序

    插入排序是一种基础且直观的排序算法,它的工作原理可以类比于整理扑克牌。在实际应用中,插入排序对于小规模数据或者部分有序的数据表现优秀,但对于大规模无序数据,其效率相对较低。以下是关于插入排序的详细知识...

    排序算法-StdDraw动态展示源码

    《排序算法-StdDraw动态展示源码》 在计算机科学中,排序算法是处理数据的一种基本技巧,它用于将一组无序的数据按照特定顺序排列。本项目提供的源码旨在通过StdDraw工具动态地展示各种排序算法的过程,帮助学习者...

    七大排序算法--c语言是实现

    七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...

    JavaScript-使用javascript开发的排序算法-sorting.zip

    1. **冒泡排序**:冒泡排序是一种简单直观的排序算法,通过重复遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序...

    详解Java常用排序算法-快速排序

    快速排序算法详解 快速排序(Quick Sort)是一种分治思想的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续...

    排序算法-基于C语言实现的排序算法之SelectionSort实现.zip

    SelectionSort是一种简单的排序算法,它的基本思想是重复地找到待排序序列中的最小(或最大)元素,然后将其与序列的第一个元素交换。这个过程会持续进行,直到整个序列有序。SelectionSort的主要步骤包括: 1. **...

    排序算法 -- 选择排序

    **选择排序**是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法,因为它可能会...

    C#-基于C#实现的选择排序算法-Selection-Sort.zip

    在编程领域,排序算法是计算机科学中的一个基本概念,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)排列。本篇将详细讲解C#中实现的选择排序算法。 选择排序是一种简单直观的排序算法,...

    排序算法-基于Java实现的排序算法之BubbleSort实现.zip

    冒泡排序是一种简单的交换排序方法,它的基本思想是通过重复遍历待排序的元素列表,比较相邻元素并根据需要交换它们的位置,从而逐渐将较大或较小的元素“浮”到列表的两端。这一过程就像水中的气泡一样,大元素逐渐...

    排序算法-基于C语言实现的排序算法之HeapSort实现.zip

    然而,由于其非稳定性和较高的交换次数,HeapSort在实际应用中可能不如其他排序算法如快速排序或归并排序。 在提供的压缩文件中,包含了用C语言实现HeapSort的源代码。通过对这段代码的学习,读者可以深入了解...

Global site tag (gtag.js) - Google Analytics