冒泡、快速以及插入排序算法

原创
2016/06/07 13:51
阅读数 40

先定义排序接口:

package com.vincent.sort;

import java.util.List;

/**
 * Vincent 创建于 2016/6/4.
 */
public interface ISort {
    /**
     * 递减
     * @param dataList
     * @return 排序耗时
     */
   long sortDesc(final List<Integer> dataList);

    /**
     * 递增
     * @param dataList
     * @return 排序耗时
     */
   long sortAsc(final List<Integer> dataList);

}

冒昧排序:

package com.vincent.sort;

import java.util.List;

/**
 * Vincent 创建于 2016/6/4.
 * 冒泡排序
 * 以递增为例
 * 先比较前两个数据,如果第一个(S1)大于第二个(S2),则交换数据
 * 循环对比,S2与S3,S3与S4。。。如果前一个比后一个大,则交换数据,通过一次循环对比,则最大的在最右侧了
 * 第二次从头开始对比交换,但是无须对比最后一个数据(因为经过第一次循环,Sn-1是最大的了)
 * 通过多次循环之后,整体是有序的了
 */
public class BubbleSort implements ISort {

    public long sortDesc(List<Integer> dataList) {

        long begin = System.currentTimeMillis();

        int size = dataList.size();

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                Integer a = dataList.get(j);
                Integer b = dataList.get(j + 1);
                if (a < b) {
                    dataList.set(j, b);
                    dataList.set(j + 1, a);
                }
            }
        }
        long end = System.currentTimeMillis();
        return end - begin;
    }

    public long sortAsc(List<Integer> dataList) {
        long begin = System.currentTimeMillis();

        int size = dataList.size();

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                Integer a = dataList.get(j);
                Integer b = dataList.get(j + 1);
                if (a > b) {
                    dataList.set(j, b);
                    dataList.set(j + 1, a);
                }
            }
        }
        long end = System.currentTimeMillis();
        return end - begin;
    }
}

快速排序:

package com.vincent.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * Vincent 创建于 2016/6/4.
 * 快速排序
 * 以升序为例,首先选择一个基准数据(这里从索引0开始),如果比该基准数据小或相等,则放入左侧集合,否则放入右侧集合。
 * 如果两侧中有一个集合empty,则基准数据重新选择(这里选择索引+1)
 * 在这个时候,left是只有比基准数据小或相等的数据集合,然后递归排序左侧集合,同理右侧一样
 *
 * 现在假设要排序的集合只有两个数据,那么肯定小的在左侧集合,大的在右侧集合,将左右两侧合并即是有序集合;
 * 如果是三个数据,假设第一次:左侧集合(S1)只有一个数据,右侧(S2)集合有两个数据,那么经过一次递归之后,
 * 左侧(S1)集合没变,右侧(S2)集合变成两个(S21,S22)(小的在左侧(S21),大的在右侧(S22),合并之后右侧(S2)集合变成有序的),
 * 再将左(S1)右(S2)合并,整体变成有序的
 *
 * 通过多次递归之后,原始数据集合里就是有序的了
 */
public class QuickSort implements ISort {

    public long sortDesc(List<Integer> dataList) {
        long begin = System.currentTimeMillis();

        int size = dataList.size();
        if (size <= 1) {
            return 0l;
        }
        int index = 0;

        List<Integer> leftList = new ArrayList<Integer>(size);

        List<Integer> rightList = new ArrayList<Integer>(size);

        getLeftAndRightList(dataList, index, leftList, rightList, false);


        sortDesc(leftList);
        sortDesc(rightList);
        dataList.clear();
        dataList.addAll(leftList);
        dataList.addAll(rightList);

        long end = System.currentTimeMillis();
        return end - begin;
    }

    private void getLeftAndRightList(List<Integer> dataList, int index, List<Integer> leftList, List<Integer> rightList, boolean asc) {
        Integer centerData = dataList.get(index);

        for (Integer data : dataList) {
            if (data.intValue() <= centerData.intValue() ? asc : !asc) {
                leftList.add(data);
            } else {
                rightList.add(data);
            }
        }

        if (leftList.isEmpty() || rightList.isEmpty()) {
            leftList.clear();
            rightList.clear();
            index++;
            int size = dataList.size();
            if (index < size) {
                getLeftAndRightList(dataList, index, leftList, rightList, asc);
            }
        }
    }

    public long sortAsc(List<Integer> dataList) {
        long begin = System.currentTimeMillis();

        int size = dataList.size();
        if (size <= 1) {
            return 0l;
        }
        int index = 0;

        List<Integer> leftList = new ArrayList<Integer>(size);

        List<Integer> rightList = new ArrayList<Integer>(size);

        getLeftAndRightList(dataList, index, leftList, rightList, true);


        sortAsc(leftList);
        sortAsc(rightList);
        dataList.clear();
        dataList.addAll(leftList);
        dataList.addAll(rightList);

        long end = System.currentTimeMillis();
        return end - begin;
    }
}

插入排序:

package com.vincent.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * Vincent 创建于 2016/6/6.
 * 插入排序
 * 以递增为例
 * 无序集合S1,空集合S2
 * 选择S1的第一个集合添加到S2中
 * 选择S1的第二个集合,如果小于S2的第一个集合,则插入到头部,否则添加到尾部(add方法),
 * 循环遍历S1的集合,插入到S2的合适位置即可
 */
public class InsertSort implements ISort {
    public long sortDesc(List<Integer> dataList) {
        long begin = System.currentTimeMillis();
        int size = dataList.size();
        List<Integer> sortList = new ArrayList<Integer>(size);
        for (Integer data : dataList) {
            if (sortList.isEmpty()) {
                sortList.add(data);
            } else {
                int sortSize = sortList.size();
                for (int i = 0; i < sortSize; i++) {
                    Integer sortData = sortList.get(i);
                    if (data > sortData) {
                        sortList.add(i, data);
                        break;
                    } else if (i == sortSize - 1) {
                        sortList.add(data);
                        break;
                    }
                }
            }
        }

        dataList.clear();
        dataList.addAll(sortList);
        long end = System.currentTimeMillis();
        return end - begin;
    }

    public long sortAsc(List<Integer> dataList) {
        long begin = System.currentTimeMillis();
        int size = dataList.size();
        List<Integer> sortList = new ArrayList<Integer>(size);
        for (Integer data : dataList) {
            if (sortList.isEmpty()) {
                sortList.add(data);
            } else {
                int sortSize = sortList.size();
                for (int i = 0; i < sortSize; i++) {
                    Integer sortData = sortList.get(i);
                    if (data < sortData) {
                        sortList.add(i, data);
                        break;
                    } else if (i == sortSize - 1) {
                        sortList.add(data);
                        break;
                    }
                }
            }
        }
        dataList.clear();
        dataList.addAll(sortList);
        long end = System.currentTimeMillis();
        return end - begin;
    }
}

 

展开阅读全文
打赏
0
2 收藏
分享
加载中
更多评论
打赏
0 评论
2 收藏
0
分享
返回顶部
顶部