Java 经典排序算法代码 + 注释分析（冒泡、选择、插入、希尔、快排、计数、堆排、归并）
以下是八种经典排序算法的代码，Java8亲测可用，可以直接运行
import java.util.Arrays;
public class Sort {
private static final int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
public static void main(String[] args) {
int num = 7;
switch (num) {
case 0:
bubbleSort();
case 1:
selectionSort();
case 2:
insertionSort();
case 3:
shellSort();
case 4:
quickSort(0, nums.length - 1);
case 5:
countSort();
case 6:
heapSort();
case 7:
mergeSort();
}
}
/**
* 冒泡排序
* <p>
* 稳定性：稳定
* <p>
* 时间复杂度：最佳：O(n)，最差：O(n^2)，平均：O(n^2)
* <p>
* 空间复杂度：O(1)
*/
private static void bubbleSort() {
for (int i = 1; i < nums.length; i++) {
boolean flag = true;
for (int j = 0; j < nums.length - i; j++) {
if (nums[j] > nums[j + 1]) {
nums[j] ^= nums[j + 1];
nums[j + 1] ^= nums[j];
nums[j] ^= nums[j + 1];
flag = false;
}
}
if (flag) {
break;
}
}
System.out.println(Arrays.toString(nums));
}
/**
* 选择排序
* <p>
* 稳定性：不稳定
* <p>
* 时间复杂度：最佳：O(n^2)，最差：O(n^2)，平均：O(n^2)
* <p>
* 空间复杂度：O(1)
*/
private static void selectionSort() {
for (int i = 0; i < nums.length; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
if (minIndex != i) {
nums[i] ^= nums[minIndex];
nums[minIndex] ^= nums[i];
nums[i] ^= nums[minIndex];
}
}
System.out.println(Arrays.toString(nums));
}
/**
* 插入排序
* <p>
* 稳定性：稳定
* <p>
* 时间复杂度：最佳：O(n)，最差：O(n^2)，平均：O(n^2)
* <p>
* 空间复杂度：O(1)
*/
private static void insertionSort() {
for (int i = 1; i < nums.length; i++) {
int preIndex = i - 1;
int current = nums[i];
while (preIndex >= 0 && current < nums[preIndex]) {
nums[preIndex + 1] = nums[preIndex];
preIndex--;
}
nums[preIndex + 1] = current;
}
System.out.println(Arrays.toString(nums));
}
/**
* 希尔排序
* <p>
* 稳定性：不稳定
* <p>
* 时间复杂度：最佳：O(nlogn)，最差：O(n^2)，平均：O(nlogn)
* <p>
* 空间复杂度：O(1)
*/
private static void shellSort() {
int gap = nums.length / 2;
while (gap > 0) {
for (int i = gap; i < nums.length; i++) {
int current = nums[i];
int preIndex = i - gap;
while (preIndex >= 0 && current < nums[preIndex]) {
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = current;
}
gap /= 2;
}
System.out.println(Arrays.toString(nums));
}
/**
* 快速排序
* <p>
* 稳定性：不稳定
* <p>
* 时间复杂度：最佳：O(nlogn)，最差：O(n^2)，平均：O(nlogn)
* <p>
* 空间复杂度：O(logn)
*/
private static void quickSort(int left, int right) {
if (left <= right) {
int middle = partition(left, right);
quickSort(left, middle - 1);
quickSort(middle + 1, right);
}
}
private static int partition(int left, int right) {
int pivot = nums[right];
int pointer = left;
for (int i = left; i <= right - 1; i++) {
if (nums[i] <= pivot) {
int temp = nums[i];
nums[i] = nums[pointer];
nums[pointer] = temp;
pointer++;
}
}
nums[right] = nums[pointer];
nums[pointer] = pivot;
System.out.println(Arrays.toString(nums));
return pointer;
}
/**
* 计数排序
* <p>
* 稳定性：稳定
* <p>
* 时间复杂度：最佳：O(n+k)，最差：O(n+k)，平均：O(n+k)
* <p>
* 空间复杂度：O(k)
*/
private static void countSort() {
int[] MaxMin = findMaxMin();
int max = MaxMin[0];
int min = MaxMin[1];
int[] counts = new int[max - min + 1];
int[] result = new int[nums.length];
//计数
for (int num : nums) {
counts[num - min]++;
}
//累加
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
//排序
for (int i = nums.length - 1; i >= 0; i--) {
result[counts[nums[i] - min] - 1] = nums[i];
counts[nums[i] - min]--;
}
System.out.println(Arrays.toString(result));
}
private static int[] findMaxMin() {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : nums) {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
return new int[]{max, min};
}
/**
* 堆排序
* <p>
* 稳定性：不稳定
* <p>
* 时间复杂度：最佳：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)
* <p>
* 空间复杂度：O(1)
*/
private static void heapSort() {
int index = 0;
//建堆
for (index = (nums.length - 1 - 1) / 2; index >= 0; index--) {
heapify(nums.length, index);
}
//排序
for (int i = nums.length - 1; i > 0; i--) {
int temp = nums[i];
nums[i] = nums[0];
nums[0] = temp;
heapify(i, 0);
}
System.out.println(Arrays.toString(nums));
}
//维护堆的性质
private static void heapify(int length, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < length && nums[left] > nums[largest]) {
largest = left;
}
if (right < length && nums[right] > nums[largest]) {
largest = right;
}
if (largest != index) {
int temp = nums[largest];
nums[largest] = nums[index];
nums[index] = temp;
heapify(length, largest);
}
}
/**
* 归并排序
* <p>
* 稳定性：稳定
* <p>
* 时间复杂度：最佳：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)
* <p>
* 空间复杂度：O(n)
*/
private static void mergeSort() {
//分配一个辅助数组
int[] tempArr = new int[nums.length];
msort(tempArr, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
//归并排序
private static void msort(int[] tempArr, int left, int right) {
//如果只有一个元素，就不需要划分
if (left < right) {
//找中间点
int middle = left + (right - left) / 2;
//划分左半区
msort(tempArr, left, middle);
//划分右半区
msort(tempArr, middle + 1, right);
//合并
merge(tempArr, left, middle, right);
}
}
//合并
private static void merge(int[] tempArr, int left, int middle, int right) {
//左半区第一个元素
int leftPtr = left;
//右半区第一个元素
int rightPtr = middle + 1;
//临时数组元素的下标
int ptr = left;
//合并
while (leftPtr <= middle && rightPtr <= right) {
if (nums[leftPtr] <= nums[rightPtr]) {
tempArr[ptr] = nums[leftPtr];
leftPtr++;
} else {
tempArr[ptr] = nums[rightPtr];
rightPtr++;
}
ptr++;
}
//左边剩下了
while (leftPtr <= middle) {
tempArr[ptr] = nums[leftPtr];
leftPtr++;
ptr++;
}
//右边剩下了
while (rightPtr <= right) {
tempArr[ptr] = nums[rightPtr];
rightPtr++;
ptr++;
}
//复制回原来的数组
while (left <= right) {
nums[left] = tempArr[left];
left++;
}
}
}
标签：堆排,right,Java,nums,int,++,快排,length,left From： https://blog.csdn.net/XRT_knives/article/details/140619451