排序算法小结

排序算法经常会忘记，记录下来，方便以后快速查看

定义排序接口

public interface ISort {
    public void sort(int[] array);
}

冒泡排序

排序思想

1. 相邻的元素,前面的比后面大，交换位置
2. 每对相邻元素做同样处理，从第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤，除去上一趟排序的最后一个
4. 重复上面的步骤，直到只剩第一个数字

算法实现

public class BubbleSort implements ISort {

    @Override
    public void sort(int[] array) {
        for (int i = array.length - 2; i > 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

快速排序

排序思想(一趟排序)

1. 设置两个变量i、j，排序开始的时候：i=0，j=N-1
2. 以第一个数组元素作为关键数据，赋值给key，即key=A[0]
3. 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]
4. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]交换
5. 重复第3、4步，直到i=j

算法实现

public class QuickSort implements ISort {
    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private void quickSort(int[] array, int left, int right) {
        if (left > right) {
            return;
        }
        int i = left, j = right;
        int flag = array[left];
        while (i < j) {
            while (j > i && array[j] >= flag) {
                j--;
            }
            while (i < j && array[i] < flag) {
                i++;
            }
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        if (array[i] < array[left]) {
            int temp = array[left];
            array[left] = array[i];
            array[i] = temp;
        }
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }
}

堆排序

算法思想

1. 创建最大堆（Build Max Heap)，使得子节点永远小于父节点
2. 移除位在第一个数据的根节点，并做最大堆调整的递归运算

算法实现

public class HeepSort implements ISort {
    @Override
    public void sort(int[] array) {
        heepSort(array);
    }

    private void heepSort(int[] array) {
        for (int i = array.length - 1; i > 0; i--) {
            heepUp(array, i);
        }
        for (int i = array.length - 1; i > 0; i--) {
            int tmp = array[0];
            array[0] = array[i];
            array[i] = tmp;
            heepDown(array, i - 1, 0);
        }
    }

    private void heepUp(int[] array, int pos) {
        while (pos > 0) {
            int father = (pos - 1) / 2;
            if (array[pos] > array[father]) {
                int tmp = array[pos];
                array[pos] = array[father];
                array[father] = tmp;
            }
            pos = father;
        }
    }

    private void heepDown(int[] array, int size, int root) {
        int large = root;
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        if (left <= size && array[large] < array[left]) {
            large = left;
        }
        if (right <= size && array[large] < array[right]) {
            large = right;
        }
        if (large != root) {
            int tmp = array[root];
            array[root] = array[large];
            array[large] = tmp;
            heepDown(array, size, large);
        }
    }
}

排序测试

• 计时辅助工具类

/**
 * 记录一段时间间隔
 */
public class TimeDelta {

    private long time;

    public TimeDelta() {
        this.time = System.currentTimeMillis();
    }

    public long getDelta() {
        return System.currentTimeMillis() - time;
    }

    public void renew() {
        time = System.currentTimeMillis();
    }
}

• 测试代码

/**
 * 随机生成 n 个数， 分别使用以上实现算法排序，记录耗时
 */
public class SortTest {

    public static void main(String[] args) {
        int size = 10000;

        int[] array = new int[size];
        Random random = new Random(System.currentTimeMillis());
        TimeDelta timeDelta = new TimeDelta();
        ISort sort;

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(100) + 1;
        }
        sort = new BubbleSort();
        timeDelta.renew();
        sort.sort(array);
        System.out.println(String.format("冒泡耗时(size:%s): %s", size, timeDelta.getDelta()));

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(100) + 1;
        }
        sort = new QuickSort();
        timeDelta.renew();
        sort.sort(array);
        System.out.println(String.format("快排耗时(size:%s): %s", size, timeDelta.getDelta()));

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(100) + 1;
        }
        sort = new HeepSort();
        timeDelta.renew();
        sort.sort(array);
        System.out.println(String.format("堆排耗时(size:%s): %s", size, timeDelta.getDelta()));
    }
}

• 测试输出

冒泡耗时(size:100): 1
快排耗时(size:100): 0
堆排耗时(size:100): 0

冒泡耗时(size:1000): 3
快排耗时(size:1000): 0
堆排耗时(size:1000): 0

冒泡耗时(size:10000): 131
快排耗时(size:10000): 4
堆排耗时(size:10000): 5

冒泡耗时(size:100000): 16252
快排耗时(size:100000): 32
堆排耗时(size:100000): 16

• 结论(数组随机生成)

1. 冒泡排序耗时最久
2. 快速排序在数据量小的时候略优于堆排序，数据量大的时候性能不如堆排序

以上排序算法复杂度

排序算法	时间复杂度	空间复杂度
冒泡排序	O(n^2)	O(1)
快速排序	O(n^2)	O(1)
堆排序	O(n*log(n))	O(1)