前面学习了内排序里面的插入排序,插入排序包含直接插入排序,二分插入排序和希尔排序,其中希尔排序的速度通常比较快。这篇博客,主要介绍排序算法中的交换排序。主要介绍冒泡排序和快速排序。
交换排序的基本思想是两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
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))。另外,快速排序是不稳定排序。
相关推荐
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
从排序的基本概念讲起,详细讲解了插入排序、交换排序、选择排序、归并排序等排序算法的原理以及实现代码
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
经典的数据结构 交换排序算法 非常实用 可以给初学者使用 也可以作为工具提供给编程人员
经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
冒泡排序-排序过程 设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,...
这是对直接插入方法,简单选择排序,简单交换(冒泡)算法的介绍和实现.
感觉比冒泡排序好的排序算法,借助此算法来对比冒泡排序算法,可以加深对这两种经典而双简单的排序算法的理解。
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
C语言排序算法
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 ...
排序是程序设汁中常见的任务,在数据结构课程中介绍了很多种排序方法,有插入排序、交换排序、选择排序、归并排序、基数排序等。每种排序的效率、稳定性和算法的复杂程度都有所区别。在实际应用中,插入排序和现则...
java实现的常用的几种基本排序算法,插入、交换、选择、归并
1.直接插入排序--增量法 2.希尔排序 3.交换排序 4.快速排序 5.直接选择排序 6.堆排序 7.归并排序
程序员可以参考的8大排序算法。1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)
C#排序算法总结:交换排序:最基础的冒泡排序,冒泡排序的优化版选择排序和快速排序,插入排序:直接插入排序和折半插入排序。
内部排序算法主要分为5 大类,有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、...
利用C++实现了常用的排序算法,包括:冒泡排序、插入排序、选择排序、归并排序、快速排序、0-交换排序。利用简单的数字序列排序为例,希望能帮助对以上算法有更深理解。