数组的算法
常见排序算法主要有：冒泡排序，选择排序，计数排序，基数排序，堆排序，桶排序，归并排序，希尔排序，插入排序，快速排序等等。
-
冒泡排序（Bubble Sort)：
-
两个for 循环（外面的遍历数组，数组最后个元素不用遍历，因为要两两比较。里面的进行两两比较）
-
通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。
-
时间复杂度：平均和最坏情况都是O(n^2)。
-
for (int i = 0; i < arr.length - 1; i++) {//内层循环控制元素交换即冒泡，一般为数组长度减外层循环变量减1
for (int j = 0; j < arr.length - 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;//
}
}
// 如果在这一轮排序中没有交换过，说明数组已经有序
}
}
口诀：
-
冒泡排序要知道，
-
内外循环两层套，
-
外环数组遍历到，
-
内环边界计算好，
-
左右元素判大小，
-
临时变量交换要；
- 选择排序（Selection Sort）：
- 每次从待排序的数据中选出最小（或最大）的元素，存放在序列的起始位置。
- 时间复杂度：O(n^2)。
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;
}
}
// 交换最小元素到当前位置
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
- 插入排序（Insertion Sort）：
- 构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 时间复杂度：平均O(n^2)，但最好情况是O(n)。
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// 将 arr[i] 插入到已排序序列中
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
- 快速排序（Quick Sort）：
- 通过一个基准值分割数组，然后递归地在分割后的子数组上重复这个过程。
- 时间复杂度：平均O(n log n)，最坏情况O(n^2)。
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
- 归并排序（Merge Sort）：
- 将数组分成两半，分别排序，然后合并。
- 时间复杂度：O(n log n)。
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
// Find the middle point
int m = (l + r) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void merge(int[] arr, int l, int m, int r) {
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temp arrays
System.arraycopy(arr, l, L, 0, n1);
System.arraycopy(arr, m + 1, R, 0, n2);
// Merge the temp arrays
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
- 堆排序（Heap Sort）：
- 使用二叉堆数据结构所设计的排序算法，分为建堆和排序两个阶段。
- 时间复杂度：O(n log n)。
Java标准库中已经提供了高效的排序方法，如Arrays.sort()，大多数情况下使用这些内置方法比手动实现排序算法更高效、更可靠。内置方法通常使用优化过的算法，如TimSort（一种结合了插入排序和归并排序的算法）。