若有不理解,可以问一下这几个免费的AI网站
- https://ai-to.cn/chat
- http://m6z.cn/6b1quh
- http://m6z.cn/6wVAQG
- http://m6z.cn/63vlPw
下面是 Java 实现的十大排序算法的示例代码。涵盖的排序算法包括:冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、计数排序、桶排序和基数排序。
1. 冒泡排序
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. 选择排序
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[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}
3. 插入排序
public void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
4. 归并排序
public void mergeSort(int[] arr) {if (arr.length < 2) return;int mid = arr.length / 2;int[] left = new int[mid];int[] right = new int[arr.length - mid];System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, arr.length - mid);mergeSort(left);mergeSort(right);merge(arr, left, right);
}private void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}while (i < left.length) {arr[k++] = left[i++];}while (j < right.length) {arr[k++] = right[j++];}
}
5. 快速排序
public void quickSort(int[] arr, int low, int high) {if (low < high) {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; j++) {if (arr[j] < pivot) {i++;// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换 arr[i + 1] 和 arr[high]int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}
6. 堆排序
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;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {// 交换 arr[i] 和 arr[largest]int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}
7. 希尔排序
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;}}
}
8. 计数排序
public void countingSort(int[] arr) {int n = arr.length;int max = Arrays.stream(arr).max().getAsInt();int[] count = new int[max + 1];int[] output = new int[n];for (int num : arr) {count[num]++;}for (int i = 1; i <= max; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}System.arraycopy(output, 0, arr, 0, n);
}
9. 桶排序
public void bucketSort(float[] arr) {int n = arr.length;if (n <= 0) return;// 创建 n 个空桶List<List<Float>> buckets = new ArrayList<>();for (int i = 0; i < n; i++) {buckets.add(new ArrayList<>());}// 将数组元素分配到桶中for (float num : arr) {int bucketIndex = (int) (num * n);buckets.get(bucketIndex).add(num);}// 对每个桶进行排序for (List<Float> bucket : buckets) {Collections.sort(bucket);}// 合并桶int index = 0;for (List<Float> bucket : buckets) {for (float num : bucket) {arr[index++] = num;}}
}
10. 基数排序
public void radixSort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}
}private void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}System.arraycopy(output, 0, arr, 0, n);
}
总结
以上代码展示了十种常见的排序算法的实现。你可以将它们放入一个 Java 类中,并根据需要进行调用和测试。每种排序算法在不同情况下的性能和效率各有不同,选择合适的排序算法可以提高程序的性能。