JAVA 排序算法实现：冒泡、选择、插入与快速排序

标题中提到的排序算法是几种常用的排序方法，它们在编程和算法领域中被广泛应用于对数据集进行排序。这四种排序算法分别是冒泡排序、选择排序、插入排序和快速排序，它们各自有其特点和应用场景。以下是对这四种排序方法的详细说明和Java实现代码。 ### 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 **冒泡排序的Java实现代码示例：** ```java public class BubbleSort { public static void bubbleSort(int[] array) { int n = array.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (array[j] > array[j + 1]) { // swap temp and array[i] int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } // 测试代码 public static void main(String args[]) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); System.out.println("Sorted array"); printArray(arr); } public static void printArray(int[] arr) { for (int i=0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } ``` ### 选择排序（Selection Sort） 选择排序算法是一种原址比较排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 **选择排序的Java实现代码示例：** ```java public class SelectionSort { public static void selectionSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int minIdx = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[minIdx]) { minIdx = j; } } int temp = array[minIdx]; array[minIdx] = array[i]; array[i] = temp; } } // 测试代码 public static void main(String args[]) { int[] arr = {64, 25, 12, 22, 11}; selectionSort(arr); System.out.println("Sorted array"); printArray(arr); } public static void printArray(int[] arr) { for (int i=0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } ``` ### 插入排序（Insertion Sort） 插入排序的工作方式类似于我们玩扑克牌时整理手牌的过程。它构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 **插入排序的Java实现代码示例：** ```java public class InsertionSort { public static void insertionSort(int[] array) { int j; for (int p = 1; p < array.length; p++) { int tmp = array[p]; for (j = p; j > 0 && array[j - 1] > tmp; j--) { array[j] = array[j - 1]; } array[j] = tmp; } } // 测试代码 public static void main(String args[]) { int[] arr = {12, 11, 13, 5, 6}; insertionSort(arr); System.out.println("Sorted array"); printArray(arr); } public static void printArray(int[] arr) { for (int i=0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } ``` ### 快速排序（Quick Sort） 快速排序是目前应用最广泛的排序算法之一。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 快速排序使用分治法的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。分治法的基本思想是将一个较大的问题分解为若干个规模较小的同类问题，递归解决这些子问题，然后再合并其结果，达到原问题的解。 **快速排序的Java实现代码示例：** ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } private 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++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } // 测试代码 public static void main(String args[]) { int[] arr = {10, 7, 8, 9, 1, 5}; int n = arr.length; quickSort(arr, 0, n - 1); System.out.println("Sorted array"); printArray(arr); } public static void printArray(int[] arr) { for (int i=0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } ``` 以上四种排序算法，每一种都有其适用的场景。例如，冒泡排序和插入排序在数据量较小或者数据接近排序的情况下表现不错，但不适合大数据量的排序。快速排序适合大数据量的排序，但其性能不稳定，在最坏情况下会退化为O(n^2)。选择排序的交换次数固定，适用于任何情况，但其性能表现一般。 最后，对于文件列表中的“readme.txt”和“sort”文件，由于没有提供具体内容，无法直接生成对应的知识点。但可以推测，“readme.txt”可能会包含关于文件集合的说明和使用指南，而“sort”可能是与排序相关的其他资源或工具。在实际应用中，应根据这些文件的具体内容来判断它们的知识点。