本文共 12283 字，大约阅读时间需要 40 分钟。

import removeNthFromEnd.ListNode;import studyproxy.staticproxy.MaskInterface;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;public class ClassicSort {    public static void main(String[] arg) {//        int[] nums = {9, 7, 23, 45, 2, 1, 0, -1};        int[] nums = {9, 7, 23, 0, 100, 45, 2, 1, 10, 111, 0};        ClassicSort classicSort = new ClassicSort();//        classicSort.bubbleSort(nums);//        classicSort.quickSort(nums);//        classicSort.simpleInsertSort(nums);//        classicSort.shellSort(nums);//        classicSort.simpleSelectSort(nums);        classicSort.heapSort(nums);//        classicSort.mergeSort(nums);//        classicSort.countSort(nums);//        classicSort.bucketSort(nums);//        classicSort.radixSort2(nums);        System.out.println(Arrays.toString(nums));    }    /**     * 冒泡排序     *     * @param nums     */    public void bubbleSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        for (int i = nums.length - 1; i > 0; i--) {            for (int j = 0; j < i; j++) {                if (nums[j] > nums[j + 1]) {                    int temp = nums[j + 1];                    nums[j + 1] = nums[j];                    nums[j] = temp;                }            }        }    }    /**     * 快速排序     *     * @param nums     */    public void quickSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        int start = 0;        int end = nums.length - 1;        quickSort(nums, start, end);    }    private void quickSort(int[] nums, int start, int end) {        if (start >= end) return;        int mid = (start + end) / 2;        int left = start;        int right = end;        while (left < right) {            while (nums[left] < nums[mid]) left++;            while (nums[right] > nums[mid]) right--;            if (left < right) {                //swap                int temp = nums[left];                nums[left] = nums[right];                nums[right] = temp;                left++;                right--;            } else {                left++;            }        }        quickSort(nums, start, right);        quickSort(nums, left, end);    }    /**     * 简单插入排序     *     * @param nums     */    public void simpleInsertSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        for (int i = 1; i <= nums.length - 1; i++) {            int temp = nums[i];            int index = i;            while (index > 0 && temp < nums[index - 1]) {                nums[index] = nums[index - 1];                index--;            }            nums[index] = temp;        }    }    /**     * 希尔排序，递减增量排序算法     *     * @param nums     */    public void shellSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        int gap = nums.length / 2;        while (gap > 0) {            for (int i = gap; i <= nums.length - 1; i += gap) {                int temp = nums[i];                int index = i;                while (index > 0 && temp < nums[index - gap]) {                    nums[index] = nums[index - gap];                    index = index - gap;                }                nums[index] = temp;            }            gap = gap / 2;        }    }    /**     * 简单选择排序     *     * @param nums     */    public void simpleSelectSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        for (int i = 0; i < nums.length - 1; i++) {            int index = i;            for (int j = i + 1; j < nums.length; j++) {                if (nums[j] < nums[index]) {                    index = j;                }            }            int temp = nums[i];            nums[i] = nums[index];            nums[index] = temp;        }    }    /**     * 堆排序     *     * @param nums     */    public void heapSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        //堆化,创建大顶堆        //找到最后一个非叶子节点        int k = (nums.length - 1) / 2;        for (int i = k; i >= 0; i--) {            headAdjust(nums, i, nums.length);        }        //排序,每次取出堆顶的数放到末尾去        for (int i = nums.length - 1; i >= 0; i--) {            int temp = nums[i];            nums[i] = nums[0];            nums[0] = temp;            headAdjust(nums, 0, i);        }    }    /**     * 堆的调整     * 递归写法     * @param nums     * @param index  需要调整的节点下标     * @param length 堆的容量     */    private void headAdjust(int[] nums, int index, int length) {        int left = 2 * index + 1;        int maxIndex = left;//定义一个指针，指向左右两个节点中比较大的那个节点，初始时先指向左节点        if(left < length){//此节点存在左子节点            int right = left + 1;            //如果存在右节点，并且右节点的值偏大，指向右节点            if(right < length && nums[left] < nums[right]){                maxIndex = right;            }            //根节点值比较小，和比自己大的子节点互换            if (nums[index] < nums[maxIndex]) {                int temp = nums[index];                nums[index] = nums[maxIndex];                nums[maxIndex] = temp;                //指向刚才调整过的节点，再次调整                headAdjust(nums, maxIndex, length);            }        }    }    /**     * 堆的调整     * 非递归写法     * @param nums     * @param index  需要调整的节点下标     * @param length 堆的容量     */    private void headAdjust2(int[] nums, int index, int length) {        while (index < length) {            int left = 2 * index + 1;            if (left >= length) break;            int maxIndex = left;            if (left + 1 < length && nums[left] < nums[left + 1]) {                maxIndex = left + 1;            }            if (nums[index] < nums[maxIndex]) {                int temp = nums[index];                nums[index] = nums[maxIndex];                nums[maxIndex] = temp;                index = maxIndex;            } else {                break;            }        }    }    /**     * 归并排序     *     * @param nums     */    public void mergeSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        int[] temp = new int[nums.length];        mergeSort(nums, 0, nums.length - 1, temp);    }    private void mergeSort(int[] nums, int start, int end, int[] temp) {        if (start < end) {            int mid = (start + end) / 2;            mergeSort(nums, start, mid, temp);            mergeSort(nums, mid + 1, end, temp);            merge(nums, start, mid, end, temp);        }    }    private void merge(int[] nums1, int start, int mid, int end, int[] temp) {        int left1 = start;        int left2 = mid + 1;        int index = start;        while (left1 <= mid && left2 <= end) {            if (nums1[left1] < nums1[left2]) {                temp[index++] = nums1[left1++];            } else {                temp[index++] = nums1[left2++];            }        }        while (left1 <= mid) {            temp[index++] = nums1[left1++];        }        while (left2 <= end) {            temp[index++] = nums1[left2++];        }        for (int i = 0; i < index - start; i++) {            nums1[start + i] = temp[start + i];        }    }    /**     * 链表归并排序     *     * @param head     * @return     */    public ListNode mergeSoreLinkedList(ListNode head) {        if (null == head || head.next == null) return head;        ListNode fast = head;        ListNode slow = head;        while (null != slow && null != slow.next                && null != fast && null != fast.next && null != fast.next.next) {            fast = fast.next.next;            slow = slow.next;        }        fast = slow;        slow = slow.next;        fast.next = null;        ListNode left = mergeSoreLinkedList(head);        ListNode right = mergeSoreLinkedList(slow);        return merge2LinkedList(left, right);    }    private ListNode merge2LinkedList(ListNode p, ListNode q) {        if (null == p) return q;        if (null == q) return p;        ListNode res = new ListNode(0);        ListNode index = res;        while (null != p && null != q) {            if (p.val <= q.val) {                index.next = p;                p = p.next;            } else {                index.next = q;                q = q.next;            }            index = index.next;        }        if (p == null) {            index.next = q;        } else {            index.next = p;        }        return res.next;    }    /**     * 计数排序，排序数据范围必须是整数范围内     *     * @param nums     */    public void countSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        //找出最大值，最小值        int minValue = Integer.MAX_VALUE;        int maxValue = Integer.MIN_VALUE;        for (int i = 0; i < nums.length; i++) {            minValue = Math.min(nums[i], minValue);            maxValue = Math.max(nums[i], maxValue);        }        //创建辅助空间        int[] countArray = new int[maxValue - minValue + 1];        //统计        for (int i = 0; i < nums.length; i++) {            int value = nums[i];            countArray[value - minValue] += 1;        }        //整理        int p = nums.length - 1;        for (int i = countArray.length - 1; i >= 0; i--) {            while (countArray[i] > 0) {                nums[p] = i + minValue;                p--;                countArray[i] -= 1;            }        }    }    /**     * 桶排序     *     * @param nums     */    public void bucketSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        int minValue = Integer.MAX_VALUE;        int maxValue = Integer.MIN_VALUE;        for (int i = 0; i < nums.length; i++) {            minValue = Math.min(minValue, nums[i]);            maxValue = Math.max(maxValue, nums[i]);        }        //计算桶的个数        int bucketNum = (maxValue - minValue) / nums.length + 1;        ArrayList
   
    
     > buckets = new ArrayList<>();        for (int i = 0; i < bucketNum; i++) {            buckets.add(new ArrayList
     
      ());        }        //遍历数组，将数据分配到不同的桶里面        for (int i = 0; i < nums.length; i++) {            int index = (nums[i] - minValue) / nums.length;            buckets.get(index).add(nums[i]);        }        //对每个桶内部的数据进行排序        for (int i = 0; i < bucketNum; i++) {            Collections.sort(buckets.get(i));        }        //整理数据        int index = 0;        for (int i = 0; i < bucketNum; i++) {            for (int j = 0; j < buckets.get(i).size(); j++) {                nums[index++] = buckets.get(i).get(j);            }        }    }    /**     * 基数排序     *     * @param nums     */    public void radixSort(int[] nums) {        if (null == nums || 0 == nums.length) return;        //查找到最大值        int maxValue = Integer.MIN_VALUE;        for (int i = 0; i < nums.length; i++) {            maxValue = Math.max(maxValue, nums[i]);        }        //准备10个桶，每个桶的大小和nums的长度一致        ArrayList
      
       
        > buckets = new ArrayList<>(10);        //最大值是几位数，就分配和收集几趟        int temp = 1;        while (maxValue > 0) {            for (int i = 0; i < 10; i++) {                buckets.add(new ArrayList
        
         ()); } //先从个位数开始 for (int i = 0; i < nums.length; i++) { int index = (nums[i] / temp) % 10; buckets.get(index).add(nums[i]); } //按顺序收集出来 int p = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < buckets.get(i).size(); j++) { nums[p++] = buckets.get(i).get(j); } } buckets.clear(); temp = temp * 10; maxValue = maxValue / 10; } } /** * 优化，基数排序的第二版，辅助空间减小 * * @param nums */ public void radixSort2(int[] nums) { if (null == nums || 0 == nums.length) return; //创建辅助空间 int[] tempArray = new int[nums.length]; int[] bucket = new int[10]; //找出最大数 int maxValue = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { maxValue = Math.max(maxValue, nums[i]); } int temp = 1; while (maxValue > 0) { //初始化辅助空间 for (int i = 0; i < tempArray.length; i++) { tempArray[i] = 0; } for (int i = 0; i < bucket.length; i++) { bucket[i] = 0; } //遍历数组，桶中开始计数 for (int i = 0; i < nums.length; i++) { int index = (nums[i] / temp) % 10; bucket[index]++; } //把桶中的数字叠加出来，以方便得出数字在tempArray中的下标 for (int i = 1; i < bucket.length; i++) { bucket[i] = bucket[i] + bucket[i - 1]; } //收集整理数据到tempArray中 for (int i = nums.length - 1; i >= 0; i--) { int index = (nums[i] / temp) % 10;//得到数字位于哪个桶里面 int p = bucket[index] - 1;//由对应的桶中的数字得出数据位于tempArray中的下标 tempArray[p] = nums[i];//数据存入tempArray中对应的位置 bucket[index]--;//桶中的数字减一 } //把数据倒回nums中 for (int i = 0; i < tempArray.length; i++) { nums[i] = tempArray[i]; } temp *= 10; maxValue /= 10; } }}
        
       
      
     
    
   

这是我刚刚申请的微信公众号，欢迎大家关注。

转载地址：http://szqli.baihongyu.com/