算法

常用的排序算法总结

《算法》- 第 2 章 排序

常见排序算法总结与实现(冒泡、插入、选择、希尔、堆排序、归并、快排)

冒泡排序

1. 除最后一个元素或已排好序的元素外，将所有的元素与相邻元素进行比较，交换。
2. 对每一对相邻元素作同样的工作，使得最后的元素会是最大的数。
3. 重复上面的步骤，直到没有任何一对数字需要比较。

public class BubbleSort {
    public void sort(Comparable[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 交换标志
            boolean swap = false;
            // arr.length - 1 - i 号元素已排好序
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    Comparable temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap) {
                // 如果没有发生交换，代表已经排好序，直接返回
                return;
            }
        }
    }
}

选择排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

public class SelectionSort {
    public void sort(Comparable[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 保留每一次遍历时的最小值对应的索引
            int minIndex = i;
            // 遍历得到当前未排序中的最小值所在索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex].compareTo(arr[j]) > 0) {
                    minIndex = j;
                }
            }
            // 将最小值与当前值交换位置
            Comparable temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

插入排序

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置。
6. 重复步骤 2-5。