前面学习了内排序里面的插入排序,插入排序包含直接插入排序,二分插入排序和希尔排序,其中希尔排序的速度通常比较快。这篇博客,主要介绍排序算法中的交换排序。主要介绍冒泡排序和快速排序。
交换排序的基本思想是两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
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))。另外,快速排序是不稳定排序。
相关推荐
冒泡排序算法是一种简单的排序算法,它的工作原理是通过不断地比较相邻元素,并交换它们以达到排序的目的。冒泡排序算法的时间复杂度为O(n^2),因此它适合小规模的数据排序。 2.选择排序算法 选择排序算法也是一种...
1. **冒泡排序**:冒泡排序是一种简单直观的排序算法,通过不断交换相邻的错误顺序元素来逐步完成排序。它重复地走访过要排序的元素,依次比较每一对相邻元素,如果它们的顺序错误就把它们交换过来。走访元素的工作...
冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的...
【排序算法概述】 排序算法是计算机科学中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定标准(如升序或降序)排列。排序算法的效率对程序的性能有着显著影响,尤其是在处理大量数据时。虽然...
在本文中,我们将深入探讨基于FPGA的并行快速排序算法,特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据,并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题: 一、快速排序算法...
**插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法对大数据量的处理效率较低,但对于小规模数据或者部分有序的...
在计算机科学领域,排序算法是数据处理的核心技术之一,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)排列。本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序...
详解Java常用排序算法-选择排序 选择排序(Selection Sort)是一种简单的排序算法,它的基本思想是每次从待排序的元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的元素排完。 选择...
冒泡排序是一种基础且经典的排序算法,它的基本思想是通过不断地交换相邻的逆序元素,使得每一轮排序后,最大的元素“浮”到数组的末尾。这个过程就像水底下的气泡逐渐升至水面一样,因此得名“冒泡排序”。 在Java...
在编程领域,排序算法是计算机科学中的基础概念,它用于对一组数据进行排列,以便于检索、分析或处理。在本主题中,我们将探讨如何使用C++类来实现不同的排序算法,并理解类在实现这些算法时的角色。我们将重点关注...
插入排序是一种基础且直观的排序算法,它的工作原理可以类比于整理扑克牌。在实际应用中,插入排序对于小规模数据或者部分有序的数据表现优秀,但对于大规模无序数据,其效率相对较低。以下是关于插入排序的详细知识...
《排序算法-StdDraw动态展示源码》 在计算机科学中,排序算法是处理数据的一种基本技巧,它用于将一组无序的数据按照特定顺序排列。本项目提供的源码旨在通过StdDraw工具动态地展示各种排序算法的过程,帮助学习者...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
1. **冒泡排序**:冒泡排序是一种简单直观的排序算法,通过重复遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序...
快速排序算法详解 快速排序(Quick Sort)是一种分治思想的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续...
SelectionSort是一种简单的排序算法,它的基本思想是重复地找到待排序序列中的最小(或最大)元素,然后将其与序列的第一个元素交换。这个过程会持续进行,直到整个序列有序。SelectionSort的主要步骤包括: 1. **...
**选择排序**是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法,因为它可能会...
在编程领域,排序算法是计算机科学中的一个基本概念,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)排列。本篇将详细讲解C#中实现的选择排序算法。 选择排序是一种简单直观的排序算法,...
冒泡排序是一种简单的交换排序方法,它的基本思想是通过重复遍历待排序的元素列表,比较相邻元素并根据需要交换它们的位置,从而逐渐将较大或较小的元素“浮”到列表的两端。这一过程就像水中的气泡一样,大元素逐渐...
然而,由于其非稳定性和较高的交换次数,HeapSort在实际应用中可能不如其他排序算法如快速排序或归并排序。 在提供的压缩文件中,包含了用C语言实现HeapSort的源代码。通过对这段代码的学习,读者可以深入了解...