七大排序
本次排序以数组为例，排序数组
一、测试用例
测试后续的排序是否正确排序
1.1 生成待测试的排序数组
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
//根据传入的方法名就可以调用方法，借助反射
public class 生成测试数组 {
//final修饰对象，内容可变引用不可变
public static final ThreadLocalRandom random = ThreadLocalRandom.current();
public static void testSort(String sortName , int[] arr){
Class<七大排序> cls = 七大排序.class;
try {
Method method = cls.getMethod(sortName , int[].class);
Long startTime = System.nanoTime();
method.invoke(null , arr);
Long endTime = System.nanoTime();
if (isSort(arr)){
System.out.println(sortName + "算法共耗时：" + (endTime - startTime) / 1000000 + "ms");
}
} catch (NoSuchMethodException e) {
e.printStackTrace();
} catch (InvocationTargetException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
}
public static boolean isSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]){
System.err.println("没排序好");
return false;
}
}
return true;
}
//生成无序数组
public static int[] disorderArr(int n , int left , int right){//n个元素，范围[left , right)
int[] arr = new int[n];
for (int i = 0; i < arr.length - 1; i++) {
arr[i] = random.nextInt(left , right);
}
return arr;
}
//生成有序数组
public static int[] orderlyArr(int n , int times){//n个元素(0 - n) ， 复杂度（times）即交换times次
int[] arr = new int[n];
for (int i = 0; i < arr.length - 1; i++) {
arr[i] = i;
}
for (int i = 0; i < times; i++) {
int a = random.nextInt(n);//交换的是数组内的值，此时a，b指的依然是索引
int b = random.nextInt(n);
swap(arr , a , b);
}
return arr;
}
public static void swap(int[] arr , int i , int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static int[] copyOf(int[] arr){
int[] arrCopyOf = Arrays.copyOf(arr , arr.length);//复制数组，深拷贝
return arrCopyOf;
}
}
二、七大排序本体
开始了开始了，一起踏上这条打怪升级路咯
2.1 冒泡排序
每一趟确定排序区间中一个位置的元素
热个身，先来个简单的
2.1.1 冒泡排序图示
2.1.2 冒泡排序
/**
* 冒泡排序
* 循环遍历数组，每次确定最后一个位置是未排序区间最大的，有序区间就会相应地减少一个
*/
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//第一个for未排序区间
boolean isSwap = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
//第二个已排序区间
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);//交换数组元素
isSwap = true;
}
}
if (!isSwap) {
//如果这一趟没有发生交换说明后面的每一个元素都没有他前面的这个元素大，所以已经完成排序
break;
}
}
}
2.1.3 冒泡排序理解
- isSwap方法：如果这一趟没有发生交换说明后面的每一个元素都没有他前面的这个元素大，所以已经完成排序，退出即可
- 冒泡排序属于交换排序；时间复杂度：O(n2)；稳定排序算法
2.2 插入排序
来点有操作的
2.2.1 插入排序图示
2.2.2 插入排序
2.2.2.1 直接插入排序
从前往后逐个排查把元素向前寻找到合适位置后插入
/**
* 直接插入排序
*循环数组，每次数组的下一元素插入之前经过的已排序空间
*每次从无序区间取第一个插入有序区间的合适位置
*/
public static void insertionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j >= 1 && arr[j] < arr[j - 1]; j--) {//已排序区间是i之前，i之后取第一个值把他插到排序好的合适位置
swap(arr, j, j - 1);
}
}
}
2.2.2.2 二分优化的直接插入排序
/**
* 直接插入排序二分优化
* 在寻找合适插入位置时用二分法查找
*/
public static void insertionSort(int[] arr) {
//有序区间[0 , i)
//无序[i , n]
for (int i = 1; i < arr.length; i++) {
int val = arr[i];//记录当前位置的索引处的值
int left = 0;//已经排序好的左边界
int right = i;//右边界
/**
while循环：二分查找合适位置，当left=right时就找到了合适位置
*/
while (left < right) {
int mid = left + ((right - left) >> 1);
//这里这个求中值比较灵性，尽量不要mid=(left+right)/2
if (val < arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
//这个for循环就可以使数组待插入位置到当前待排序位置前的值全体后移
for (int j = i; j > left; j--) {
arr[j] = arr[j - 1];
}
//后移完成后使待排序元素归位即插入到while找到的待插入位置
arr[left] = val;
}
}
2.2.3 插入排序理解
- 二分取中值时这样写不会有越界问题
int mid =left + ((right - left) >> 1);尽量不要mid=(left+right)/2 - 直接插入排序时间复杂度：O(n2)；稳定排序
2.3 希尔排序
逐渐加难度了哟
把排序区间分组后，组内进行插入排序
2.3.1 希尔排序图示
2.3.2 希尔排序
2.3.2.1 希尔排序一
//希尔排序，缩小增量排序
//每次取一个gap，将原数组按gap分组，组内插入排序
public static void shellSort(int[] arr) {
int gap = arr.length >> 1;
while (gap > 1) {
//进行分组
insertionSortGap(arr, gap);
gap = gap >> 1;
}
//按分组进行插排
insertionSort(arr);
}
//按分组进行插排
public static void insertionSortGap(int[] arr, int gap) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= 0; j = j - gap) {
swap(arr, j, j - gap);
}
}
}
2.3.2.2 希尔排序二
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
//每次大循环就是在进行分组，每组几个
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
//while和底下的arr[j + step] = temp实现前大于后时的交换操作
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
//不满足while时j是负的是0-step所以j+step表示0完成交换
//并且当前小于后时表示原来的不变很巧妙
arr[j + step] = temp;
}
}
}
2.3.3 希尔排序理解
- 希尔排序也属于插排的一种；时间复杂度大概O(n1.3～1.5);不稳定排序
2.4 归并排序
对待排序区间进行拆分再合并，合并过程中完成排序
在来加点难度
2.4.1 归并排序图示
2.4.2 归并排序
2.4.2.1 归并排序一
private static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
if (r - l <= 15) {
//排序长度小于15时插排效率更高
insertionSort(arr, l, r);
}
int mid = l + ((r - l) >> 1);
//分别进行左右递归拆分分开
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
//因为是一步一步合并上来的，所以只要左右中左边最后一个大于右边第一个时说明没排序好，否则这组已经是有序的
if (arr[mid] > arr[mid + 1]) {
merge(arr, l, mid, r);
}
}
private static void insertionSort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {//从l + 1开始防止索引越界
for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
}
private static void merge(int[] arr, int l, int mid, int r) {
//合并操作，过程中进行排序
int[] aux = new int[r - l + 1];//待合并的新建数组
for (int i = 0; i < aux.length; i++) {
//整个新建aux数组的取值过程仍参考原数组，所以i+l可以保证拆分时、拆出来的右区间在原数组的位置
aux[i] = arr[i + l];
}
int i = l;//记录左区间的左端值
int j = mid + 1；//记录右区间的左端值
for (int k = l; k <= r; k++) {
//分情l，r在不同情况下指的是谁
//重新确定合并数组值，操作基础在原数组上
if (i > mid) {
//左边处理完了，处理右面
arr[k] = aux[j - l];
//可能是右半部分的aux
j++;
} else if (j > r) {
//右边好了，处理左面
arr[k] = aux[i - l];
i++;
} else if (aux[i - l] <= aux[j - l]) {
//待排序的左部分值更小，把左部分值放进去
arr[k] = aux[i - l];
i++;
} else {
//否则右部分的值更小放进去
arr[k] = aux[j - l];
j++;
}
}
}
2.4.2.2 归并排序二
//1、递归分区，对分好的区按范围新建数组作为合并后的数组
public int[] mergeSort(int[] sourceArray) {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
//取好中间值把左右部分继续分别递归分开
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
//分好后对左右部分进行合并，合并时进行排序
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
//归并排序中，并的过程，并的过程中完成排序
int[] result = new int[left.length + right.length];
int i = 0;
//两个区间都存在元素
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
//当左区间的值比右区间小时，更新排序数组result的值，并且更新左区间去掉第一个元素
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
//当右区间的值比左区间小时，更新排序数组result的值，并且更新右区间去掉第一个元素
right = Arrays.copyOfRange(right, 1, right.length);
}
}
//当左右区间只有一个存在元素时
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
2.4.2.3 归并排序三
这个相对不好理解，用两个for循环替换递归拆分的过程
//合并过程是一样的，优化递归拆分的过程
public static void mergeSort(int[] arr) {
for (int i = 1; i < arr.length; i += i) {
//每次合并的子数组的元素个数
for (int j = 0; j + i < arr.length; j += 2 * i) {
//j为每次合并的开始索引
//元素的起始索引是j每个小数组有i个元素，所以i+ j就是第二个数组也就是待合并数组的右端数组的第一个元素，所以i + j - 1 就mid
merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));//j + 2 * i - 1同上思路基本一致
}
}
}
//合并过程是一样的，优化递归拆分的过程
private static void merge(int[] arr, int l, int mid, int r) {
//合并操作，过程中进行排序
int[] aux = new int[r - l + 1];//待合并的新建数组
for (int i = 0; i < aux.length; i++) {
//整个新建aux数组的取值过程仍参考原数组，所以i+l可以保证拆分时、拆出来的右区间在原数组的位置
aux[i] = arr[i + l];
}
int i = l;//记录左区间的左端值
int j = mid + 1；//记录右区间的左端值
for (int k = l; k <= r; k++) {
//分情l，r在不同情况下指的是谁
//重新确定合并数组值，操作基础在原数组上
if (i > mid) {
//左边处理完了，处理右面
arr[k] = aux[j - l];
//可能是右半部分的aux
j++;
} else if (j > r) {
//右边好了，处理左面
arr[k] = aux[i - l];
i++;
} else if (aux[i - l] <= aux[j - l]) {
//待排序的左部分值更小，把左部分值放进去
arr[k] = aux[i - l];
i++;
} else {
//否则右部分的值更小放进去
arr[k] = aux[j - l];
j++;
}
}
}
2.4.3 归并排序理解
- 15以内插排序效率最高可以用插排优化一部分
- copyOfRange（数组[] , a ,b）是左闭右开区间[a , b);
- Math.floor() 向下取整，即小于这个数的最大的那个整数。
- Math.ceil() 向上取整，即大于这个数的最小的那个整数。
- Math.round() 四舍五入
- 一定理解归并时左右区间在哪
- 归并排序是稳定排序；时间复杂度O(nlogn)
2.5 选择排序
看的很头大了吧，那先再来个简单的缓解一下疲劳
遍历无序区间在其中找到最合适的元素与有序区间的边界进行交换
2.5.1 选择排序图示
2.5.2 选择排序
2.5.2.1 单向选择排序
循环遍历数组，i之前是已经排序的，每次从i开始在未排序区间找到最小值与当前位置交换逐个排序，每次从无序区间找到最小值放在无需区间最前端，每经过一轮，一个元素归为，有序加1，无序-1
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
//要取最后一个元素，j是i+1，当i是倒数第二个时
if (arr[j] < arr[min]) {
min = j;
//暂存索引到min，循环完此层时，min就是最小元素的下标
//看清索引下标,索引下标,索引下标
}
}
swap(arr, min, i);
}
}
2.5.2.2 双向选择排序
一次循环同时确定左右即最小值与最大值
public static void selectionSort(int[] arr) {
int low = 0;
int height = arr.length - 1;
while (low <= height) {
int min = low;//初始化不是从最大和最(0或length -1 )开始，从未排序区间找出最大最小，未排序区间，未排序区间
int max = low;
for (int i = low + 1; i <= height; i++) {//在未排序数组中找到最大最小不是全部
if (arr[i] < arr[min]) {
min = i;
}
if (arr[i] > arr[max]) {
max = i;
}
}
swap(arr, min, low);
if (max == low) {
//如果一开始的low位置是最大元素的位置，因为经过了最小值归位的交换运算，所以此时最大值的位置在min索引处交换max与min即可
max = min;
}
swap(arr, max, height);
low += 1;//已经处理过最小的向后移
height -= 1;
}
}
2.5.3 选择排序理解
- 选择排序时间复杂度O(n2)；不稳定排序
2.6 堆排序
现在我宣布正式进入实力操作环节
从第一个非叶子节点开始进行元素下沉操作来构造最大堆，构造好之后在依次交换首尾值进行首元素下沉
2.6.1 堆排序图示
2.6.2 堆排序
从第一个非叶子节点开始进行元素下沉操作来构造最大堆，构造好之后在依次交换首尾值进行首元素下沉
public static void heapSort(int[] arr) {
for (int i = (arr.length - 1 - 1) >> 1; i >= 0; i--) {
//第一个for循环从第一个非叶子结点开始做下沉来构造大根堆
//最后一个节点的父节点就是第一个非叶子结点。详细看后续介绍及开头的必会操作。
siftDown(arr, i, arr.length - 1);
}
for (int i = arr.length - 1; i > 0; i--) {
//从末位遍历元素对每个元素与首元素交换后进行下沉操作。
swap(arr, i, 0);
siftDown(arr, 0, i);
}
}
public static void siftDown(int[] arr, int i, int length) {
//对索引元素i进行下沉操作，下沉范围为length
while (2 * i + 1 < length) {
int j = 2 * i + 1;
if (j + 1 < length && arr[j + 1] > arr[j]) {
//下沉时j + 1 < length,索引必须是小于长度的不能等于，等于就会返回到原来位置这个东西真的很妙
j += 1;
}
if (arr[i] < arr[j]) {
swap(arr, i, j);
i = j;
} else {
break;
}
}
}
2.6.3 堆排序理解
- 堆排序时间复杂度：O(nlogn)，不稳定排序
- 堆的排序会牵扯很多二叉树的知识这些(avl树、红黑树等)后续将添加链接
- 一定注意下沉操作时的下沉范围，每次都是下沉完后会有一个最大元素归位
2.7 快速排序
既然都瞅到这里了那也就不藏了，该放大招了
以一个数为基准，每次把为排序区间分成比这个基准大和比这个基准值小的两个部分，在讲这个基准值放在合适的分界处
2.7.1 快速排序图示
2.7.2 快速排序
准备好兄弟们，纷争开始了
以一个数为基准，每次把为排序区间分成比这个基准大和比这个基准值小的两个部分，再将这个基准值放在合适的分界处
2.7.2.1 单路快排
public static void quickSort(int[] arr) {
partitionHelp(arr, 0, arr.length - 1);
}
private static void partitionHelp(int[] arr, int l, int r) {
if (r - l <= 15) {
insertionSort(arr,l,r);
return;
}//random的范围[l , r]r必须>l
int p = partition(arr, l, r);//以p分区分成下面两种情况；partition方法进行排序的变化操作
partitionHelp(arr, l, p - 1);
partitionHelp(arr, p + 1, r);
}
public static final ThreadLocalRandom random = ThreadLocalRandom.current();
private static int partition(int[] arr, int l, int r) {
int p = random.nextInt(l, r);
swap(arr, l, p);//先把p放到首位
int val = arr[l];//将p的这个随机值赋给val作为基准值
int j = l;//j是比val小的最后一个元素索引，所以j + 1 就是第一个比val 大或等的元素
for (int i = l + 1; i <= r; i++) {
if (arr[i] < val) {
swap(arr, j + 1, i);//变换当前元素位置到比val小的最后索引即第一个比val大的位置
j++;
}
}
//此时第一个是p，以j为分界[l + 1 , j]为小于val的元素，此时把l 归位即可
swap(arr, l, j);
return j;//已经经过转换归为，返回的是判断的值的索，放便后续在其左右区间继续寻找基准值排序
}
2.7.2.2 双路快排
来来来已经翻过一座山，继续继续核心理解的话下面这个也就简单了
从两端开始操作，同时排序大于等于和小于等于基准值的数
public static void quickSort(int[] arr){
partitionHelpTwo(arr , 0 , arr.length - 1);
}
private static void partitionHelp(int[] arr, int l, int r) {
if (r - l <= 15){
insertionSort(arr , l , r);
return;
}
int p = partition(arr , l , r);//这些都一样只是用来分区重点是排序过程
partitionHelp(arr , l , p - 1);
partitionHelp(arr , p + 1 , r);
}
private static int partition(int[] arr, int l, int r) {
int p = random.nextInt(l , r);
swap(arr , p , l);
int val = arr[l];//基准值
int i = l + 1;//最后一个小于等于基准值的元素索引
int j = r;//第一个大于等于基准值的元素
while (true){
while (i <= j && arr[i] < val){//左面都是小于，遇到小于不用管
i ++ ;
}//左端遇到了第一个大于val的元素索引
while (i <= j && arr[j] > val){
j -- ;
}
if (i >= j){
//这时说明已经排序完成了操作完了所有元素
break;
}
//走到这里没跳出说明没排序完，此时的情况就是i遇到了比基准值大的，j遇到了比基准值小的，把他俩对应的值交换一下就好了
swap(arr , i , j);
//此时继续向后走
i ++ ;
j -- ;//这里减了一次，所以j最后表示的是最后一个<= val的元素
}
swap(arr , l , j );
return j;
}
2.7.2.3 三路快排
嗯～8错，小怪打完了，现在就来刷最后的boss吧，原理核心是一样的哦
核心是一样的，只是把等于基准值的也独立出来
public static void quickSortThree(int[] arr){
partitionHelpThree(arr , 0 , arr.length - 1);
}
private static void partitionHelpThree(int[] arr, int l, int r) {
if (r - l <= 15){
insertionSort(arr , l , r);
return;
}
int p = random.nextInt(l , r);
swap(arr , l , p);
int val = arr[l];
int k = l;//[l , k]< val，k是最后一个小于val的元素
int i = k + 1;//[k + 1 , i] = val;
int j = r + 1;//[j , r] > val;
while (i < j){
if (arr[i] < val){
//值小于基准值
swap(arr , i , k + 1 );
//此时等于和小于的最后一个元素位置都要后移
i++;
k++;
}else if (arr[i] > val){
swap(arr , i , j - 1);//looklook交换的是前一个位置哦因为我们定义的是r+1
j -- ;
}else {
//此时值等于基准值将最后一个相等的位置后移
i ++ ;
}
}
//当跳出这个循环时，说明排序完了
swap(arr , l , k );//k是最后一个小于基准值的
partitionHelpThree(arr , l ,k - 1);//这里分区看好了哦这个排小于基准值的左面
partitionHelpThree(arr , j , r );//这个排大于基准值的右面
}
2.7.3 快速排序理解
- 快排时间复杂度O(nlogn)，不稳定排序
- 上面介绍了递归的分区操作，下面展示另一种方法
嗯，只是把递归的分区换成栈进行操作，排序的过程还是一样的
public static void quickSortParticular(int[] arr){
//不断的做以p为边界的区间分割
Deque<Integer> stack = new ArrayDeque<>();
int l = 0 ;
int r = arr.length - 1 ;
stack.push(r);
stack.push(l);
while (!stack.isEmpty()){
int left = stack.pop();
int right = stack.pop();
if (left >= right){
//此时全部读进过栈了，然后对栈内的剩余元素进行操作就好了
continue;
}
int p = partition(arr , left , right);//以p分区对左右，后续继续进行左面与右面的操作
stack.push(right);//对p的右半部分入栈
stack.push(p + 1);
stack.push(p - 1);//对p的左半部分入栈
stack.push(left);
}
}
- 三路快排只是提出来了等于基准时的情况，注意边界元素代表的位置，尤其三路时大于基准值时的情况
2.8 计数排序
boss刷完了看看剩下的小野怪吧都是很简单的
找到原数组最大值，记录每个值对应出现的次数，在以最大值定义的数组中，找出对应元素位置记录次数，循环这个数组，在元素内不为0时说明索引是待排序元素，值表示原数组中元素出现的个数，按次序对原数组更新。
2.8.1 计数排序图示
2.8.2 计数排序
public class CountingSort {
public int[] sort(int[] sourceArray) {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
//进行排序
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private int getMaxValue(int[] arr) {
//寻找当前数组最大值
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
}
还有两个野怪分别是‘桶排序’和‘基数排序’，嗯。。。我就不做搬运工了，因为这个我确实没有自己写，具体的排序方式可以参考《菜鸟教程》，这里是链接，桶排序、基数排序。
骑士的征战旅完成了哦，日后的学习继续加油