Java 7大常见排序方法实例详解
排序算法是计算机科学中的重要技能之一,Java为开发者提供了多种常见的排序方法,本文将介绍Java 7大常见排序方法并提供详细的示例说明。
1. 冒泡排序(Bubble Sort)
冒泡排序是最简单的排序算法之一,它的思想是依次比较相邻的两个元素,如果前面的元素比后面的元素大,则交换这两个元素的位置,通过多次比较和交换,将最大的元素不断移到最后面,直到排序完成。下面是用Java实现的冒泡排序算法示例代码:
public void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
示例说明:通过冒泡排序算法对数组进行升序排序,时间复杂度为O(n^2)。
2. 选择排序(Selection Sort)
选择排序是一种简单的排序算法,它的思想是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放到序列的起始位置,然后再从剩余的未排序元素中继续寻找最小(或最大)元素,依次类推,直到全部排序完毕。下面是用Java实现的选择排序算法示例代码:
public void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
示例说明:通过选择排序算法对数组进行升序排序,时间复杂度为O(n^2)。
3. 插入排序(Insertion Sort)
插入排序是一种简单排序算法,它的想法是不断将元素插入到已排序的数据中,初始时认为第一个数是已排序的数据,再把下一个数插入已排序好的数列中,直到插完所有的数为止。下面是用Java实现的插入排序算法示例代码:
public void insertionSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
}
示例说明:通过插入排序算法对数组进行升序排序,时间复杂度为O(n^2)。
4. 希尔排序(Shell Sort)
希尔排序是一种基于插入排序的排序算法,它的思想是将数组划分为若干个小组进行插入排序,通过缩小增量的方式不断缩短排序时间,直到增量为1时,算法结束。下面是用Java实现的希尔排序算法示例代码:
public void shellSort(int[] arr) {
int len = arr.length;
int gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
int j = i;
while (j >= gap && arr[j] < arr[j - gap]) {
int temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
j -= gap;
}
}
gap /= 2;
}
}
示例说明:通过希尔排序算法对数组进行升序排序,时间复杂度为O(n log n)。
5. 归并排序(Merge Sort)
归并排序是一种高效的排序算法,它的思想是将一个数组分成两个子数组,然后将两个子数组排序,最后将排序好的两个子数组合并成一个有序数组。下面是用Java实现的归并排序算法示例代码:
public 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);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[arr.length];
int i = left;
int j = mid + 1;
int 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 < k; p++) {
arr[left + p] = temp[p];
}
}
示例说明:通过归并排序算法对数组进行升序排序,时间复杂度为O(n log n)。
6. 快速排序(Quick Sort)
快速排序是一种高效的排序算法,它的思想是通过一趟排序将待排序列分成独立的两部分,其中左边部分所有元素都小于右边部分的所有元素,然后分别递归左右两部分的元素,直到整个序列有序。下面是用Java实现的快速排序算法示例代码:
public void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
index++;
}
}
int temp = arr[pivot];
arr[pivot] = arr[index - 1];
arr[index - 1] = temp;
return index - 1;
}
示例说明:通过快速排序算法对数组进行升序排序,时间复杂度为O(n log n)。
7. 堆排序(Heap Sort)
堆排序是一种树形选择排序,它的思想是将待排序序列构造成一个堆,堆顶元素是最大或最小元素,然后将堆顶元素与序列末尾元素交换位置,对剩余的序列重新构建堆,依次进行,直到整个序列有序。下面是用Java实现的堆排序算法示例代码:
public void heapSort(int[] arr) {
int len = arr.length;
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(arr, len, i);
}
for (int i = len - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int len, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, len, largest);
}
}
示例说明:通过堆排序算法对数组进行升序排序,时间复杂度为O(n log n)。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java 7大常见排序方法实例详解 - Python技术站