@[TOC]

冒泡排序

原理

每一次排序都会把大的元素移到后边
第一次排序把最大的移到了最后边，
第二次把其次第二大的移到最后边，所以才有减i的操作

时间复杂度

O(n*n)

空间复杂度

O(1)

代码

冒泡排序算是最经典的排序算法了

    public static void main(String[] args) {
        Integer[] a = {0,-10,-8, 8,7,9,-90};
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j]>a[j+1]){
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        // 验证
        Stream.of(a).forEach(System.out::println);
    }

快速排序

原理

时间复杂度

O(n log n) 最坏是O(n*n)

空间复杂度

O(log n)

代码

public static void main(String[] args) {
        Integer[] a = {0,-10,-8, 8,7,9,-90};

        // 快排
        quickSort(a, 0,a.length-1);

        // 验证
        Stream.of(a).forEach(System.out::println);
    }

    public static void quickSort(Integer[] arr, Integer low, Integer high){
        // 这个退出条件一定不能少，否则堆栈溢出
        if (low>high){
            return;
        }

        int i,j,tmp,t;
        i = low; j = high; tmp=arr[low];
        while (i<j){
            // 先遍历j，找到比基准元素小的，找不到就一直遍历
            while (arr[j]>=tmp && i<j){
                j--;
            }
            // 然后让i,低位走，找到比基准元素tmp大的
            while (arr[i]<=tmp && i<j){
                i++;
            }

            if (i<j){
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;

            }
        }
        arr[low]  = arr[i];
        arr[i] = tmp;

        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);
    }

问题

快排中为什么一定是右边先开始循环？
从右边先开始的前提是我们选择序列中最左边的元素最为基准值。
先从右边开始可以保证i,j相等的时候，arr[i] = arr[j] 小于基准值p。这样交换之后才能保证基准值左右两边分别小于和大于它的值。

参考文章

• 快速排序

• 快速排序 知乎专栏

• 快速排序