图1. 小林Coding整理图
排序算法是计算机科学中常见的一类算法，用于将一组数据按照一定规则进行排序。
常见的排序算法包括以下几种：
冒泡排序（Bubble Sort）：通过相邻元素的比较和交换来实现排序，每一轮将最大（或最小）的元素移动到数组末尾（或开头）。 选择排序（Selection Sort）：每次从未排序的部分选择最小（或最大）的元素放到已排序部分的末尾（或开头）。 插入排序（Insertion Sort）：将未排序的元素逐个插入到已排序部分的合适位置，直到所有元素都有序。 快速排序（Quick Sort）：通过一次排序将数组分成两部分，然后分别对两部分递归地进行快速排序。 归并排序（Merge Sort）：将数组不断二分直至最小单元素，然后两两合并有序数组直至整个数组有序。 堆排序（Heap Sort）：利用堆这种数据结构来实现排序，通过建立最大堆或最小堆进行排序。 希尔排序（Shell Sort）：将数组划分成若干个子序列进行插入排序，最终对整个数组进行插入排序。 计数排序（Counting Sort）：统计每个元素的出现次数，然后根据计数结果重建有序序列。 桶排序（Bucket Sort）：将数据按照区间划分为若干个桶，对每个桶中的数据进行排序，最后合并各个桶的数据。
以上列举了常见的几种排序算法，每种算法都有其特点和适用场景，选择合适的排序算法可以提高算法效率。
1、冒泡排序
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。时间复杂度为O(n^2)。
图2. 菜鸟教程
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前数组：");
printArray(arr);
bubbleSort(arr);
System.out.println("\n排序后数组：");
printArray(arr);
}
// 冒泡排序函数
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换arr[j]和arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 打印数组函数
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
}
}
冒泡排序的核心思想是通过相邻元素的比较和交换，逐步将最大（或最小）的元素移动到数组的末尾（或开头）。下面我来解析一下冒泡排序函数每一步的具体操作：
第一轮循环：
比较第一个元素和第二个元素，如果前者大于后者则交换它们；比较第二个元素和第三个元素，同理；依此类推，直到倒数第二个元素和最后一个元素比较完毕。 第二轮循环：
重复上述步骤，但这次最大的元素已经被移动到了数组的末尾，因此不再参与比较。 经过 n-1 轮循环之后，数组中最大（或最小）的元素已经被移动到了正确的位置，剩余元素无需再进行比较。 最终，整个数组按照从小到大（或从大到小）的顺序排列完成。
在冒泡排序算法中，每一轮循环都会将当前未排序部分的最大（或最小）元素“冒泡”到正确的位置，因此称为冒泡排序。虽然冒泡排序算法简单易懂，但其时间复杂度为 O(n^2)，效率较低，不适用于大规模数据的排序。
2、选择排序
选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下：
首先，在未排序序列中找到最小（或最大）的元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（或最大）的元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
唯一的好处可能就是不占用额外的内存空间了吧。
图3. 菜鸟教程
以下是选择排序的Java代码示例：
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前数组：");
printArray(arr);
selectionSort(arr);
System.out.println("\n排序后数组：");
printArray(arr);
}
// 选择排序函数
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将找到的最小元素与当前位置交换
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 打印数组函数
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
}
}
选择排序的核心思想是每次遍历未排序部分，找到最小元素的索引，然后将其与未排序部分的第一个元素交换位置，这样经过 n-1 次遍历后，整个数组就会有序。选择排序的时间复杂度也是 O(n^2)，因此效率较低，不适用于大规模数据的排序。
3、插入排序
插入排序如同斗地主一般，拿到牌依序整理好。
插入排序（Insertion Sort）是一种简单且直观的排序算法。它的工作原理如下：
将数组分为已排序部分和未排序部分，初始时已排序部分只包含第一个元素，未排序部分包含剩余元素。 依次将未排序部分的元素插入到已排序部分的合适位置，直到所有元素都被插入到已排序部分。
以下是插入排序的示例代码（使用Java实现）：
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前数组：");
printArray(arr);
insertionSort(arr);
System.out.println("\n排序后数组：");
printArray(arr);
}
// 插入排序函数
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 打印数组函数
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
}
}
在插入排序算法中，我们从第二个元素开始遍历未排序部分，将当前元素插入到已排序部分的合适位置。
具体步骤为：将当前元素与已排序部分中的元素逐个比较并向右移动，直到找到合适的插入位置。插入排序的时间复杂度也是O(n^2)，但在实际应用中，对小规模数据或部分有序的数据进行排序时，插入排序的性能是非常不错的。
4、希尔排序
希尔排序（Shell Sort）是一种改进自插入排序的排序算法，也被称为“缩小增量排序”。希尔排序的基本思想是将待排序的数组划分为若干个子序列，对各个子序列进行插入排序，通过逐渐减小步长（增量），最终实现整个数组的排序。
以下是使用Java编写的希尔排序算法示例代码：
public class ShellSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前数组：");
printArray(arr);
shellSort(arr);
System.out.println("\n排序后数组：");
printArray(arr);
}
// 希尔排序函数
public static void shellSort(int[] arr) {
int n = arr.length;
// 使用希尔增量gap，初始化为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子序列进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i]; //将当前元素的值存储到临时变量 temp
int j = i; //用变量 j 记录当前位置
// 将当前元素插入到所属子序列的正确位置上
/**
* while 循环，将当前元素与前面相隔 gap 个位置的元素进行比较
* 1、如果前面的元素比当前元素大，则将前面的元素向后移动 gap 个位置
* 2、直到找到合适的位置将当前元素插入进去
*/
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
//将当前元素的值存储到 arr[j] 的位置上，这样当前子序列的前 i+1 个元素就变得更加有序了
arr[j] = temp;
}
}
}
// 打印数组函数
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
}
}
在这段代码中，我们定义了一个ShellSort类，其中包含了希尔排序算法的实现。通过调用shellSort方法对输入数组进行排序，并通过printArray方法打印排序前和排序后的数组。
具体来说，该算法使用一个变量 gap 来表示子序列的间隔，每一轮排序结束后将 gap 缩小一半。
在每个子序列中，从第 gap 个元素开始，依次与前面的元素进行比较，如果该元素比前面的元素小，则将前面的元素后移一个位置，直到找到合适的位置将该元素插入进去。最后在子序列中将其余元素依次向后移动并插入到合适的位置上，以保证整个子序列的有序。
希尔排序的核心思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。通过不断减小步长，最终实现整个数组的排序。希尔排序的时间复杂度取决于步长序列的选择，一般为 O(n log^2 n)。
5、归并排序
归并排序是一种经典的分治算法，它通过将待排序的数组不断地分割成更小的数组，直到无法再分割为止，然后再将这些小数组按顺序合并起来。
下面是归并排序的基本思路：
分割（Divide）：将数组不断地对半分割，直到每个子数组中只有一个元素为止。 合并（Merge）：将两个已经排好序的子数组合并成一个大的有序数组，同时保持整体有序。 重复上述两个步骤，直到所有的子数组都合并为一个完整的数组。
归并排序通常通过递归的方式来实现。具体来说，可以分为以下几个步骤：
递归分割：将原始数组递归地对半分割，直到每个子数组只有一个元素为止。 合并操作：将两个有序的子数组合并成一个更大的有序数组。
下面是Java语言实现的归并排序示例代码：
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
public static void main(String[] args) {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
System.out.println("Before sorting: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，mergeSort 方法用于递归地分割和合并数组，而 merge 方法则用于合并两个有序的子数组。最后，我们在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
6、快速排序
快速排序（Quick Sort）是一种常见且高效的排序算法，它通过选择一个基准元素，将数组分割成两部分，然后对这两部分分别进行递归排序来实现排序。下面是快速排序的基本思路：
选择基准元素：从数组中选择一个基准元素（通常选择第一个元素），将数组分为两部分，一部分包含比基准元素小的元素，另一部分包含比基准元素大的元素。 分区操作：重新排列数组，使得比基准元素小的元素位于基准元素的左边，比基准元素大的元素位于基准元素的右边，基准元素位于最终排序位置上。 递归排序：对基准元素左右两部分分别进行递归排序。
下面是一个简单的快速排序的Java代码示例：
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before sorting: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，quickSort 方法用于递归地对数组进行快速排序，partition 方法用于进行分区操作，将数组重新排列。最后在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
7、堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
堆排序分为两个主要步骤：建堆和排序。
建堆：将待排序的数组看作一个完全二叉树，根据堆的性质，从最后一个非叶子节点开始，逐个向上调整节点，保持堆的性质。这样就得到了一个堆。 排序：将堆顶元素与最后一个元素交换，然后将剩余元素重新构建成一个堆。重复这个过程，直到堆为空或者只剩下一个元素。每次交换后，堆中最大的元素都会被放置在数组的末尾。
下面是一个简单的堆排序的Java代码示例：
import java.util.Arrays;
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before sorting: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，heapSort 方法用于进行堆排序，heapify 方法用于调整堆的性质。最后在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
8、计数排序
计数排序（Counting Sort）是一种非比较排序算法，它通过统计数组中每个元素出现的次数，然后根据元素的值将其放回到正确的位置上实现排序。
计数排序的基本思想是利用额外的辅助数组来记录每个元素出现的次数，然后根据这些计数信息将元素放回原数组中。
下面是计数排序的基本步骤：
找出待排序数组中的最大值：遍历整个数组，找到数组中的最大值。 初始化计数数组：创建一个计数数组，大小为最大值加一，用于记录每个元素出现的次数。 统计每个元素出现的次数：遍历待排序数组，统计每个元素出现的次数并存储在计数数组中。 累加次数：对计数数组进行累加操作，使得每个元素表示小于等于该元素值的元素个数。 排序：倒序遍历待排序数组，根据计数数组中的信息将元素放回到正确的位置上。
下面是一个简单的计数排序的Java代码示例：
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] arr) {
int n = arr.length;
if (n == 0) {
return;
}
// 找出最大值
int max = Arrays.stream(arr).max().getAsInt();
// 初始化计数数组
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int num : arr) {
count[num]++;
}
// 累加次数
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 排序
int[] result = new int[n];
for (int i = n - 1; i >= 0; i--) {
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 将结果拷贝回原数组
System.arraycopy(result, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Before sorting: " + Arrays.toString(arr));
countingSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，countingSort 方法用于进行计数排序，根据上述步骤实现排序过程。最后在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
9、桶排序
桶排序（Bucket Sort）是一种分布式排序算法，它将待排序的元素分到不同的桶中，每个桶内的元素再进行单独的排序（可以使用其他排序算法或递归地使用桶排序），最后将各个桶中的元素合并起来得到有序的结果。桶排序适用于输入数据的范围已知且较为均匀分布的情况。
下面是桶排序的基本步骤：
确定桶的数量：根据待排序数组的范围和数据分布情况，确定需要的桶的数量。 分配元素到桶中：遍历待排序数组，根据元素的值将元素分配到对应的桶中。 对每个桶中的元素进行排序：对每个非空的桶中的元素进行排序。可以使用其他排序算法（如插入排序、快速排序等）或者递归地使用桶排序。 合并桶中的元素：按照桶的顺序，将各个桶中的元素按顺序合并起来，得到最终的排序结果。
下面是一个简单的桶排序的Java代码示例：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class BucketSort {
public static void bucketSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
// 确定桶的数量
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int bucketCount = (max - min) / n + 1;
// 创建桶
ArrayList
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 分配元素到桶中
for (int num : arr) {
int index = (num - min) / n;
buckets.get(index).add(num);
}
// 对每个桶中的元素进行排序
for (ArrayList
Collections.sort(bucket);
}
// 合并桶中的元素
int index = 0;
for (ArrayList
for (int num : bucket) {
arr[index++] = num;
}
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 5, 1, 6, 3};
System.out.println("Before sorting: " + Arrays.toString(arr));
bucketSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，bucketSort 方法用于进行桶排序，根据上述步骤实现排序过程。最后在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
10、基数排序
基数排序（Radix Sort）是一种非比较排序算法，它将整数按照位数进行排序。
基数排序的基本思想是从最低有效位（最右边）到最高有效位（最左边）依次对数字进行排序，直到所有位都排完为止。基数排序可以采用 LSD（Least Significant Digit）或 MSD（Most Significant Digit）两种方式进行排序。
下面是基数排序（LSD）的基本步骤：
确定排序的位数：首先确定待排序的整数中最大位数，以确定排序的轮数。 按照每一位进行排序：从最低有效位开始，依次对每一位进行计数排序（或桶排序），根据当前位的值将数字分配到对应的桶中。 合并桶中的元素：按照桶的顺序以及数字在桶中的顺序，将所有元素依次取出合并成一个有序序列。 重复上述步骤：根据整数的位数，重复进行位数次排序，直到所有位都排完为止。
LSD 基数排序动图演示
下面是一个简单的基数排序（LSD）的Java代码示例：
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
// 找出最大值
int max = Arrays.stream(arr).max().getAsInt();
// 计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 统计每个数字出现的次数
for (int num : arr) {
count[(num / exp) % 10]++;
}
// 累加次数
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 排序
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将结果拷贝回原数组
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Before sorting: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在这段代码中，radixSort 方法用于进行基数排序，通过 LSD 的方式实现排序过程。在每轮排序中调用 countingSort 方法对当前位进行计数排序。最后在 main 方法中测试代码的正确性，输出排序前和排序后的数组。
文章来源
发表评论