本文主要讲述：实现数组和集合排序的工具类。

其中，1和2都是使用random生成伪随机数，以当前纳秒时间作为种子数，多线程高并发场景下存在性能问题，可以使用3ThreadLocalRandom来替代；当对安全性要求比较高时，可以使用SecureRandom，其会收集随机事件作为随机种子，是真正意义上的随机。另外，5和6纯属娱乐，大家可以讨论下这两种方式可不可行。

一、数组排序

• 1、冒泡排序

冒泡排序的逻辑是：从第一个元素开始，两两比较，将大数后移，这样第一轮拿到最大数，第二轮拿到第二大，以此类推

public static int[] maopaoSort(int[] arr) {
		for (int j = 0; j < arr.length - 1; j++) {
			for (int i = 0; i < arr.length - 1 - j; i++) {
				if (arr[i] > arr[i + 1]) {
					int mid = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = mid;
				}
			}
		}
		return arr;
	}

• 2、选择排序

选择排序的逻辑与冒泡排序相反，从第一个元素开始，依次与后边的元素进行比较，小的放前面，这样第一轮拿到最小数，第二轮拿到第二小，以此类推

public static int[] selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int mid = arr[i];
                    arr[i] = arr[j];
                    arr[j] = mid;
                }
            }
        }
        return arr;
    }

• 3、快速排序

快速排序的逻辑，我理解是冒泡排序和选择排序的折中排序法，找一个基准点，将数组中小于基准点的数放在左侧，反之放右侧，这样形成了两个分区，对两个分区执行同样操作，一直到每个分区只有一个元素

public static int[] quickSort(int[] arr, int start, int ends) {
		if (start < ends) {
			int index = getIndex(arr, start, ends);
			quickSort(arr, start, index - 1);
			quickSort(arr, index + 1, arr.length - 1);
		}
		return arr;
	}

	private static int getIndex(int[] arr, int start, int ends) {
		int i = start;
		int j = ends;
		int s = arr[i];
		while (i < j) {
			while (i < j && arr[j] >= s) {
				j--;
			}
			if (i < j) {
				arr[i] = arr[j];
				i++;
			}
			while (i < j && arr[i] < s) {
				i++;
			}
			if (i < j) {
				arr[j] = arr[i];
				j--;
			}
		}
		arr[j] = s;
		return i;
	}	

• 4、插入排序

将数组的第一个元素看作是一个有序数组，从第二个元素开始，将其与前面有序元素从左往右依次进行比较，当小于等于某一元素时将其插入，保证插入后也是有序的，依次将数组所有元素插入

个人觉得插入排序是最好理解的一种排序方法

public static int[] insertSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[i] < arr[j]) {
					int mid = arr[i];
					arr[i] = arr[j];
					arr[j] = mid;
				}
			}
		}
		return arr;
	}

• 5、归并排序

将一个右n个元素的数组拆成一个个单独的元素，这些单独的元素都可以认为是有序的，将这些单独的元素两个一组合并成n/2个有序数组，再将这n/2个有序数组合并成n/4个有序数组，最终得到长度为n的一个有序数组

public static void mergeSort(int[] a, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(a, start, mid);
			mergeSort(a, mid + 1, end);
			merge(a, start, mid, end);
		}
	}

	private static void merge(int[] a, int left, int mid, int right) {
		int[] tmp = new int[a.length];
		int p1 = left, p2 = mid + 1, k = left;
		while (p1 <= mid && p2 <= right) {
			if (a[p1] <= a[p2])
				tmp[k++] = a[p1++];
			else if (a[p1] > a[p2])
				tmp[k++] = a[p2++];
		}
		while (p1 <= mid) tmp[k++] = a[p1++];
		while (p2 <= right) tmp[k++] = a[p2++];
		for (int i = left; i <= right; i++) {
			a[i] = tmp[i];
		}
	}

二、集合排序

我们都知道，ArrayList是有序的，因此这里的集合只针对List<Map>进行排序

针对List<Integer>：

• 1、ArrayList是有序集合，可以实现排序
• 2、Collections.sort(list);

针对List<Map>：

• 1、使用list.stream().sorted

public static List<Map> listSort(List<Map> list, String sortKey) {
		List<Map> sortList = list.stream().sorted((o1, o2) -> {
			int value1 = (int)o1.get(sortKey);
			int value2 = (int)o2.get(sortKey);
			if (value1 > value2){
				return 1;
			} else if (value1 < value2){
				return -1;
			}
			return 0;
		}).collect(Collectors.toList());
		return sortList;
	}

• 2.Collections.sort()实现排序
• 其实是使用了匿名内部类Comparator

public static List<Map> listSort(List<Map> list, String sortKey) {
		Collections.sort(list, new Comparator<Map>() {
			@Override
			public int compare(Map map1, Map map2) {
				return (int)map1.get(sortKey) - (int)map2.get(sortKey);
			}
		});
		return list;
	}

本文仅供个人记录，如有任何问题可在评论区提问，欢迎大家交流。