排序算法复习

排序算法的一些复习笔记。

顺便分享一个视频,群魔乱舞到秩序与整洁的变化挺爽的(小心精神污染):15 Sorting Algorithms in 6 Minutes - YouTube

冒泡排序

维基百科: > 重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 > 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 > 冒泡排序对n个项目需要O(n^2)的比较次数,且可以原地排序。

演示:

代码:

package bubble;

import java.util.Random;

/**
 * @author Boli Tao
 */
public class BubbleSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    public static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    /**
     * bubble sort
     *
     * @param arr the array to be sorted
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[100000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        bubbleSort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("冒泡排序写错了");
            }
        }
        System.out.println("Test complete.");
    }
}

选择排序

冒泡排序比较的是相邻元素,而选择排序是比较整体,并且选择排序交换的是最小值和未经排序“头部”元素。其时间复杂度为 O(n^2)。

演示:

代码:

package selection;

/**
 * @author Boli Tao
 */
public class SelectionSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            swap(arr, i, min_idx);
        }
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        selectionSort(arr);
        System.out.print("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i != arr.length - 1) {
                System.out.print(" ,");
            }
        }
        System.out.print("]");
    }
}

插入排序

插入排序通过找到合适位置进行插入达到排序目的。时间复杂度为 O(n^2)。

演示:

代码:

package insertion;

/**
 * @author Boli Tao
 */
public class InsertionSort {
    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 后移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            // 插入
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        insertionSort(arr);
        StringBuilder builder = new StringBuilder();
        builder.append("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            builder.append(arr[i]);
            if (i != arr.length - 1) {
                builder.append(" ,");
            }
        }
        builder.append("]");
        System.out.println(builder.toString());
    }
}

归并排序

空间复杂度 O(n),时间复杂度 O(nlogn)。

演示:

package merge;

/**
 * @author 陶波利
 */
public class MergeSort {
    private static void merge(int[] arr, int l, int m, int r) {
        int leftArraySize = m - l + 1;
        // r - (m + 1) + 1
        int rightArraySize = r - m;

        // temp array
        int[] leftTempArray = new int[leftArraySize];
        int[] rightTempArray = new int[rightArraySize];

        // 把 arr 中的数据拷入两个 temp 数组
        for (int i = 0; i < leftArraySize; i++) {
            leftTempArray[i] = arr[l + i];
        }
        for (int i = 0; i < rightArraySize; i++) {
            rightTempArray[i] = arr[m + 1 + i];
        }

        // 两个 temp 数组的索引
        int i = 0, j = 0;
        // arr 数组的索引
        int k = l;

        // 将 temp 数组的数据按顺序填入 arr
        while (i < leftArraySize && j < rightArraySize) {
            if (leftTempArray[i] <= rightTempArray[j]) {
                arr[k] = leftTempArray[i];
                i++;
            } else {
                arr[k] = rightTempArray[j];
                j++;
            }
            k++;
        }

        while (i < leftArraySize) {
            arr[k] = leftTempArray[i];
            i++;
            k++;
        }

        while (j < rightArraySize) {
            arr[k] = rightTempArray[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }

    public static void main(String[] args) {
        int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
        mergeSort(arr, 0, arr.length - 1);
        StringBuilder builder = new StringBuilder();
        builder.append("Sorted array:\n[");
        for (int i = 0; i < arr.length; i++) {
            builder.append(arr[i]);
            if (i != arr.length - 1) {
                builder.append(" ,");
            }
        }
        builder.append("]");
        System.out.println(builder.toString());
    }
}

快速排序

快速排序相比冒泡排序,不是比较相邻元素,而是比较和交换大数和小数,做到把小数浮到上面、大数沉到下面。

快速排序不稳定,平均时间复杂度为 O(nlogn)。

演示:

代码:

package quick;

import java.util.Random;

/**
 * @author 陶波利
 */
public class QuickSort {
    /**
     * 交换 arr 数组中索引为 index1 和 index2 的值
     *
     * @param arr    array
     * @param index1 index1
     * @param index2 index2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int pivotIndex = left;
        while (left < right) {
            // 从右侧开始寻找比基准数小的元素的索引
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //从左侧开始寻找比基准数大的元素的索引
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 把大数移到右边,小数移到左边
            swap(arr, left, right);
        }
        // 把 pivot 移到中间
        swap(arr, pivotIndex, left);
        return left;
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[1000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        sort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("快排写错了");
            }
        }
    }
}

堆排序

平均时间复杂度为 O(nlogn)。

自己实现一个最大堆,所有的问题都迎刃而解。

代码:

package heap;

import array.Array;

import java.util.Random;

/**
 * @author 陶波利
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    /**
     * 构造函数:将传入数组组成为最大堆
     *
     * @param arr 待化为最大堆的数组
     */
    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * @param index index
     * @return index 的父节点的索引
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 向堆中添加元素
     *
     * @param e 待添加的元素值
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 为满足最大堆性质而设计的元素上浮方法
     *
     * @param k 需要被上浮的元素索引
     */
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 取出堆中最大元素
     *
     * @return
     */
    public E extractMax() {
        E ret = getMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    public E getMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Size is 0, no element in heap.");
        }
        return data.get(0);
    }

    /**
     * 为满足最大堆性质而设计的元素下沉方法
     * TODO: 需要进一步理解
     *
     * @param k 需要被下沉的元素索引
     */
    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            // ↑此时 j 表示孩子节点中更大元素的索引
            if (data.get(k).compareTo(data.get(j)) > 0) {
                break;
            }
            data.swap(k, j);
            k = j;
        }
    }

    public E replace(E e) {
        E ret = getMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

    /**
     * 测试类
     *
     * @param args args
     */
    public static void main(String[] args) {
        int n = 1000000;
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = maxHeap.extractMax();
        }
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("Error: 最大堆实现出现问题!");
            }
        }
        System.out.println("Completed!");
    }
}

自定义的 Array 类如下:

package array;

/**
 * 自定义的 Array 类
 *
 * @author 陶波利
 */
public class Array<E> {
    private E[] data;
    private int size;

    public Array() {
        this(10);
    }

    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(E[] arr) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get() failed, index is illegal.");
        }
        return data[index];
    }

    public void set(int index, E value) {
        data[index] = value;
    }

    public boolean isContaianed(E value) {
        for (E m : data) {
            if (value.equals(m)) {
                return true;
            }
        }
        return false;
    }

    public int find(E value) {
        for (int i = 0; i < data.length; i++) {
            if (value.equals(data[i])) {
                return i;
            }
        }
        return -1;
    }

    public void add(int index, E value) {
//        if (size >= data.length) {
//            throw new IllegalArgumentException("add() method failed, array is full.");
//        }
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
        }
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = value;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    public void addFirst(E value) {
        add(0, value);
    }

    public void addLast(E value) {
        add(size, value);
    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove() failed, index is illegal.");
        }
        E removedValue = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        // loitering objects != memory leak
        data[size] = null;
        if (size == data.length / 4 && data.length / 2 != 0) {
            // TODO: / 4?
            resize(data.length / 2);
        }
        return removedValue;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void removeElement(E value) {
        int index = find(value);
        if (-1 != index) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    public E getLast() {
        return get(size - 1);
    }

    public E getFirst() {
        return get(0);
    }

    /**
     * 交换索引为 i j 的元素
     *
     * @param i index i
     * @param j index j
     */
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

希尔排序

package shell;

import java.util.Random;

/**
 * @author 陶波利
 */
public class ShellSort {
    private static void shellInsert(int[] arr, int d) {
        for (int i = d; i < arr.length; i++) {
            int j = i - d;
            //记录要插入的数据
            int temp = arr[i];
            //从后向前,找到比其小的数的位置
            while (j >= 0 && arr[j] > temp) {
                //向后挪动
                arr[j + d] = arr[j];
                j -= d;
            }
            //存在比其小的数
            if (j != i - d) {
                arr[j + d] = temp;
            }
        }
    }

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int d = arr.length / 2;
        while (d >= 1) {
            shellInsert(arr, d);
            d /= 2;
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] array = new int[1000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }
        shellSort(array);
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i + 1] < array[i]) {
                throw new IllegalArgumentException("希尔排序写错了");
            }
        }
        System.out.println("Test complete.");
    }
}

参考: Sorting Algorithms - GeeksforGeeks francistao/LearningNotes: Enjoy Learning. VisuAlgo - visualising data structures and algorithms through animation 排序算法 - 维基百科,自由的百科全书

updatedupdated2020-10-102020-10-10
加载评论