快速排序quickSort

package com.moonlight.algorithm.sort;

import com.google.common.collect.Lists;

import java.util.Collections;
import java.util.List;

/**
 * 手写快速排序
 * 时间复杂度 O(nlog n)
 * 也是存在跳跃性的交换，所以也不是稳定的
 * 综合性能最好（需要诸多的优化）
 * 在小数组的时候，没有优势
 */
public class QuickSort {

	public static void main(String[] args) {
		// List.of 构造的集合是不可变的
//		var arr = List.of(6, 34, 5, 9, 3, 88, 99, 37);
		var arr = Lists.newArrayList(6, 34, 5, 9, 3, 88, 99, 37);
		var right = arr.size() - 1;
		quickSort(arr, 0, right);
		System.out.println(arr);
	}

	public static void quickSort(List<Integer> arr, int left, int right) {
		int index;
		if (left < right) {
			index = partition(arr, left, right);
			quickSort(arr, left, index - 1);
			quickSort(arr, index + 1, right);

		}

	}

	public static int partition(List<Integer> arr, int left, int right) {
		int key = arr.get(left);
		while (left < right) {
			while (arr.get(right) > key && right > left) {
				right--;
			}
			while (arr.get(left) < key && left < right) {
				left++;
			}
			Collections.swap(arr, left, right);
		}
		return left;

	}
}

归并排序mergeSort

package com.moonlight.algorithm.sort;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 手写归并排序
 * 空间换时间的方式，先把小的地方排序之后， 然后合并到一起，那么这个合并的过程就是它的精髓了
 * 归并排序的时间复杂度为 O(nlog n)
 * 特性就是稳定、占用内存、效率高
 */
public class MergeSort {

	public static void main(String[] args) {
		// List.of 构造的集合是不可变的
//		var arr = List.of(6, 34, 5, 9, 3, 88, 99, 37);
		var arr = new int[]{6, 34, 5, 37, 9, 3, 88, 99, 37, 56, 555};
		var right = arr.length - 1;
		mergeSort(arr, 0, right);
		Arrays.stream(arr).forEach(System.out::println);
	}

	public static void mergeSort(int[] arr, int left, int right) {
		if (left >= right) {
			return;
		}
		var mid = left + (right - left) / 2;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);

		mainSort(arr, left, mid, right);
	}

	// 这里是核心逻辑，将arr[left...mid],和arr[mid+1...right] 两个数组的元素进行合并
	public static void mainSort(int[] arr, int left, int mid, int right) {
		var aux = new int[right - left + 1];
		// 创建一个辅助元素数组
		for (var i = left; i <= right; i++) {
			aux[i - left] = arr[i];
		}
		var i = left;
		var j = mid + 1;
		for (int k = left; k <= right; k++) {
			if (j > right) {
				arr[k] = aux[i-left];
				i++;
			} else if (i > mid) {
				arr[k] = aux[j-left];
				j++;
			} else if (aux[i-left] < aux[j-left]) {
				arr[k] = aux[i-left];
				i++;
			} else {
				arr[k] = aux[j-left];
				j++;
			}
		}

	}
}

堆排序

package com.moonlight.algorithm.sort;

import java.util.Arrays;

import static cn.hutool.core.util.ArrayUtil.swap;


/**
 * 手写堆排序
 * 优劣分析：
 * 时间复杂度为O(nlog n)，树的高度为log 2 n,需要的是n-1 次的排序操作
 * 空间复杂度低
 * 由于是跳跃性的排序方式，所以不是稳定的排序
 * 由于需要初始化大顶堆，所以不适用于数据量小的情况
 */
public class HeapSort {

	public static void main(String[] args) {
		// List.of 构造的集合是不可变的
		var arr = new int[]{6, 34, 5, 37, 9, 3, 88, 99, 37, 56, 555, 444};
		heapSort(arr);
		Arrays.stream(arr).forEach(System.out::println);
	}

	public static void heapSort(int[] arr) {

		buildMaxHeap(arr);
		var len = arr.length;
		for (int i = len - 1; i > 0; i--) {
			swap(arr, 0, i);
			len--;
			heapify(arr, 0, len);
		}

	}

	/**
	 * 将整个数住初始化为一个大顶堆
	 * @param arr
	 */
	private static void buildMaxHeap(int[] arr) {
		for (int i = arr.length / 2; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
	}

	/**
	 * 这里采用了递归的方式来处理重建堆
	 * @param arr 待排序数组
	 * @param start 起始排序的根节点
	 * @param len 尚未排序的数组的长度
	 */
	private static void heapify(int[] arr, int start, int len) {
		var left = start * 2 + 1;
		var right = start * 2 + 2;
		var largest = start;

		if (left < len && arr[left] > arr[largest]) {
			largest = left;
		}

		if (right < len && arr[right] > arr[largest]) {
			largest = right;
		}

		if (start != largest) {
			swap(arr, start, largest);
			heapify(arr, largest, len);
		}
	}

}

三种进阶排序算法的比较