今天学习两个简单的数组排序算法，选择排序和插入排序。
题目介绍
给定一个数组，将数组按从小到大顺序排序。题目理解起来也是很容易的，就不再画图介绍了。
选择排序
选择排序算法如下：首先找到数组中最小的那个元素，其次将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此反复，直到将整个数组排序。
这种算法叫选择排序就是因为它在不断地选择剩余元素中最小者。
插入排序
插入排序我们使用通常整理纸牌的方法来描述，我们在整理纸牌的时候一般是一张张的来，将每一张插入到其他已经有序的纸牌中的合适位置。在计算机的程序中，为了给要插入的元素腾出空间，我们需要将其余的所有元素都向右移动一位。
实现代码
因为后续多种排序算法都是基于比较+交换的方式来完成排序的，因此先定义一个抽象的排序类。其他排序算法只需要完成类中的sort方法即可。
/**
* 比较交换排序算法抽象类
*/
public abstract class AbstractSort {
/**
* 对给定数组按从小到大排序
*
* @param a
*/
public abstract void sort(Comparable[] a);
/**
* 判斷數字是否已經有序
*
* @param a
* @return
*/
public boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) return false;
}
return true;
}
/**
* 比较两个元素，第一个参数是否小于第二个参数
*
* @param v
* @param w
* @return
*/
protected boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/**
* 交换数组中的两个元素
*
* @param a
* @param i
* @param j
*/
protected void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* 在一行中打印数组
*
* @param a
*/
protected void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
}
选择排序：
public class Selection extends AbstractSort {
@Override
public void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i; //最小元素的索引
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[min])) min = j;
exch(a, i, min);
}
}
}
}
插入排序
public class Insertion extends AbstractSort {
@Override
public void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
}
算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms
网友评论