总体预览

排序算法	时间复杂度			空间复杂度	稳定性
	最好	最坏	平均
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
希尔排序	O(n log n)	O(n^2)	O(n log n)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n log n)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n^2)	O(n+k)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

名词解释:

n: 数据规模
k: “桶”的个数

冒泡排序

重复的遍历要排序的序列,依次比较两个元素,如果他们的顺序不符合要求,交换它们,直到没有需要交换为止.算法名字是因为越小的元素会经过交换慢慢到数列顶端。

算法步骤

相邻比较与交换：对数组中的每一对相邻元素进行比较，若顺序不符（升序排序时前一个大于后一个，降序反之），则交换两者位置。
逐轮推进：对所有元素进行此操作，每轮结束后确保最右侧元素为当前子序列的最大/最小值。后续轮次排除已排序部分，仅处理剩余元素。
迭代直至完成：重复上述步骤，直到整个数组完全排序（即某轮遍历无交换发生）。

代码实现

public class BubbleSortOptimized {
    public static void bubbleSortOptimized(int[] array) {
        int n = array.length;
        boolean swapped; // 标记是否发生过交换

        for (int i = 0; i < n - 1; i++) {
            swapped = false; // 初始化每轮比较的交换标志为false
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 发生交换
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true; // 设置交换标志为true
                }
            }

            // 如果一轮比较下来没有发生过交换，说明数组已有序，无需继续后续的比较
            if (!swapped) {
                break;
            }
        }
    }

    // 测试优化后的冒泡排序
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("原始数组：");
        for (int value : arr) {
            System.out.print(value + " ");
        }

        bubbleSortOptimized(arr);

        System.out.println("\n\n排序后的数组：");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

选择排序

选择排序是通过不断遍历待排序序列并选取当前最小（或最大）元素放入已排序序列的过程来实现排序的一种算法。

算法步骤

在未排序部分找出最小（或最大）值。
将这个最小（或最大）值与未排序部分的第一个元素交换位置，使其进入已排序部分。
重复上述过程，每次都在剩余的未排序部分里找最小（或最大）值，并将其与未排序部分的首个元素交换。
直到所有元素都被包含进已排序部分，排序完成。

代码实现

public class SelectionSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 找到未排序部分的最小值索引
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将找到的最小值与未排序部分的第一个元素交换
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        sort(array);
        System.out.println("Sorted Array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

这段代码首先定义了一个 sort方法用于执行选择排序算法，它会遍历数组中的每个元素，每次都找到剩余未排序部分的最小值，并与当前未排序部分的第一个元素交换位置。

插入排序

插入排序是将待排序的元素逐个插入到已排序好的序列中的适当位置，从而达到整个序列有序的一种排序算法。

算法步骤

把数组视为若干个已排序区间和一个未排序区间的组合，初始时，已排序区间只有一个元素（即数组的第一个元素）。
取出未排序区间的第一个元素，称为“基准”。
从已排序区间的最后一个元素开始向前比较，如果“基准”小于已排序元素，将该元素向后移动一位，重复此过程直到找到合适的插入位置。
将“基准”插入到已排序区间的合适位置。
重复步骤 2-4，每次从未排序区间取出一个元素进行插入，直到未排序区间为空，排序完成。

代码实现

public class InsertionSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; // 将当前元素作为待插入的键值
            int j = i - 1;

            // 将大于key的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 插入key到正确的位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        sort(array);
        System.out.println("Sorted Array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

该方法遍历数组中的每一个元素，对于每个元素，它都会检查前一位置的元素是否比当前元素大，如果是，则将前一位置的元素后移一位，直到找到合适的位置将当前元素插入。

快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。

算法步骤

选择基准：选择待排序数组中的一个元素作为基准（通常选择第一个或最后一个元素）。
分区：将数组中所有其他元素与基准进行比较，将小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，这一步完成后，基准处于最终排序后所在的位置。
递归排序：对基准左右两侧的两个子数组（如果它们的长度都不为 0）重复第一步和第二步，即分别对左子数组和右子数组再次进行快速排序。
终止条件：当子数组只剩下一个元素或者为空时，认为该子数组已经有序，停止递归。

总结起来，快速排序的核心思想就是“分而治之”，通过不断划分、排序子数组，逐步将整个数组变得有序。

代码实现

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // pi 是分区的中间点
            int pi = partition(arr, low, high);

            // 对分区左侧和右侧分别进行快速排序
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = (low - 1); // i指向小于基准的最后一个元素

        for (int j = low; j < high; j++) {
            // 当前元素小于或等于基准时，将i后移并将当前元素赋给i+1的位置
            if (arr[j] <= pivot) {
                i++;

                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准值与i+1位置上的数交换
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] array = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(array, 0, array.length - 1);
        System.out.println("Sorted Array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

我们定义了一个quickSort方法，它接受一个数组以及起始和结束索引作为参数，表示要排序的子数组范围。在quickSort方法内部首先判断是否需要继续排序（即子数组是否有多个元素），然后调用partition方法进行分区操作。在partition方法中，我们选定一个基准元素，将所有小于基准的元素移到基准的左侧，大于基准的元素移到基准的右侧，最后返回基准的新位置。