2020-04-30-排序算法

冒泡排序

    public void sort(List<Integer> list) {
        // 平均时间复杂度O(n^2)
        for (int i = 0; i < list.size(); i++) {
            // 每次从第一个数开始遍历
            for (int j = 0; j < list.size() - i - 1; j++) {
                // 每一轮排序后，最后一个数字最大
                if (list.get(j) > list.get(j + 1)) {
                    int temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                    count++;
                }
            }
        }
        System.out.println("Bubble sort count=" + count);
    }

直接选择排序

    public void sort(List<Integer> list) {
        // 平均时间复杂度O(n^2)
        for (int i = 0; i < list.size() - 1; i++) {
            // 每次从第（i+1）个数开始遍历
            for (int j = i + 1; j < list.size(); j++) {
                // 每一轮排序后第一个数最小
                if (list.get(i) > list.get(j)) {
                    int temp = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, temp);
                    count++;
                }
            }
        }
        System.out.println("Select sort count=" + count);
    }

插入排序

    public void sort(List<Integer> list) {
        // 平均时间复杂度O(n^2)，从第二个数开始遍历
        for (int i = 1; i < list.size(); i++) {
            // 如果后面的数比前面大
            if (list.get(i - 1) > list.get(i)) {
                int temp = list.get(i);
                int j = i;
                // 则往前寻找比它大的数，插入到这个数前面
                while (j > 0 && list.get(j - 1) > temp) {
                    list.set(j, list.get(j - 1));
                    j--;
                    count++;
                }
                list.set(j, temp);
            }
        }
        System.out.println("Insert sort count=" + count);
    }

快速排序

    public void sort(List<Integer> list, int head, int tail) {
        // 如果头部大于等于尾部，结束递归，完成排序
        if (head >= tail) {
            return;
        }
        // 通过一个key值将数组分成两拨，key前面的数都比key小，key后面的数都比key大
        // 时间复杂度缩短为O(n log_n);
        int key = list.get(head);
        int tHead = head;
        int tTail = tail;
        while (tHead < tTail) {
            // 从后往前遍历，直到找到比key小的数，将它设为新的key
            while (tHead < tTail && list.get(tTail) >= key) {
                tTail--;
            }
            // 从前往后遍历，直到找到比key大的数，将它设为新的key
            list.set(tHead, list.get(tTail));
            while (tHead < tTail && list.get(tHead) <= key) {
                tHead++;
            }
            list.set(tTail, list.get(tHead));
        }
        list.set(tHead, key);
        count++;
        sort(list, head, tHead - 1);
        sort(list, tTail + 1, tail);
    }

参考

算法学习笔记17-经典排序算法
八大排序算法稳定性分析