线性排序的实现

java 代码

/**
 * 线性表
 */
package line;

/**
 * @author sumbeam
 *
 */
public class LineSort {

    // 数据结构
    private int data[];

    // 最大容量
    private int maxSize;

    // 实际容量
    private int size;

    public LineSort(int maxSize) {

        this.maxSize = maxSize;
        data = new int[maxSize];
        size = 0;
    }

    /**
     * 查找某数据的位置
     *
     * @param data
     *            数据
     * @return 位置
     */
    public int inStr(int data) {
        for (int i = 0; i < this.data.length; i++) {
            if (this.data[i] == data)
                return i;
        }
        return -1;
    }

    /**
     * 判断是否到达最后一位
     *
     * @return 是否已满
     */
    public boolean isEnd() {
        return size == maxSize;
    }

    /**
     * 判断数据是否为空
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在老数据前增加一个新的数据
     *
     * @param oldData
     *            老数据
     * @param newData
     *            新数据
     * @return 是否成功
     */
    public boolean add(int oldData, int newData) {

        int p = inStr(oldData);
        if (p != -1)
            return insert(newData, p);
        return false;
    }

    /**
     * 将数据插入在第一位
     *
     * @param data
     *            要插入的数据
     * @return 是否成功
     */
    public boolean addFirst(int data) {

        return insert(data, 0);
    }

    /**
     * 定义一个插入数据的方法
     *
     * @param data
     *            要插入的数据
     * @param p
     *            要插入的位置
     * @return 是否插入成功
     */
    public boolean insert(int data, int p) {
        if (isEnd()) {
            System.out.println("数据已满!");
            return false;
        }
        for (int i = (size - 1); i >= p; i--) {
            this.data[i + 1] = this.data[i];
        }
        this.size++;
        this.data[p] = data;
        return true;
    }

    /**
     * 在最后一位插入一个数据
     *
     * @param data
     *            要插入的数据
     * @return 是否成功
     */
    public boolean addLast(int data) {
        return insert(data, size);
    }

    /**
     * 先移除一个数据
     *
     * @param data
     *            要删除的数据
     * @return 是否成功
     */
    public boolean remove(int data) {
        if (isEmpty()) {
            System.out.println("数据是空的!");
            return false;
        }
        int p = inStr(data);
        if (p != -1) {
            for (int i = p; i < size; i++) {
                this.data[i] = this.data[i + 1];
            }
            size--;
            return true;
        }
        return false;
    }

    /**
     * 修改数据
     *
     * @param olddata
     *            要被修改的数据
     * @param newdata
     *            修改后的数据
     * @return 是否修改成功
     */
    public boolean updata(int olddata, int newdata) {
        int p = inStr(olddata);
        if (p != -1) {
            this.data[p] = newdata;
            return true;
        }
        return false;
    }

    /**
     * 显示所有数据
     */
    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.println(this.data[i]);
        }
    }

    /**
     * 交换位置
     *
     * @param i
     *            位置i
     * @param j
     *            位置j
     */
    public void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * 选择排序
     */
    public void selectSort() {
        for (int i = 0; i < size - 1; i++) {
            int k = i;
            for (int j = i + 1; j < size; j++) {
                if (data[k] > data[j])
                    k = j;
            }
            if (k != i)
                swap(k, i);
        }
    }

    /**
     * 冒泡排序
     */
    public void bubbleSort() {
        for (int i = 0; i < size - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < size - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    flag = true;
                    swap(j, j + 1);
                }
            }
            if (!flag)
                break;
        }
    }

    /**
     * 插入排序
     */
    public void interSort() {
        for (int i = 0; i < size; i++) {
            int temp = data[i];
            int sort = i;
            while (sort > 0 && temp < data[sort - 1]) {
                data[sort] = data[sort - 1];
                sort--;
            }
            data[sort] = temp;
        }
    }

    public static void main(String[] args) {
        LineSort line = new LineSort(1000);
        line.addFirst(1);
        line.addFirst(-1);
        line.add(-1, 2);
        line.add(1, 3);
        line.addLast(100);
        line.updata(3, 90);
        // line.remove(-1);
        // line.remove(2);
        // line.remove(100);
        // line.remove(90);
        // line.remove(1);
        // line.selectSort();
        // line.bubbleSort();
        line.interSort();
        line.display();
    }
}