Java实现的十种经典排序算法详解

资源摘要信息:"常用的十种Java排序算法实现" 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 实现方法（伪代码）: ``` public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换两个元素的位置 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } ``` 插入排序（Insertion Sort） 插入排序的工作方式像许多人排序一副扑克牌。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 实现方法（伪代码）: ``` public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int j = i; int current = arr[i]; while (j > 0 && arr[j - 1] > current) { arr[j] = arr[j - 1]; j--; } arr[j] = current; } } ``` 选择排序（Selection Sort） 选择排序是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。选择排序每次从未排序序列中选取最小（或最大）的一个元素，存放到排序序列的起始位置，直到全部待排序的数据元素排完。 实现方法（伪代码）: ``` public static void selectionSort(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; } } } ``` 快速排序（Quick Sort） 快速排序是对冒泡排序的一种改进。它的基本思想是：选择一个基准值，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 实现方法（伪代码）: ``` 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; } ``` 归并排序（Merge Sort） 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 实现方法（伪代码）: ``` public static void mergeSort(int[] arr, int[] temp, int leftStart, int rightEnd) { if (leftStart >= rightEnd) { return; } int middle = (leftStart + rightEnd) / 2; mergeSort(arr, temp, leftStart, middle); mergeSort(arr, temp, middle + 1, rightEnd); mergeHalves(arr, temp, leftStart, rightEnd); } private static void mergeHalves(int[] arr, int[] temp, int leftStart, int rightEnd) { int leftEnd = (rightEnd + leftStart) / 2; int rightStart = leftEnd + 1; int size = rightEnd - leftStart + 1; int left = leftStart; int right = rightStart; int index = leftStart; while (left <= leftEnd && right <= rightEnd) { if (arr[left] <= arr[right]) { temp[index] = arr[left]; left++; } else { temp[index] = arr[right]; right++; } index++; } System.arraycopy(arr, left, temp, index, leftEnd - left + 1); System.arraycopy(arr, right, temp, index, rightEnd - right + 1); System.arraycopy(temp, leftStart, arr, leftStart, size); } ``` 堆排序（Heap Sort） 堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 实现方法（伪代码）: ``` public static void heapSort(int[] arr) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap private static void heapify(int[] arr, int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) { largest = l; } // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) { largest = r; } // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } ``` 计数排序（Counting Sort） 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 实现方法（伪代码）: ``` public static void countingSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int range = max - min + 1; int[] count = new int[range]; int[] output = new int[arr.length]; // Store the count of each object for (int i = 0; i < arr.length; i++) { count[arr[i] - min]++; } // Change count[i] so that count[i] now contains actual // position of this object in output array for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } // Build the output array for (int i = arr.length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current output for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; } } ``` 桶排序（Bucket Sort） 桶排序是计数排序的升级版。它利用了函数的映射关系，是非比较排序算法，时间复杂度为O(n+k)，空间复杂度也为O(n+k)，其性能优于传统的比较排序。桶排序是计数排序的升级版。它利用了函数的映射关系，是非比较排序算法，时间复杂度为O(n+k)，空间复杂度也为O(n+k)，其性能优于传统的比较排序。 实现方法（伪代码）: ``` public static void bucketSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int bucketRange = 5; // 5 buckets used int bucketCount = (max - min) / bucketRange + 1; // Create empty buckets List<List<Integer>> buckets = new ArrayList<>(bucketCount); for (int i = 0; i < bucketCount; i++) { buckets.add(new ArrayList<>()); } // Place each element in the corresponding bucket for (int i = 0; i < arr.length; i++) { int bucketIndex = (arr[i] - min) / bucketRange; buckets.get(bucketIndex).add(arr[i]); } // Sort individual buckets using insertion sort for (List<Integer> bucket : buckets) { insertionSort(bucket); } // Concatenate all buckets into arr[] int arrIndex = 0; for (List<Integer> bucket : buckets) { for (int value : bucket) { arr[arrIndex++] = value; } } } ``` 基数排序（Radix Sort） 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表示字符串（如名字或日期）和特定格式的浮点数，基数排序也不是只能用于整数。 实现方法（伪代码）: ``` public static void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) { countSort(arr, exp); } } // A function to do counting sort of arr[] according to the digit represented by exp. private static void countSort(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; // output array int i, count[] = new int[10]; Arrays.fill(count, 0); // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains the actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to the current digit for (i = 0; i < n; i++) arr[i] = output[i]; } ``` 希尔排序（Shell Sort） 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序的核心在于间隔序列的设定。首先一定不要把希尔排序与插入排序混淆，希尔排序的实质就是分组插入排序。 实现方法（伪代码）: ``` public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } ``` 以上就是Java中常用的十种排序算法的简要介绍和实现方法。通过这些算法的使用可以高效地对数据进行排序。