七、排序-算法总结

七、排序算法

7.1 常考排序

7.1.1 快速排序

package com.gyh.reverselinkedlist;import java.util.*;
import java.util.stream.Collectors;/*** @author Gao YongHao* @version 1.0*/
public class Test1 {public static void main(String[] args) {int[] nums = {2};quickSort(nums, 0, nums.length-1,false);Arrays.stream(nums).forEach(System.out::println);}/*** 快排* @param nums 原数组* @param left 左边界* @param right 右边界* @param isAsc 是否升序*/private static void quickSort(int[] nums, int left, int right, boolean isAsc){if(nums == null || nums.length == 1){return;}int pivot = nums[left]; // 选定第一个数为中轴值int l = left , h = right;while(l < h){while(l<h && (isAsc == (nums[h] >= pivot))){h--;}nums[l] = nums[h];while(l<h && (isAsc == (nums[l] <= pivot))){l++;}nums[h] = nums[l];}nums[l] = pivot; // 摆放中轴值// 对左右分别再进行中轴值定位if(l - 1>left){quickSort(nums, left, l-1, isAsc);}if(h+1<right){quickSort(nums, h+1, right, isAsc);}}}

7.1.2 归并排序

package com.gyh.reverselinkedlist;import java.util.Arrays;/*** @author Gao YongHao* @version 1.0*/
public class Test2 {public static void main(String[] args) {int[] nums = {1,22,13,94,5};divide(nums, new int[nums.length], 0, nums.length-1,false);Arrays.stream(nums).forEach(System.out::println);}/*** 使用分治算法* @param nums 数组* @param temp 临时数组* @param left 保存左边界* @param right 保存右边界* @param isAsc 是否为升序*/private static void divide(int[] nums, int[] temp, int left, int right, boolean isAsc){if(left>=right){return;}int mid = (right+left) / 2;divide(nums, temp, left, mid, isAsc);divide(nums, temp, mid+1, right, isAsc);merge(nums, temp, left, mid+1, right+1, isAsc);}private static void merge(int[] nums, int[] temp, int l, int r, int end, boolean isAsc){int length = 0;int start = l;int mid = r;while(l<mid&&r<end){if(isAsc?nums[l]<=nums[r]:nums[r]<=nums[l]){temp[length++] = nums[l++];}else{temp[length++] = nums[r++];}}while(l<mid) temp[length++] = nums[l++];while(r<end) temp[length++] = nums[r++];length = 0;for(int i = start;i<end;i++){nums[i] = temp[length++];}}
}

7.1.3 堆排序

package com.gyh.reverselinkedlist;import java.util.Arrays;/*** @author Gao YongHao* @version 1.0*/
public class Test3 {public static void main(String[] args) {int[] nums = {10,28,1,5,88,17,2,17};heapSort(nums, false);Arrays.stream(nums).forEach(System.out::println);}private static void heapSort(int[] nums, boolean isAsc){// 对原数组初始化堆initHeap(nums, isAsc);// 只用作 nums.length-1 次调整堆for(int i = nums.length-1;i>0;i--){// 将堆顶元素放置于最后int temp = nums[0];nums[0] = nums[i];nums[i] = temp;adjustHeap(nums, 0, i-1, isAsc);}}// 初始化堆private static void initHeap(int[] nums, boolean isAsc){// nums.length/2-1为最后一个非叶子结点的位置// 从最后一个非叶子结点依次向上进行堆构建for(int i = nums.length/2-1;i>=0;i--){adjustHeap(nums, i, nums.length-1,isAsc);}}/*** 调整堆* @param nums 原数组* @param heapTopIndex 堆顶* @param lastIndex 最后一个元素的下标* @param isAsc 是否升序*/private static void adjustHeap(int[] nums, int heapTopIndex, int lastIndex, boolean isAsc){if(heapTopIndex>=lastIndex){return;}// 按完全二叉树结构从最顶至最后一个元素依次进行堆构建//int heapTopData = nums[heapTopIndex];// 首先定位至其左子树for(int i = heapTopIndex*2+1;i<=lastIndex;i=i*2+1){// 定位满足堆条件的子树// 找到子树根节点的最大值对应的下标if(i<lastIndex && (isAsc?nums[i+1] > nums[i]:nums[i+1] < nums[i])){i++;}// 找到原始堆顶的最终位置if(isAsc?heapTopData >= nums[i]:heapTopData <= nums[i]){break;}// 与子树根节点交换(此处直接覆盖)nums[heapTopIndex] = nums[i];// 更新栈顶下标heapTopIndex = i;}// 将原始的堆顶元素放置于最终位置nums[heapTopIndex] = heapTopData;}
}