目录：

1.常见算法复杂度
2.冒泡排序
3.选择排序

1.常见算法复杂度

image.png

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

2.冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。适用于少量数据排序，数据越少性能越优

2.1算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

2.2代码实现

/**
     * 冒泡排序 只使用于少量数据
     *
     * @param array {3,2,5,8,1}
     *              1次循环  2 3 5 1 8
     *              2次循环  2 3 1 5 8
     *              3次循环  2 1 3 5 8
     *              4次循环  2 3 5 1 8
     *              5次循环  1 2 3 5 8
     */
    public void bubbleSort(int[] array) {
        // n*(n-1)/2    n
        for (int i = array.length - 1; i > 0; i--) {
            boolean flag = true;
            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;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

3.选择排序（Select Sort）

选择排序（Select Sort） 是直观的排序，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 双重循环时间复杂度为 O(n^2)

3.1算法描述

• 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
• 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
• 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

3.2代码实现

/**
     * 选择排序 使用于少量数据
     *
     * @param array {3,2,5,8,1}
     *              1次循环  1 2 5 8 3
     *              2次循环  1 2 5 8 3
     *              3次循环  1 2 3 8 5
     *              4次循环  1 2 3 5 8
     *              5次循环  1 2 3 5 8
     */
    public void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[index]) {
                    index = j;
                }
            }
            //{1,2,3,5,8}
            //如果已经是最小的，就不需要交换
            if (index != i) {
                int temp = array[index];
                array[index] = array[i];
                array[i] = temp;
            }
        }
    }