简单排序

众所周知，JDK提供了java.util.Arrays工具类，能通过sort方法对基本类型的数据或者Java对象进行排序。

本文通过学习及使用三种简单排序算法（冒泡排序、选择排序、插入排序），实现对存储Java对象的数组进行排序。

以便使大家在学习简单排序算法的同时，又能对Arrays的排序实现有个更加感性的认知。

package com.zhangsx.sort;

import java.util.Comparator;

/**
 * 简单排序算法的实现。
 * 包括冒泡排序、选择排序和插入排序；可对对象数组按照指定的排序规则进行排序。
 * 
 * 数组中的对象必须提供可比较的功能。
 * 有以下两种方式为对象实现可比较功能：
 * 1.对象实现java.lang.Comparable接口，提供比较规则。
 * 2.提供一个实现了java.util.Comparator接口的比较器。
 * 
 * @version 1.00 2010-4-11
 * @since 1.5
 * @author ZhangShixi
 */
public class SimpleSort {
    private SimpleSort() {
    }
    /**
     * 冒泡排序。
     * 
     * 排序数组中的对象必须实现java.lang.Comparable接口，提供排序比较规则。
     * 否则，调用时会抛出运行时异常java.lang.ClassCastException。
     * 
     * 算法描述如下：
     * 外层循环控制未排序的数据项，从数组最后一项开始，向低位递减。
     * 内层循环控制数据项的比较和排序，从数组起始项开始，向高位递增。
     * 每次内层循环结束，即外层循环移动一次时，数组的右侧将多一项排好序的数据。
     * 
     * 1.从数组起始位置开始，比较数组前两项。
     * 2.如果第一项大于第二项，则交换这两项。
     * 3.数组下标下移一位，继续比较下两项数据的大小。
     * 4.当遇到排好序的数据项时，返回到数组首项，重新开始下一趟排序。
     * 
     * @param arrays 排序数组
     */
    @SuppressWarnings("unchecked")
    public static void bubbleSort(Object[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        for (int out = arrays.length - 1; out > 0; out--) {
            for (int in = 0; in < out; in++) {
                if (((Comparable) arrays[in]).compareTo(arrays[in + 1]) > 0) {
                    swap(arrays, in, in + 1);
                }
            }
        }
    }

    /**
     * 冒泡排序。
     * 按提供的比较器的比较规则进行排序。
     * @param arrays 排序数组
     * @param compara 排序比较器
     */
    public static <T> void bubbleSort(T[] arrays, Comparator<? super T> compara) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        for (int out = arrays.length - 1; out > 0; out--) {
            for (int in = 0; in < out; in++) {
                if (compara.compare(arrays[in], arrays[in + 1]) > 0) {
                    swap(arrays, in, in + 1);
                }
            }
        }
    }

    /**
     * 选择排序。
     * 
     * 排序数组中的对象必须实现java.lang.Comparable接口，提供排序比较规则。
     * 否则，调用时会抛出运行时异常java.lang.ClassCastException。
     * 
     * 算法描述如下：
     * 外层循环控制未排序的数据项及交换最小数据项，从数组起始位置开始，向高位递增。
     * 内层循环控制查找最小数据项，从外层循环所指向的位置开始，向高位递增。
     * 每次内层循环结束，即外层循环移动一次时，数组的左侧将多一项排好序的数据。
     *
     * 1.外层循环从数组起始位置开始，并将最小数据项置为最小数据项。
     * 2.内层循环从外层循环指向的下一个数据项开始，分别与最小数据项进行比较。
     * 3.如果内层循环所指的当前数据项小于最小数据项，则将当前数据项下标置为最小数据项下标。
     * 4.循环比较，直至内层循环结束，将找到为排序部分的最小数据项的下标。
     * 5.交换外层循环当前数据项与内层循环找到的最小数据项。继续下一排序。
     * 
     * @param arrays 排序数组
     */
    @SuppressWarnings("unchecked")
    public static <T> void selectSort(Object[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        int minIndex;
        for (int out = 0; out < arrays.length - 1; out++) {
            minIndex = out;

            for (int in = out + 1; in < arrays.length; in++) {
                if (((Comparable) arrays[minIndex]).compareTo(arrays[in]) > 0) {
                    minIndex = in;
                }
            }
            swap(arrays, out, minIndex);
        }
    }

    /**
     * 选择排序。
     * 按提供的比较器的比较规则进行排序。
     * @param arrays 排序数组
     * @param compara 排序比较器
     */
    public static <T> void selectSort(T[] arrays, Comparator<? super T> compara) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        int minIndex;
        for (int out = 0; out < arrays.length - 1; out++) {
            minIndex = out;

            for (int in = out + 1; in < arrays.length; in++) {
                if (compara.compare(arrays[minIndex], arrays[in]) > 0) {
                    minIndex = in;
                }
            }
            swap(arrays, out, minIndex);
        }
    }

    /**
     * 插入排序。
     * 
     * 排序数组中的对象必须实现java.lang.Comparable接口，提供排序比较规则。
     * 否则，调用时会抛出运行时异常java.lang.ClassCastException。
     * 
     * 算法描述如下：
     * 外层循环控制未排序的数据项及循环交换最小数据项，从数组起始位置开始，向高位递增。
     * 内层循环控制查找最小数据项，从外层循环所指向的位置开始，向高位递增。
     * 每次内层循环结束，即外层循环移动一次时，数组的左侧将多一项排好序的数据。
     * 
     * 1.外层循环从数组第二项开始，记录当前数据项及其下标。
     * 2.当数据项指向的数组下标大于0时，且当前数据项比其前一个数据项大时，交换这两项数据。
     * 3.数组下标指针减1，按条件2，循环比较前两项数据。
     * 4.当条件不满足时，跳出内层循环，并将外层循环的当前数据项赋予内层指针下标所指的数据项。
     * 5.外层循环递增，继续下一排序。
     * 
     * @param arrays 排序数组
     */
    @SuppressWarnings("unchecked")
    public static void insertSort(Object[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        int in;
        for (int out = 1; out < arrays.length; out++) {
            Object temp = arrays[out];
            in = out;

            while (in > 0 && ((Comparable) arrays[in - 1]).compareTo(temp) > 0) {
                arrays[in] = arrays[in - 1];
                in--;
            }
            arrays[in] = temp;
        }
    }

    /**
     * 插入排序。
     * 按提供的比较器的比较规则进行排序。
     * @param arrays 排序数组
     * @param compara 排序比较器
     */
    public static <T> void insertSort(T[] arrays, Comparator<? super T> compara) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        int in;
        for (int out = 1; out < arrays.length; out++) {
            T temp = arrays[out];
            in = out;

            while (in > 0 && compara.compare(arrays[in - 1], temp) > 0) {
                arrays[in] = arrays[in - 1];
                in--;
            }
            arrays[in] = temp;
        }
    }

    /**
     * 交换指定数组中的指定下标的两个数据项。
     * @param first 第一个数据项的下标
     * @param second 第二个数据项的下标
     */
    private static void swap(Object[] arrays, int firstIndex, int secondIndex) {
        Object temp = arrays[firstIndex];
        arrays[firstIndex] = arrays[secondIndex];
        arrays[secondIndex] = temp;
    }
}

 

测试代码如下：

package com.zhangsx.sort;

import java.util.Comparator;
import java.util.Random;
import junit.framework.TestCase;

/**
 * 测试简单排序算法的实现。
 * @version 1.00 2010-4-11
 * @since 1.5
 * @author ZhangShixi
 */
public class SimpleSortTest extends TestCase {

    Person[] persons;
    Comparator<Person> comparator;

    @Override
    protected void setUp() throws Exception {
        persons = new Person[10];
        comparator = new PersonComparator();

        Person person;
        Random random = new Random();
        for (int count = 0; count < 10; count++) {
            int value = random.nextInt(100);
            person = new Person("name-" + value, value);
            persons[count] = person;
        }

        display();
    }

    @Override
    protected void tearDown() throws Exception {
        display();
    }

    /**
     * 测试冒泡排序算法的实现。
     */
    public void testBubbleSort() {
        SimpleSort.bubbleSort(persons, comparator);
        display();
        SimpleSort.bubbleSort(persons);
    }

    /**
     * 测试选择排序算法的实现。
     */
    public void testSelectSort() {
        SimpleSort.selectSort(persons);
        display();
        SimpleSort.selectSort(persons, comparator);
    }

    /**
     * 测试插入排序算法的实现。
     */
    public void testInsertSort() {
        SimpleSort.insertSort(persons);
        display();
        SimpleSort.insertSort(persons, comparator);
    }
    /**
     * 显示排序结果。
     */
    private void display() {
        for (Person person : persons) {
            System.out.println(person.toString());
        }
        System.out.println("-------------------");
    }
}

 

数组中的比较对象：实现Comparable接口，按年龄大小升序排序。

package com.zhangsx.sort;

/**
 * 人，排序对象。
 * @version 1.00 2010-4-11
 * @since 1.5
 * @author ZhangShixi
 */
public class Person implements Comparable<Person> {

    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person: [" + this.age + "]";
    }

    public int compareTo(Person person) {
        if (this.age > person.getAge()) {
            return 1;
        } else if (this.age < person.getAge()) {
            return -1;
        } else {
            return 0;
        }
    }
}

 

自定义的对象比较器：按年龄大小降序排序。

package com.zhangsx.sort;

import java.util.Comparator;

/**
 * 自定义比较器。
 * @version 1.00 2010-4-11
 * @since 1.5
 * @author ZhangShixi
 */
public class PersonComparator implements Comparator<Person> {

    public int compare(Person person1, Person person2) {
        if (person1.getAge() > person2.getAge()) {
            return -1;
        } else if (person1.getAge() < person2.getAge()) {
            return 1;
        } else {
            return 0;
        }
    }
}