排序算法是计算机科学中的一个基本问题,它涉及到将一组数据元素(如整数、浮点数、字符串等)按照某种顺序(如升序或降序)进行排列。以下是您提到的几种排序算法的概念和相应的Java实现:
1. 冒泡排序(Bubble Sort)
概念:
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
Java实现:
public 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; | |
} | |
} | |
} | |
} |
2. 选择排序(Selection Sort)
概念:
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
Java实现:
public 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; | |
} | |
} | |
// 交换 arr[i] 和 arr[minIndex] | |
int temp = arr[i]; | |
arr[i] = arr[minIndex]; | |
arr[minIndex] = temp; | |
} | |
} |
3. 插入排序(Insertion Sort)
概念:
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
Java实现:
public void insertionSort(int[] arr) { | |
int n = arr.length; | |
for (int i = 1; i < n; i++) { | |
int key = arr[i]; | |
int j = i - 1; | |
// 将大于key的元素向后移动 | |
while (j >= 0 && arr[j] > key) { | |
arr[j + 1] = arr[j]; | |
j = j - 1; | |
} | |
arr[j + 1] = key; | |
} | |
} |
4. Shell排序(Shell Sort)
概念:
Shell排序是插入排序的一种更高效的改进版本,也称为缩小增量排序。它是先将整个待排序的记录序列分割成为若干子序列(由相隔某个“增量”的记录组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
Java实现(这里使用了简单的增量序列:n/2, n/4, ... 1):
public void shellSort(int[] arr) { | |
int n = arr.length; | |
for (int gap = n / 2; gap > 0; gap /= 2) { | |
for (int i = gap; i < n; i++) { | |
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; | |
} | |
} | |
} |
5. 快速排序(Quick Sort)
概念:
快速排序是一种分而治之的排序算法。通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
Java实现:
public void quickSort(int[] arr, int low, int high) { | |
if (low < high) { | |
// pi是分区点,arr[pi]已经在正确的位置 | |
int pi = partition(arr, low, high); | |
// 分别对分区点两边进行递归排序 | |
quickSort(arr, low, pi - 1); | |
quickSort(arr, pi + 1, high); | |
} | |
} | |
// 分区操作,返回分区点的索引 | |
private int partition(int[] arr, int low, int high) { | |
int pivot = arr[high]; // 选择最右边的元素作为枢轴 | |
int i = low - 1; // 小于枢轴的元素的索引 | |
for (int j = low; j <= high - 1; j++) { | |
// 如果当前元素小于或等于枢轴 | |
if (arr[j] <= pivot) { | |
i++; // 增加i | |
// 交换arr[i]和arr[j] | |
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 void quickSort(int[] arr) { | |
quickSort(arr, 0, arr.length - 1); | |
} |
6. 堆排序(Heap Sort)
概念:
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。
Java实现(这里以最大堆为例):
public 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--) { | |
// 将当前最大的元素arr[0]和arr[i]交换 | |
int temp = arr[0]; | |
arr[0] = arr[i]; | |
arr[i] = temp; | |
// 重新对堆进行调整 | |
heapify(arr, i, 0); | |
} | |
} | |
// 调整堆 | |
private void heapify(int[] arr, int n, int i) { | |
int largest = i; // 初始化largest为根 | |
int left = 2 * i + 1; // 左 = 2*i + 1 | |
int right = 2 * i + 2; // 右 = 2*i + 2 | |
// 如果左子节点大于根 | |
if (left < n && arr[left] > arr[largest]) { | |
largest = left; | |
} | |
// 如果右子节点大于目前最大的 | |
if (right < n && arr[right] > arr[largest]) { | |
largest = right; | |
} | |
// 如果最大元素不是根 | |
if (largest != i) { | |
int swap = arr[i]; | |
arr[i] = arr[largest]; | |
arr[largest] = swap; | |
// 递归调整受影响的子堆 | |
heapify(arr, n, largest); | |
} | |
} |
7. 合并排序(Merge Sort)
概念:
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
Java实现:
public void mergeSort(int[] arr) { | |
if (arr.length > 1) { | |
int mid = arr.length / 2; | |
int[] left = Arrays.copyOfRange(arr, 0, mid); | |
|
); | |
// 递归对左右子数组进行排序 | |
mergeSort(left); | |
mergeSort(right); | |
// 合并两个已排序的子数组 | |
merge(arr, left, right); | |
} | |
} | |
private void merge(int[] arr, int[] left, int[] right) { | |
int i = 0; // 左子数组的索引 | |
int j = 0; // 右子数组的索引 | |
int k = 0; // 合并后数组的索引 | |
// 合并两个数组到arr中 | |
while (i < left.length && j < right.length) { | |
if (left[i] <= right[j]) { | |
arr[k++] = left[i++]; | |
} else { | |
arr[k++] = right[j++]; | |
} | |
} | |
// 如果左子数组还有剩余元素,则将它们复制到arr中 | |
while (i < left.length) { | |
arr[k++] = left[i++]; | |
} | |
// 如果右子数组还有剩余元素,则将它们复制到arr中 | |
while (j < right.length) { | |
arr[k++] = right[j++]; | |
} | |
} | |
// 调用合并排序 | |
public void mergeSort(int[] arr, int low, int high) { | |
if (low < high) { | |
int mid = (low + high) / 2; | |
mergeSort(arr, low, mid); | |
mergeSort(arr, mid + 1, high); | |
merge(arr, low, mid, high); | |
} | |
} | |
// 合并操作的扩展版本,带有low, mid, high三个参数 | |
private void merge(int[] arr, int low, int mid, int high) { | |
int[] temp = new int[high - low + 1]; | |
int i = low; | |
int j = mid + 1; | |
int k = 0; | |
while (i <= mid && j <= high) { | |
if (arr[i] <= arr[j]) { | |
temp[k++] = arr[i++]; | |
} else { | |
temp[k++] = arr[j++]; | |
} | |
} | |
while (i <= mid) { | |
temp[k++] = arr[i++]; | |
} | |
while (j <= high) { | |
temp[k++] = arr[j++]; | |
} | |
// 将temp数组中的元素复制回arr | |
for (i = 0; i < temp.length; i++) { | |
arr[low + i] = temp[i]; | |
} | |
} |
注意:在上面的mergeSort
函数中,我提供了两个版本。第一个版本假设整个数组都需要排序,并自动找到中点。第二个版本允许你指定要排序的数组范围(通过low
和high
参数),这通常在你需要对数组的一部分进行排序时很有用。同时,我也提供了带有low
, mid
, high
参数的merge
函数版本,这是为了在递归调用mergeSort
时能够正确地合并子数组。