经典排序有以下几种：

O(n²)：冒泡排序、插入排序、选择排序 基于比较
O(nlogn)：归并排序、快速排序 基于比较
O(n)：捅排序、计数排序、基数排序

如何分析排序算法

1，最好时间复杂度，最坏时间复杂度，平均时间复杂度
2，时间复杂度的系数，常数，低阶
3，比较次数和交换次数
排序算法内存消耗
排序算法稳定性

冒泡排序

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Utils.exchange(arr, j, j + 1);
                }
            }
        }
    }

可以优化如果没有交换跳出循环

    public static void sort2(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;//提前退出排序标志
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Utils.exchange(arr, j, j + 1);
                    flag = true;//表示有数据交换
                }
            }
            if (!flag)//没有数据交换提前退出
                break;
        }
    }

冒泡排序性能分析

是原地排序算法么？

冒泡排序只涉及到相邻两个元素交换，空间复杂度是O(1)，所有是原地排序

是稳定排序算法么？

冒泡排序中只有比较才会交换顺序，所以我们控制在相等时不交换元素顺序即可，所以冒泡排序是稳定排序算法

时间复杂度是多少？

最好的情况下数据为有序，我们只需要进行一次冒泡即可，时间复杂度为O(n)
最坏的情况下数据为倒序，我们需要进行n次冒泡操作，时间复杂度为O(n²)
平均时间复杂度为O(n²)

插入排序

    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];
            int j = i - 1;
            //查找插入位置
            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = value;//插入数据
        }
    }

插入排序性能分析

是原地排序算法么？

空间复杂度是O(1)，是原地排序

是稳定排序算法么？

对于相同的值，我们可以把后面出现的元素插入到之前出现元素的后面，所以是稳定排序算法

时间复杂度是多少？

最好的情况下数据为有序，我们只需要遍历一次，时间复杂度为O(n)
最坏的情况下数据为倒序，相当于每次都是在数组的第一个位置插入元素，时间复杂度为O(n²)
平均时间复杂度为O(n²)

选择排序

    //选择排序：从待数组中选择出一个最小放入排序数组中以此类推
    public static void sort(int[] arr) {
        int minIndex;
        for (int i = 0; i < arr.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            Utils.exchange(arr, i, minIndex);
        }
    }

选择排序性能分析

是原地排序算法么？

空间复杂度是O(1)，是原地排序

是稳定排序算法么？

不是稳定的排序算法

时间复杂度是多少？

最好的情况下数据为有序，复杂度为O(n²)
最坏的情况下数据为倒序，复杂度为O(n²)
平均时间复杂度为O(n²)