一起学算法（计算排序篇）

客官°小女子只卖身不卖艺 2023-10-14 10:08 111阅读 0赞

### 概念： ###

**计数排序**（Counting sort）是一个非基于比较稳定的线性时间的排序算法

**非基于比较**：之前学的排序都是通过比较数据的大小来实现有序的，比如希尔排序等，而计数排序不需要比较数据的大小而进行排序，计数排序顾名思义就是根据计数进行排序

**工作原理**：使用一个额外的数组arr,其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数组arr来将A中的元素排到正确的位置上

![01cf15dd05db4d0db7ce91040df02d76.png][]

**具体实现**：创建一个足够大的数组arr,足够大的意思是arr的下标范围可以包括所有的待排序数据值，然后遍历待排序数据，使用计数法统计每个数据出现的次数，最后遍历arr数组，将每一个值（arr\[i\]）的下标（i）放入arr\[i\]次

// 计数排序
        // 求数组中元素的最大值
        private int getMaxVal(int[] arr) {
            return Arrays.stream(arr).max().getAsInt();
        }
    
        public void countSort(int[] arr) {
            // 对数组进行判断
            if (arr == null || arr.length < 2) {
                return;
            }
            // 获取数组中最大值
            int max = getMaxVal(arr);
            //  创建一个比max多1个元素的数组
            int[] c = new int[max + 1];
            // 统计
            Arrays.stream(arr).forEach(item -> c[item]++);
            // 数组回填
            int index = 0;
            for (int i = 0; i < c.length; i++) {
                while (c[i] > 0) {
                    arr[index++] = i;
                    c[i]--;
                }
            }
        }

计数排序的排序是不是和数组的索引有关，索引是>=0,所以是不是我们如果碰到数列中有负数的情况，计数排序就失效了呢？一般的计数排序确实是失效了，但是咋们是二班的技术排序，

上**离散化**\+技术排序

// 离散化+计数排序
        public void countSort2(int[] arr) {
            // 去重，排序---形成离散化之后的数组
            int[] s = Arrays.stream(arr).distinct().sorted().toArray();
            // 创建一个统计数组
            int[] c = new int[s.length];
            // 进行统计
            // 从s数组中找arr[i]对应的索引
            Arrays.stream(arr).forEach(item -> {
                int index = find(s, item, 0, s.length - 1);
                c[index]++;
            });
    
            // 回填
            int index = 0;
            for (int i = 0; i < c.length; i++) {
                while (c[i] > 0) {
                    arr[index++] = s[i];
                    c[i]--;
                }
            }
        }
    
        // 二分查找法
        private int find(int[] arr, int num, int left, int right) {
            // 先找中间值
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] == num) {
                    return mid;
                } else if (arr[mid] > num) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return -1;
        }

### leetcode题单： ###

#### [找不同][Link 1] ####

class Solution {
        public char findTheDifference(String s, String t) {
            if (s == null && t == null) {
                return '0';
            }
            int[] hash = new int[256];
            for (int i = 0; i <s.length(); i++) {
                  hash[s.charAt(i)]++;
            }
            for (int i = 0; i <t.length(); i++) {
                hash[t.charAt(i)]++;
            }
            for (int i = 0; i <hash.length; i++) {
                 if((hash[i]&1)==1){
                     return (char) (i);
                 }
            }
            return '0';
        }
    }

#### [既不是最小值也不是最大值][Link 2] ####

class Solution {
        public int findNonMinOrMax(int[] nums) {
            if (nums.length < 3) return -1;
            countSort(nums); // 只对前三个数排序
            return nums[1];
        }
            public void countSort(int[] arr) {
            // 对数组进行判断
            if (arr == null || arr.length < 2) {
                return;
            }
            // 获取数组中最大值
            int max = getMaxVal(arr);
            //  创建一个比max多1个元素的数组
            int[] c = new int[max + 1];
            // 统计
            Arrays.stream(arr).forEach(item -> c[item]++);
            // 数组回填
            int index = 0;
            for (int i = 0; i < c.length; i++) {
                while (c[i] > 0) {
                    arr[index++] = i;
                    c[i]--;
                }
            }
        }
          private int getMaxVal(int[] arr) {
            return Arrays.stream(arr).max().getAsInt();
        }
    
    }

[01cf15dd05db4d0db7ce91040df02d76.png]: https://img-blog.csdnimg.cn/01cf15dd05db4d0db7ce91040df02d76.png
[Link 1]: https://leetcode.cn/problems/find-the-difference/
[Link 2]: https://leetcode.cn/problems/neither-minimum-nor-maximum/