88bifa必发唯一官网 1

88bifa必发唯一官网依附python进行桶排序与基数排序的总括,桶式排序和基数排序

本文首先举例阐述了两种排序方法的操作步骤,然后列出了用python进行的实现过程,最后对桶式排序方法的优劣进行了简单总结。

桶式排序不再是一种基于比较的排序方法,它是一种比较巧妙的排序方式,但这种排序方式需要待排序的序列满足以下两个特征:

基本概念

比较排序和非比较排序:

  • 常见的排序算法都是比较排序

    • 比较排序的时间复杂度通常为 O(n2) 或者
      O(nlogn),比较排序的时间复杂度下界就是 O(nlogn)
  • 非比较排序包括计数排序、桶排序和基数排序,非比较排序对数据有要求,因为数据本身包含了定位特征,所有才能不通过比较来确定元素的位置

    • 非比较排序的时间复杂度可以达到 O(n),但是都需要额外的空间开销

一、桶排序:

待排序列所有的值处于一个可枚举的范围之类;

几种排序算法的总结与比较

排序方法 平均时间 最坏时间 辅助空间 稳定性
简单排序 – 冒泡排序 O(n2) O(n^2) O(1) 稳定
简单排序 – 选择排序 O(n2) O(n2) O(1) 不稳定
简单排序 – 插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(nlogn) O(n2) O(logn) 不稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(n) 稳定
希尔排序 O(nlogn2) = O(n1.3) O(n2) O(n) 不稳定
计数排序 O(n + k) O(n + k) O(k) 稳定
桶排序 O(n + k) O(n2) O(n) 稳定
基数排序 O(nk) O(nk) O(n + k) 不稳定

88bifa必发唯一官网 1

Array Sorting Algorithms

排序一个数组[5,3,6,1,2,7,5,10]

待排序列所在的这个可枚举的范围不应该太大,否则排序开销太大。

冒泡排序

通过与相邻元素的比较和交换来把小的数交换到最前面,或者把大的数交换到最后面。

冒泡排序的时间复杂度为 O(n2)

代码如下:

    // 冒泡排序
    public void bubbleSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        // 只需要循环 n-1 次
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

分析:假设输入为 4, 2, 5, 1, 3
第一次循环后,变为 2, 4, 1, 3, 55 被移动到最后
第二次循环后,变为 2, 1, 3, 4, 54 被移动到最后的第二个位置
以此类推

值都在1-10之间,建立10个桶:

排序的具体步骤如下:

选择排序

选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。
但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。

选择排序的时间复杂度为 O(n2)

代码如下:

    // 选择排序
    public void selectSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        int minIndex;

        // 只需要循环 n-1 次
        for (int i = 0; i < nums.length - 1; i++) {
            minIndex = i;

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
        }
    }

分析:假设输入为 4, 2, 5, 1, 3
第一次循环后,变为 1, 2, 5, 4, 31 被移动到最前
第二次循环后,变为 1, 2, 5, 4, 32 被移动到最前的第二个位置
以此类推

[0 0 0 0 0 0 0 0 0 0] 桶

(1)对于这个可枚举范围构建一个buckets数组,用于记录“落入”每个桶中元素的个数;

插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的。

插入排序的时间复杂度为 O(n2)

代码如下:

    // 插入排序
    public void insertSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        // 假设第一个数位置是正确的
        for (int i = 1; i < nums.length; i++) {
            int j = i;

            int target = nums[j];

            // 后移
            while (j > 0 && nums[j - 1] > target) {
                nums[j] = nums[j - 1];
                j--;
            }

            // 插入
            nums[j] = target;
        }
    }

分析:假设输入为 4, 2, 5, 1, 3
第一次循环后,变为 2, 4, 5, 1, 3
第二次循环后,变为 2, 4, 5, 1, 3
第三次循环后,变为 1, 2, 4, 5, 3
以此类推

[1 2 3 4 5 6 7 8 9 10] 桶代表的值

(2)将(1)中得到的buckets数组重新进行计算,按如下公式重新计算:

快速排序

其实其思想是来自冒泡排序,冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端,而快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

快速排序是不稳定的,其时间复杂度为 O(nlogn)

代码如下:

    // 快速排序
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end)
            return;

        int partitionIdx = partition(nums, start, end);

        quickSort(nums, start, partitionIdx - 1);
        quickSort(nums, partitionIdx + 1, end);
    }

    // partition
    public int partition(int[] nums, int start, int end) {
        if (start == end) {
            return start;
        }

        int pivot = nums[start];

        while (start < end) {
            // 从右往左找到第一个小于 pivot 的元素
            while (start < end && nums[end] >= pivot) {
                end--;
            }
            // 把小的移动到左边
            nums[start] = nums[end];

            // 从左往右找到第一个大于 pivot 的元素
            while (start < end && nums[start] <= pivot) {
                start++;
            }
            // 把大的移动到右边
            nums[end] = nums[start];
        }

        // 最后把pivot赋值到中间
        nums[start] = pivot;

        return start;
    }

分析:假设输入为 4, 2, 5, 1, 3
第一轮递归后,变为 3, 2, 1, 4, 5
第一轮递归后,变为 1, 2, 3, 4, 5
以此类推

遍历数组,第一个数字5,第五个桶加1

buckets[i] = buckets[i] +buckets[i-1]
(其中1<=i<buckets.length); 

堆排序

堆排序是借助堆来实现的选择排序。
注意:如果想升序排序就使用大顶堆,反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

具体参见:堆的使用及相关LeetCode题目

[0 0 0 0 1 0 0 0 0 0]

桶式排序是一种非常优秀的排序算法,时间效率极高,它只要通过2轮遍历:第1轮遍历待排数据,统计每个待排数据“落入”各桶中的个数,第2轮遍历buckets用于重新计算buckets中元素的值,2轮遍历后就可以得到每个待排数据在有序序列中的位置,然后将各个数据项依次放入指定位置即可。

归并排序

归并排序使用了递归分治的思想。
把待排序列看成由两个有序的子序列,然后合并两个子序列,然后把子序列看成由两个有序序列…倒着来看,其实就是先两两合并,然后四四合并…最终形成有序序列。

归并排序空间复杂度为 O(n),时间复杂度为 O(nlogn)

代码如下:

    // 归并排序
    public void mergeSort(int[] arr, int start, int end) {
        if (start >= end)
            return;

        int mid = (start + end) / 2;

        // 递归排序左边
        mergeSort(arr, start, mid);
        // 递归排序右边
        mergeSort(arr, mid + 1, end);

        // 合并
        merge(arr, start, mid, end);
    }

    // 合并两个有序数组
    public void merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1]; // 中间数组

        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= end) {
            temp[k++] = arr[j++];
        }

        for (int p = 0; p < temp.length; p++) {
            arr[start + p] = temp[p];
        }
    }

第二个数字3,第三个桶加1

桶式排序的空间开销较大,它需要两个数组,第1个buckets数组用于记录“落入”各桶中元素的个数,进而保存各元素在有序序列中的位置,第2个数组用于缓存待排数据。

希尔排序

希尔排序是插入排序的一种高效率的实现。
简单的插入排序中,如果待排序列是正序时,时间复杂度是O(n),如果序列是基本有序的,使用直接插入排序效率就非常高。
希尔排序就利用了这个特点。基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

希尔排序时间复杂度为 O(nlogn)

代码如下:

    // 希尔排序的一趟插入
    public void shellInsert(int[] nums, int d) {
        for (int i = d; i < nums.length; i++) {
            int j = i - d;

            // 记录要插入的数据
            int temp = nums[i];
            // 从后向前,找到比其小的数的位置
            while (j >= 0 && nums[j] > temp) {
                // 向后挪动
                nums[j + d] = nums[j];
                j -= d;
            }

            // 存在比其小的数
            if (j != i - d)
                nums[j + d] = temp;
        }
    }

    // 希尔排序
    public void shellSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        int d = nums.length / 2;
        while (d >= 1) {
            shellInsert(nums, d);
            d /= 2;
        }
    }
[0 0 1 0 1 0 0 0 0 0]

桶式排序是稳定的。

计数排序

前提条件:待排序的数要满足一定的范围的整数,而且计数排序需要比较多的辅助空间。其基本思想是,用待排序的数作为计数数组的下标,统计每个数字的个数。然后依次输出即可得到有序序列。

计数排序空间复杂度为 O(n),时间复杂度为 O(n)

代码如下:

    // 计数排序
    public void countSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        int max = max(nums);

        int[] counts = new int[max + 1];
        Arrays.fill(counts, 0);

        // 计数
        for (int i : nums) {
            counts[i]++;
        }

        int k = 0;
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < counts[i]; j++) {
                nums[k++] = i;
            }
        }
    }

    public int max(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i : nums) {
            if (i > max)
                max = i;
        }

        return max;
    }

遍历后

如果待排序数据的范围在0~k之间,那么它的时间复杂度是O(k+n)的

桶排序

桶排序算是计数排序的一种改进和推广。
基本思想:使用映射函数将待排序的数组划分成M个的子区间(桶)
。接着对每个桶中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出每个桶中的全部内容即是一个有序序列。
桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:如果关键字k1<k2,那么f(k1)<=f(k2)也就是说第
i 个桶中的最小数据都要大于第 i - 1 个桶中最大数据。

代码如下:

    // 桶排序
    public void bucketSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }

        // 桶数
        int bucketNum = (max - min) / nums.length + 1;

        // 创建桶
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>(
                bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for (int i = 0; i < nums.length; i++) {
            int idx = (nums[i] - min) / (nums.length);
            buckets.get(idx).add(nums[i]);
        }

        // 对每个桶进行排序
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }

        // 还原排好序的数组
        int k = 0;
        for (List<Integer> bucket : buckets) {
            for (int i : bucket) {
                nums[k++] = i;
            }
        }
    }
[1 1 1 0 2 1 1 0 0 1]

桶式排序算法速度很快,因为它的时间复杂度是O(k+n),而基于交换的排序时间上限是nlg n。

基数排序

基数排序是一种和前面排序方式不同的排序方式,基数排序不需要进行关键字之间的比较。
基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。
如果对数字进行排序,那么个位、十位、百位就是不同优先级的关键字,如果要进行升序排序,那么个位、十位、百位优先级依次增加。

代码如下:

    // 基数排序
    public void radixSort(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        // 获取最大位数
        int maxBit = getMaxBit(nums);

        /*
         * 先根据个位数排序,再根据十位数排序...
         */
        for (int i = 1; i <= maxBit; i++) {
            // 分配
            List<List<Integer>> buf = distribute(nums, i);

            // 收集
            collect(nums, buf);
        }

    }

    // 分配
    public List<List<Integer>> distribute(int[] nums, int iBit) {
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for (int j = 0; j < 10; j++) {
            buf.add(new LinkedList<Integer>());
        }

        for (int i = 0; i < nums.length; i++) {
            buf.get(getNBit(nums[i], iBit)).add(nums[i]);
        }

        return buf;
    }

    // 收集
    public void collect(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for (List<Integer> bucket : buf) {
            for (int i : bucket) {
                arr[k++] = i;
            }
        }
    }

    // 获取最大位数
    public int getMaxBit(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i : nums) {
            max = Math.max(max, (i + "").length());
        }

        return max;
    }

    // 获取数字x的第n位
    public static int getNBit(int x, int n) {
        String str = x + "";
        if (str.length() < n)
            return 0;
        else
            return str.charAt(str.length() - n) - '0';
    }

引用:
面试中的排序算法总结
各种排序算法总结和比较
Big-O Complexity
Chart

输出

但是它的限制多,比如它只能排整形数组。而且当k较大,而数组长度n较小,即k>>n时,辅助数组C[k+1]的空间消耗较大。

[1 2 3 5 5 6 7 10]

当数组为整形,且k和n接近时,
可以用此方法排序。(有的文章也称这种排序算法为“计数排序”)

代码:

代码实现:

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res
public class BucketSortTest {  
    public static int count = 0;  

    public static void main(String[] args) {  

        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };  
        print(data);  
        bucketSort(data, 0, 10);  
        print(data);  

    }  

    public static void bucketSort(int[] data, int min, int max) {  
        // 缓存数组  
        int[] tmp = new int[data.length];  
        // buckets用于记录待排序元素的信息  
        // buckets数组定义了max-min个桶  
        int[] buckets = new int[max - min];  
        // 计算每个元素在序列出现的次数  
        for (int i = 0; i < data.length; i++) {  
            buckets[data[i] - min]++;  
        }  
        // 计算“落入”各桶内的元素在有序序列中的位置  
        for (int i = 1; i < max - min; i++) {  
            buckets[i] = buckets[i] + buckets[i - 1];  
        }  
        // 将data中的元素完全复制到tmp数组中  
        System.arraycopy(data, 0, tmp, 0, data.length);  
        // 根据buckets数组中的信息将待排序列的各元素放入相应位置  
        for (int k = data.length - 1; k >= 0; k--) {  
            data[--buckets[tmp[k] - min]] = tmp[k];  
        }  
    }  

    public static void print(int[] data) {  
        for (int i = 0; i < data.length; i++) {  
            System.out.print(data[i] + "\t");  
        }  
        System.out.println();  
    }  

}  

二、基数排序:

  运行结果:

例如,对如下数据序列进行排序。

5    3    6    2    1    9    4    8    7    
1    2    3    4    5    6    7    8    9    
192,221,12,23

基数排序,说白了就是进行多次的桶式排序。

可以观察到它的每个数据至多只有3位,因此可以将每个数据拆分成3个关键字:百位(高位)、十位、个位(低位)。如果按照习惯思维,会先比较百位,百位大的数据大,百位相同的再比较十位,十位大的数据大;最后再比较个位。基数排序方法对任一子关键字排序时必须借助于另一种排序方法,而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字,它们一定位于0-9这个可枚举的范围内,这个范围不大,因此用桶式排序效率非常好。

基数排序已经不再是一种常规的排序方式,它更多地像一种排序方法的应用,基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序,也就是说,基数排序的实质是多关键字排序。

代码:

多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字;第1个排序关键字,第2个排序关键字,第3个排序关键字……然后,根据子关键字对待排序数据进行排序。

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d轮排序
  s = [[] for k in xrange(10)]#因为每一位数字都是0~9,故建立10个桶
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

多关键字排序时有两种解决方案:

对数组中的元素按照从低位到高位排序,对于[192,221,12,23]第一轮按照个位数字相同的放在一组,是s[1]
=[221],s[2]=[192,12],s[3]=23,第二轮按照十位数字进行排序,s[1]=[12],s[2]=[221,23],s[9]=[192],第三轮按照百位数字进行排序,s[0]=[12,23],s[1]=[192],s[2]=[221]

最高位优先法(MSD)(Most Significant Digit first)

总结:

最低位优先法(LSD)(Least Significant Digit first)

桶排序与基数排序常作为桶式排序出现,基数排序进行了多轮的桶排序。桶式排序不再是一种基于比较的排序方法,它是一种比较巧妙的排序方式,但这种排序方式需要待排序的序列满足以下两个特征:待排序列所有的值处于一个可枚举的范围之类;待排序列所在的这个可枚举的范围不应该太大,否则排序开销太大。可以用于学生成绩的排序,因为在若干学生中成绩的范围仅在100以内。

例如,对如下数据序列进行排序。

桶式排序的空间开销较大,它需要两个数组,第1个buckets数组用于记录“落入”各桶中元素的个数,进而保存各元素在有序序列中的位置,第2个数组用于缓存待排数据。它只能排整形数组。而且当k较大,而数组长度n较小,即k>>n时,辅助数组C[k+1]的空间消耗较大。

192,221,12,23

以上这篇基于python进行桶排序与基数排序的总结就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持脚本之家。

可以观察到它的每个数据至多只有3位,因此可以将每个数据拆分成3个关键字:百位(高位)、十位、个位(低位)。

您可能感兴趣的文章:

  • Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】
  • Python实现的基数排序算法原理与用法实例分析
  • Python实现桶排序与快速排序算法结合应用示例
  • python简单实现基数排序算法
  • Python实现的桶排序算法示例

如果按照习惯思维,会先比较百位,百位大的数据大,百位相同的再比较十位,十位大的数据大;最后再比较个位。人得习惯思维是最高位优先方式。

如果按照人得思维方式,计算机实现起来有一定的困难,当开始比较十位时,程序还需要判断它们的百位是否相同–这就认为地增加了难度,计算机通常会选择最低位优先法。

基数排序方法对任一子关键字排序时必须借助于另一种排序方法,而且这种排序方法必须是稳定的。

对于多关键字拆分出来的子关键字,它们一定位于0-9这个可枚举的范围内,这个范围不大,因此用桶式排序效率非常好。

对于多关键字排序来说,程序将待排数据拆分成多个子关键字后,对子关键字排序既可以使用桶式排序,也可以使用任何一种稳定的排序方法。

 

代码实现:

package 基数排序;

import java.util.Arrays;

public class MultiKeyRadixSortTest {  

    public static void main(String[] args) {  
        int[] data = new int[] { 1100, 192, 221, 12, 23 };  
        print(data);  
        radixSort(data, 10, 4);  
        System.out.println("排序后的数组:");  
        print(data);  
    }  

    public static void radixSort(int[] data, int radix, int d) {  
        // 缓存数组  
        int[] tmp = new int[data.length];  
        // buckets用于记录待排序元素的信息  
        // buckets数组定义了max-min个桶  
        int[] buckets = new int[radix];  

        for (int i = 0, rate = 1; i < d; i++) {  

            // 重置count数组,开始统计下一个关键字  
            Arrays.fill(buckets, 0);  
            // 将data中的元素完全复制到tmp数组中  
            System.arraycopy(data, 0, tmp, 0, data.length);  

            // 计算每个待排序数据的子关键字  
            for (int j = 0; j < data.length; j++) {  
                int subKey = (tmp[j] / rate) % radix;  
                buckets[subKey]++;  
            }  

            for (int j = 1; j < radix; j++) {  
                buckets[j] = buckets[j] + buckets[j - 1];  
            }  

            // 按子关键字对指定的数据进行排序  
            for (int m = data.length - 1; m >= 0; m--) {  
                int subKey = (tmp[m] / rate) % radix;  
                data[--buckets[subKey]] = tmp[m];  
            }  
            rate *= radix;  
        }  

    }  

    public static void print(int[] data) {  
        for (int i = 0; i < data.length; i++) {  
            System.out.print(data[i] + "\t");  
        }  
        System.out.println();  
    }  

}  

  运行结果:

1100    192    221    12    23    
排序后的数组:
12    23    192    221    1100    

 转自: