zxspopo
- 浏览: 4607 次
- 性别:
- 来自: 济南
-
最新评论
文章列表
归并排序
每次把待排序列分成两部分，分别对这两部分递归地用归并排序，完成后把这两个子部分合并成一个有序序列。
package algorithms.sort;
import algorithms.AbstractSort;
public class MergeSort extends AbstractSort {
@Override
public void sort(int[] array, int from, int len) {
if (len <= 1) {
return;
}
int[] tmpArray = new ...
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A ...
Shell排序
Shell排序可以理解为插入排序的变种，它充分利用了插入排序的两个特点：
1）当数据规模小的时候非常高效
2）当给定数据已经有序时的时间代价为O(N)
所以，Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，知道最后成一个块，并使用插入排序。
这里每次分成若干小块是通过“增量” 来控制的，开始时增量交大，接近N/2,从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终到减小到1。
一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序 ...
java排序算法(三)： 选择排序
- 博客分类：
- java，排序，算法
选择排序
选择排序相对于冒泡来说，它不是每次发现逆序都交换，而是在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序。
相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。
package algorithms.sort;
import algorithms.AbstractSort;
public class SelectSort extends AbstractSort {
@Override
public void sort(int[] array) {
int len ...
冒泡排序
这可能是最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。（当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。
package algorithms.sort;
import algorithms.AbstractSort;
public class BubbleSort extends AbstractSort {
@Override
public void sort(int[] array) {
...
插入排序
该算法在数据规模小的时候十分高效，该算法每次插入第K+1到前K个有序数组中一个合适位置，K从0开始到N-1,从而完成排序
package algorithms.sort;
import algorithms.AbstractSort;
public class InsertSort extends AbstractSort {
@Override
public void sort(int[] array) {
int tmp = 0;
for (int i = 1; i < array.length; i++) {
tm ...
排序算法总共分为插入排序，冒泡排序，选择排序，shell排序，快速排序，归并排序，堆排序。另外还有桶式排序和基数排序。
各类的各类排序具体细节会在后续的代码详解中详细介绍。
为了方便管理，引入一个父类：
public abstract class AbstractSort{
public abstract void sort(int[] array);
protected final void swap(int[] array,int from ,int to)
{
int tmp=array[from ...