基础排序算法
通常情况下复杂算法处理小文件的开销会比基本的算法慢，这里先总结3个最基础的排序算法，即选择排序、插入排序和冒泡排序。
1. 该节中通用的方法
01 |
static void exch(double[] a, int i, int j){ |
07 |
static void compExch(double[] a, int i, int j){ |
1. 选择排序
从数组中找出最小的元素和第一个位置的元素进行交换。然后找出第二个最小的元素和第二个位置的元素交换。直到整个数组排序完毕。
01 |
static void selectionSort(double[] a, int start, int end){ |
02 |
for(int i = start; i < end; i++){ |
04 |
for(int j = i + 1; j <= end; j++){ |
选择排序的缺点是运行时间与文件中已排序的数量几乎没有关系。寻找最小元素的一次遍历并不能提供多少关于下一次遍历文件时最小元素位置的信息。对于已经有一定顺序的文件排序和对一个随机顺序的文件排序所花的时间差不多相等。
2. 插入排序
最基本的插入排序
1 |
static void basicInsertSort(double[] a, int start, int end){ |
2 |
for(int i = start + 1; i <= end; i++){ |
3 |
for(int j = i; j > start; j--){ |
改进后的插入排序
改进后的插入排序是先将数组中最小元素放在第一个位置，使得该元素作为一个监视哨。然后像桥牌整理的样子，将和监视哨相比较大的元素右移一个位置，为要插入的元素腾出空间，找到比监视哨。
01 |
static void upgradeInsertSort(double[] a, int start, int end){ |
02 |
for(int i = end; i > start; i--){ |
03 |
compExch(a, i - 1, i); |
05 |
for(int i = start + 2; i <= end; i++){ |
3. 冒泡排序
不断遍历文件，交换倒序的相邻元素，直到文件排号。通常情况下，冒泡排序会比另外两个方法慢，但是冒泡还是选择排序的一种。
1 |
static void bubbleSort(double[] a, int start, int end){ |
2 |
for(int i = start; i < end; i++){ |
3 |
for(int j = end; j > i; j--){ |
4. 比较
选择、插入、冒泡都是二次方时间的算法，而且都不需要额外的存储空间。
对于非随机文件，插入和冒泡可以很好的发挥作用。
对于小文件排序，插入和选择排序比冒泡要快大约两倍。
对于大型随机文件，这3种方法基本相同没有特别有效的方法。
posted on 2011-05-10 21:49
Daniel 阅读(607)
评论(0) 编辑 收藏 所属分类:
CoreJava