标签:sort

冒泡排序BubbleSort

发表于3年前(Dec 24, 2014 10:08:51 AM)  阅读 3049  评论 0

分类: Java 算法 排序

标签: sort 排序 bubblesort 冒泡排序

冒泡排序也是常用的排序方法之一,他的优点在于可读性好,容易编程实现。他的原理是,对于长度为n的数组,做n-1趟比较,每一趟比较,依次比较前后两数,小的数往前放,大的数往后放,相当于气泡往上升,所以叫冒泡排序。每一趟依次找出数组中最大的数,因此,每趟可以依次少比较一个数,只需比较到n-i+1个数即可。

冒泡排序的时间复杂度为O(n2)。

合并排序MergeSort

发表于3年前(Dec 24, 2014 9:57:55 AM)  阅读 546  评论 0

分类: Java 算法 排序

标签: sort 排序 mergesort 合并排序 递归

合并排序是分治法的典型应用,就是我们常说的递归。合并排序是将两个已经排好序的数组合并成一个有序数组的过程,所以只需保证子数组有序,那么合并出来的数组也是有序的,那剩下的问题就是如何递归地对子数组进行排序。

合并排序是不能在原数组上实现的,他的时间复杂度为O(nlog n)。在上面的代码中,核心算法是merge合并算法。在该算法的实现中,对要合并的目标数组进行了拷贝,然后替换源数组的值,这样的话可读性较好,但实际上也是一件影响效率的工作。参考网上其它的算法,一般是返回一个新的排序数组,各中优略请读者自己把握。

插入排序InsertionSort

发表于3年前(Dec 24, 2014 9:56:10 AM)  阅读 502  评论 0

分类: Java 算法 排序

标签: insertionsort sort 排序 插入排序

插入排序是排序算法中很简单的一种排序,适用于少量元素排序。对他的描述,《算法导论》一书中的例子我觉得很形象。插入排序的算法原理类似于打牌中的摸牌:没摸牌时,我们手中是空的,接着,一次摸一张牌,每次摸起时,我们按照大小把它排列,无论什么时候,我们手中的牌都是已排好序的。

在实现时,我们使用两个数组,数组A用来模拟待摸的牌,数组B用来模拟我们自己手上抓的牌,每次我们从A中取一张牌插到B中,不管什么时候,B中的牌都是排好序的。

插入排序是可以在原数组上实现的,时间复杂度为O(n2)。