一、冒泡排序
冒泡排序是最简单的排序算法之一,其基本思想是通过不断交换相邻的元素将最大(或最小)的元素逐渐“浮”到数列的最后。具体步骤如下:
public static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }
冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1)。
二、选择排序
选择排序是一种简单直观、易于实现的排序方法,其基本思想是从待排序的数据中选择最小(或最大)的一个元素,存放到序列的起始位置,然后再从剩余的未排序元素中继续寻找最小(或最大)的元素,放到已排序序列的末尾。具体步骤如下:
public static void selectionSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { int minIdx = i; for (int j = i + 1; j < len; j++) { if (arr[minIdx] > arr[j]) { minIdx = j; } } int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } }
选择排序的时间复杂度为O(n^2),空间复杂度为O(1)。
三、插入排序
插入排序是一种简单直观、稳定性高的排序方法,其基本思想是将待排序的数列分成已排序和未排序两部分,每次从未排序的数列中取一个元素,依次插入到已排序数列中的适当位置。具体步骤如下:
public static void insertionSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int tmp = arr[i]; int j; for (j = i; j > 0 && arr[j - 1] > tmp; j--) { arr[j] = arr[j - 1]; } arr[j] = tmp; } }
插入排序的时间复杂度为O(n^2),空间复杂度为O(1)。
四、快速排序
快速排序是一种运算复杂度平均且效率较高的排序算法,其基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
public static void quickSort(int[] arr, int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } } public static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) { j--; } if (i < j) { arr[i++] = arr[j]; } while (i < j && arr[i] <= pivot) { i++; } if (i < j) { arr[j--] = arr[i]; } } arr[i] = pivot; return i; }
快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn)。
五、归并排序
归并排序是一种稳定的排序算法,其基本思想是将数列划分成若干个小数列,分别排序后再合并。具体步骤如下:
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 len = right - left + 1; int[] tmp = new int[len]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= right) { tmp[k++] = arr[j++]; } for (int t = 0; t < len; t++) { arr[left + t] = tmp[t]; } }
归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。
六、堆排序
堆排序是一种高效的排序算法,其基本思想是将待排序序列建成一个大根堆(或小根堆),此时整个序列的最大值(或最小值)即为堆顶元素,将它移走(放到数组末尾),然后将剩余的n-1个序列重新建成一个堆,如此反复执行直到整个序列有序。具体步骤如下:
public static void heapSort(int[] arr) { int len = arr.length; for (int i = len / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, len); } for (int i = len - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; adjustHeap(arr, 0, i); } } public static void adjustHeap(int[] arr, int i, int len) { int tmp = arr[i]; for (int j = 2 * i + 1; j < len; j = 2 * j + 1) { if (j + 1 < len && arr[j] < arr[j + 1]) { j++; } if (arr[j] > tmp) { arr[i] = arr[j]; i = j; } else { break; } } arr[i] = tmp; }
堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)。
总结
不同的排序算法有不同的优缺点,根据具体的情况选择合适的排序算法可以提高程序的效率和性能。本文介绍的是Java中常用的六种排序算法,分别是冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,理解和掌握这些算法的基本思想和实现方法,可以为我们解决实际问题提供参考和借鉴。