首页 > 代码库 > 交换排序算法
交换排序算法
交换排序的基本思想是:两两比较待排序记录的关键字,一旦发现两个记录不满足次序要求时则进行交换,直到整个序列全部满足要求为止。
交换排序算法分为冒泡排序和快速排序
冒泡排序(Bubble Sort)是一种最简单的交换排序方法,它通过两两比较相邻记录的关键字,如果发生逆序,则进行交换,从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移)
或者使关键字大的记录如石块一样逐渐向下“坠落”(右移)。
代码
void bubbleSort(int[] list){ for(int i=list.length-1;i>=0;i--){ for(int j=0;j<i;j++){ if(list[j]>list[j+1]){ int flag=list[j]; list[j]=list[j+1]; list[j+1]=flag; } } }
算法时间复杂度O(n^2), 空间复杂度O(1)
算法特点:
(1)稳定排序
(2)可用于链式存储结构
(3)移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时,此算法不宜采用。
快速排序
快速排序(Quick Sort)是由冒泡排序改进而得的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。
代码:
void quickSort(int left,int right){ int i,j,t,temp; }
交换排序算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。