精华内容
下载资源
问答
  • void sort(String[] arr) { int sLen = arr[0].length(); //从右往左对每个位置上的字符排序 for(int i = sLen-1; i >= 0; i--) { //用于存储arr中某个位置上各字符数量,ASCII 0~255,所以大小为256 ...
    /*定长字符串*/
    void sort(String[] arr) {
        int sLen = arr[0].length();
        //从右往左对每个位置上的字符排序
        for(int i = sLen-1; i >= 0; i--) {
            //用于存储arr中某个位置上各字符数量,ASCII 0~255,所以大小为256
            int[] count =  new int[256];
            //统计索引i上各字符的数量
            for(int j = 0; j < arr.length; j++) {
                count[arr[j].charAt(i)]++;
            }
            //将count[j]转换为索引i上字符为j的一组字符串的起始索引
            int pre = 0;
            for(int j = 0; j < 256; j++) {
                if(count[j] != 0) {
                    int t = count[j];
                    count[j] = pre;
                    pre += t;
                }
            }
            String[] sorted = new String[arr.length];
            //将对索引i上的字符排序后的arr存进sorted
            for(int j = 0; j < arr.length; j++) {
                sorted[count[arr[j].charAt(i)]++] = arr[j];
            }
            //将sorted写回arr
            for(int j = 0; j < arr.length; j++) {
                arr[j] = sorted[j];
            }
        }
    }

    展开全文
  • C语言实现低位优先法分配排序(LSD)代码如下: #include<stdio.h> #include<math.h> #define N 10000 void LSD(int s[],int n,int digits_max)//自定义低位优先法分配排序函数,s为数组名,n为数组...

    C语言数组实现低位优先法分配排序(LSD)代码如下:

    #include<stdio.h>
    #include<math.h>
    #define N 10000
    
    void LSD(int s[],int n,int digits_max)//自定义低位优先法分配排序函数,s为数组名,n为数组长度,digits_max为数组元素最大位数
    {
        double i;
        for(i=0;i<digits_max;i++){
            int j,k,t,l;
            for(j=1;j<n;j++){//对各位次分别利用直接插入排序
                for(k=j-1;k>=0;k--){
                    if((s[j]/(int)pow(10,i)%10)>=(s[k]/(int)pow(10,i)%10))//按位数进行比较
                        break;
                }
                if(j!=k+1){
                    t=s[j];
                    for(l=j-1;l>=k+1;l--){
                        s[l+1]=s[l];
                    }
                    s[k+1]=t;
                }
            }
        }
    }
    
    
    int main()
    {
        int s[N];
        int n,i,digits_max;
        printf("请输入待排数组长度:\n");
        scanf("%d",&n);//扫描数组长度
        printf("请输入待排数组:\n");
        for(i=0;i<n;i++)
            scanf("%d",&s[i]);//扫描数组
        printf("请输入待排数组元素的最大位数:\n");
        scanf("%d",&digits_max);//扫描数组元素的最大位数
        LSD(s,n,digits_max);//将数组通过自定义的低位优先法分配排序函数进行排序
        printf("排序结果如下:\n");
        for(i=0;i<n;i++)
            printf("%d ",s[i]);//输出排序结果
        return 0;
    }
    
    展开全文
  • package com.xiuye.util.string; import com.xiuye.sharp.X; import com.xiuye.util.log.XLog; import java.util.Arrays; ...public class LSD { ... public static void sort(String []a,int W){ ... String []aux = n.
    package com.xiuye.util.string;
    
    import com.xiuye.sharp.X;
    import com.xiuye.util.log.XLog;
    
    import java.util.Arrays;
    
    public class LSD {
    
        public static void sort(String []a,int W){
            int N = a.length;
            int R = 256;
            String []aux = new String[N];
            for(int d=W-1;d>=0;d--){
                int []count = new int[R+1];
                for(int i=0;i<N;i++){//计算频率
                    count[a[i].charAt(d)+1]++;
                }
    
    //            for(int i=0;i< count.length;i++){
    //                XLog.print(count[i]," ");
    //            }
    //            XLog.println();
    
                for(int r=0;r<R;r++){//frequency to index
                    count[r+1] += count[r];
                }
    //            for(int i=0;i< count.length;i++){
    //                XLog.print(count[i]," ");
    //            }
    //            XLog.println();
                for (int i=0;i<N;i++){//classify
                    aux[count[a[i].charAt(d)]++] = a[i];
                }
    //            for(int i=0;i< N;i++){
    //                XLog.print(aux[i]," ");
    //            }
    //            XLog.println();
                for(int i=0;i<N;i++){//rewrite back
                    a[i] = aux[i];
                }
            }
        }
    
        public static void main(String[] args) {
    
            String []str = {
    //                "A",
    //                "B",
    //                "C"
              "4PGC938",
              "2IYE230",
              "3CI0720",
              "1ICK750",
              "10HV845",
              "4JZY524",
              "1ICK750",
              "3CI0720",
              "10HV845",
              "10HV845",
              "2RLA629",
              "2RLA629",
              "3ATW723"
    
            };
            sort(str,1);
    
            for(int i=0;i<str.length;i++){
                X.lnS(str[i]);
            }
            X.lnS(str);
    
        }
    
    }
    
    1ICK750 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    10HV845 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    1ICK750 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    10HV845 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    10HV845 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    2IYE230 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    2RLA629 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    2RLA629 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    3CI0720 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    3CI0720 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    3ATW723 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    4PGC938 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    4JZY524 	[ line:69 | com.xiuye.util.string.LSD | LSD.java ]
    1ICK750 10HV845 1ICK750 10HV845 10HV845 2IYE230 2RLA629 2RLA629 3CI0720 3CI0720 3ATW723 4PGC938 4JZY524 	[ line:71 | com.xiuye.util.string.LSD | LSD.java ]
    
    
    

     

    展开全文
  • 这种方法一般被称为低位优先(Least=Significant-Digit First,LSD)的字符串排序。使用数字(digit)代替字符(character)的原因要追溯到相同方法在各种数字类型中的应用。如果将一个字符串看作一个256进制的数字...

    字符串排序

    对于许多排序应用,决定顺序的键都是字符串。

    第一类方法会从右到左检查键中的字符。这种方法一般被称为低位优先(Least=Significant-Digit First,LSD)的字符串排序。使用数字(digit)代替字符(character)的原因要追溯到相同方法在各种数字类型中的应用。如果将一个字符串看作一个256进制的数字,那么从右向左检查字符串就等价于先检查数字的最低位。这种方法最适合用于键的长度都相同的字符串排序应用。

    第二类方法会从左到右检查键中的字符,首先查看的是最高位的字符。这些方法通常称为高位优先(MSD)的字符串排序。高位优先的字符串排序的吸引人之处在于,它们不一定需要检查所有的输入就能够完成排序。高位优先的字符串排序和快速排序类似,因为它们都会将需要排序的数组切分为独立的部分并递归地用相同的方法处理子数组来完成排序。它们的区别之处在于高位优先的字符串排序算法在切分时仅使用键的第一个字符,而快速排序的比较则会涉及键的全部。要学习的第一种方法会为每个字符创建一个切分,第二种方法则总会产生三个切分,分别对应被搜索键的第一个字符小于、等于或大于切分键的第一个字符的情况。

    键索引计数法

    键索引计数的方法适用于小整数键的简单排序方法,它是下面三种字符串排序算法中两种的基础。
    这种方法有以下4个步骤:

    • 频率统计:第一步就是使用int数组count[]计算每个键出现的频率。对于数组中的每个元素,都使用它的键访问count[]中的相应元素并将其加1,如果键为r,则将count[r+1]加1。
    • 将频率转换为索引:接下来,使用count[]来计算每个键在排序结果中的起始索引位置。一般来说,任意给定的键的起始索引均为所有较小的键所对应的出现频率之和。对于每个键值r,小于r+1的键的频率之和为小于r的键的频率之和加上count[r],因此从左向右将count[]转化为一张用于排序的索引表是很容易的。
    • 数据分类:在将count[]数组转换为一张索引表之后,将所有元素移动到一个辅助数组aux[]中以进行排序。每个元素在aux[]中的位置是由它的键对应的count[]值决定,在移动之后将count[]中对应元素的值加1,以保证count[r]总是下一个键为r的元素在aux[]中的索引位置。这个过程只需遍历一遍数据即可产生排序结果。注意:在我们的一个应用中,这种实现方式的稳定性是很关键的——键相同的元素在排序后会被聚集到一起,但相对顺序没有变化。
    • 回写:因为我们在将元素移动到辅助数组的过程中完成了排序,所以最后一步就是将排序的结果复制回原数组中。

    键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组11N+4R+1次。只要当R在N的一个常数因子范围之内,它都是一个线性时间级别的排序方法。

    代码:

    package section5_1;
    
    public class KeyIndexCount {
    
        public static void main(String[] args) {
            String[] a = {
                    "Anderson 2",
                    "Brown 3",
                    "Davis 3",
                    "Garcia 4",
                    "Harris 1",
                    "Jackson 3",
                    "Johnson 4",
                    "Jones 3",
                    "Martin 1",
                    "Martinez 2",
                    "Miller 2",
                    "Moore 1",
                    "Robinson 2",
                    "Smith 4",
                    "Taylor 3",
                    "Thomas 4",
                    "Thompson 4",
                    "White 2",
                    "Williams 3",
                    "Wilson 4"
            };
    
            int N = a.length;
            int R = 5;
            String[] aux = new String[N];
            int[] auxidx = new int[N];
            int[] count = new int[R + 1];
    
            System.out.println("----------------------before sort:");
            for (int i = 0;i < N;i++) {
                System.out.println(a[i]);
            }
    
            //计算出现的频率
            for (int i = 0;i < N;i++) {
                String[] s = a[i].split(" ");
                count[Integer.parseInt(s[1]) + 1]++;
            }
    
            System.out.println("---------------------count:");
            for (int i = 0;i <= R;i++)
                System.out.print(count[i] + " ");
            System.out.println();
    
            //将频率转换为索引
            for (int r = 0;r < R;r++) {
                count[r + 1] += count[r];
            }
    
            System.out.println("---------------------count:");
            for (int i = 0;i <= R;i++)
                System.out.print(count[i] + " ");
            System.out.println();
    
            //将元素分类
            for (int i = 0;i < N;i++) {
                String[] s = a[i].split(" ");
                aux[count[Integer.parseInt(s[1])]] = s[0];
                auxidx[count[Integer.parseInt(s[1])]++] = Integer.parseInt(s[1]);
            }
    
            //回写
            for (int i = 0;i < N;i++) {
                a[i] = aux[i] + " "  + auxidx[i];
            }
    
            System.out.println("-------------------after sort:");
            for (int i = 0;i < N;i++) {
                System.out.println(a[i]);
            }
        }
    
    }
    
    

    输出:
    在这里插入图片描述

    低位优先的字符串排序

    车牌号由数字和字母混合组成,因此一般都将它们表示为字符串。在最简单的情况中,这些字符串的长度都是相同的。将此类字符串排序可以通过键索引计数法来完成。如果字符串的长度均为W,那就从右向左以每个位置的字符作为键,用键索引计数法将字符串排序W遍。除非键索引计数法是稳定的,否则这种方法是行不通的。

    命题:低位优先的字符串排序算法能够稳定地将定长字符串排序。

    排序的稳定性:在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,则称排序算法是稳定的。

    证明该命题的另一种方法是向前看:如果有两个键,它们中还没有被检查过的字符串是完全相同的,那么键的不同之处就仅限于已经被检查过的字符。因为两个键已经被排序过,所以出于稳定性它们将一直保持有序。另外,如果还没被检查过的部分是不同的,那么已经被检查过的字符对于两者的最终顺序没有意义,之后的某轮处理会根据更高位字符的不同修正这对键的顺序。

    从理论上说,低位优先的字符串排序的意义重大,因为它是一种适用于一般应用的线性时间排序算法。无论N有多大,它都只遍历W次数据。

    代码:

    package section5_1;
    
    public class LSD {
    
        public static void sort(String[] a, int W) {
            int N = a.length;
            int R = 256;
            String[] aux = new String[N];
    
            for (int d = W - 1;d >= 0;d--) {
                int[] count = new int[R + 1];
                for (int i = 0;i < N;i++) {
                    count[a[i].charAt(d) + 1]++;
                }
                for (int r = 0;r < R;r++) {
                    count[r + 1] += count[r];
                }
                for (int i = 0;i < N;i++) {
                    aux[count[a[i].charAt(d)]++] = a[i];
                }
                for (int i = 0;i < N;i++) {
                    a[i] = aux[i];
                }
            }
        }
    
        public static void main(String[] args) {
            String[] a = {
                    "4PGC938",
                    "2IYE230",
                    "3CIO720",
                    "1ICK750",
                    "1OHV845",
                    "4JZY524",
                    "1ICK750",
                    "3CIO720",
                    "1OHV845",
                    "1OHV845",
                    "2RLA629",
                    "2RLA629",
                    "3ATW723"
            };
            int w = 7;
            sort(a,w);
            for (int i = 0;i < a.length;i++) {
                System.out.println(a[i]);
            }
    
        }
    }
    
    

    输出:
    在这里插入图片描述

    展开全文
  • JAVA-基数排序代码(低位优先) 基数排序与计数排序相似。 首先比较个位数大小–然后比较十位数大小–然后比较百位数大小… 这样我们就应该先算出数组中的最大值是多少位 计算数组的最大位数的代码为: int[] arr = ...
  • /* 低位优先排序:将字符串进行低位优先排序(试用情况: 字符串的长度相同) * 参数:a:参与排序的字符串数组,N:字符串中元素的个数 * 返回值:无 */ void LSD(string *a, int N) { int W = a[0].length(), R = 256;...
  • LSD:低位优先的字符串排序,核心思想就是对字符串的每个字符做一次键索引排序 #include <iostream> #include <utility> #include <vector> #include <string> using namespace std; int...
  • 低位优先基数排序对下列字符串进行排序。 Input 输入包含两行,第一行为列表中元素个数n,第二行为列表中的元素。 本题列表中的元素都是包含三个字母的英文单词。 Output 1.输出排序后的字符串序列。 2.中间用空格...
  • 字符串排序-低位优先(LSD)

    千次阅读 2016-05-07 17:23:24
    在介绍低位优先的字符排序之前先介绍一下“键索引计数法”,有下面一组数据:  姓名 组号 "Anderson" 2 "Brown" 3 "Davis" 3 "Garcia" 4 "Harris" 1
  • bool isXiaoDuan()//是小端返回1 否则返回0; { int a=1; return *((char *)(&a)) == (char)a; } bool isDaDuan()//是大端返回1,否则返回0; { nt a=1; return *((char *)(&......
  • 时间有限,这篇博客就只介绍下低位优先的字符串排序算法。核心思想是:键索引计数。它稳定性很强,就是说键相同的元素在排序后会被聚集在一起,但是相对顺序没有变化。 本博客代码示例均来自:算法 Algorithmes For...
  • 考虑一个short整数0x3132(0x32是低位,0x31是高位),把它赋值给一个short变量,那么它在内存中的存储可能有两种不同的方式。  对于.net 直接用BitConverter的IsLittleEndian属性来判断。 Int16可以这样处理:  ...
  • 高位优先与低位优先

    千次阅读 2012-08-10 15:04:54
    在微处理器中,象long/DWORD(32 bits) 0x12345678 这样的数据总是按照高位优先(BIG ENDIAN)方式存放的。但在内存中,数据存放顺序则因微处理器厂商的不同而不同。 数据大小的不同: Byte:一个字节,标记为byte 0 ...
  • 注意: 1、数组实现有点浪费空间,但是好在写起来简单; 2、num数组记录桶内元素个数,循环一次初始化一次; 3、T为桶,也就是临时数组,最后倒回原数组,在下一次循环初始化 实现原理:先按个位排序,放到对应的个...
  • 低位优先的字符串排序相当于是对键索引计数方法的一个扩展,主要用于处理固定长度字符串,比如说手机号,固定电话,银行卡卡号,字符串的长度为N,从右向左开始进行每个键作为值开始遍历,实现比较简单: -(void)...
  • 我认为低位优先字符串排序比较重要的思想: 构建字母表,将要排序的对象中包含的所有字符组成String ,输入字母表中。字母表的顺序,就是后面排序的顺序。建立字符和索引的关系,方便两向查询。 索引计数...
  • 低位优先的字符串排序 用于等长字符串中,比如电话号码,IP地址等。 如果字符串的长度为W,那就从右向左以每个位置的字符串作为键,用键索引计数法将字符串排序W遍。 代码实现 #include &amp;lt;stdio.h...
  • 文章目录造轮子博客链接我的理解代码实现测试字符串示例实现效果 造轮子博客链接 算法第四版C++算法实现全集 我的理解 C++ 字符串排序 键索引计数法排序示例代码实现+算法理解(第五章) 其实就是上一个键排序的...
  • 高位优先和低位优先

    2010-03-23 10:24:19
    java基础比较差,请教各位几个问题。 什么叫做高位优先? 什么叫做低位优先? 高位优先和低位优先的应用场合? 汉字用低位优先存放是怎么写法? 汉字用低位优先读取是怎么写法? 谢谢~~
  • 小白学算法3.1——低位优先字符串排序标签: 小白学算法 博客本节内容总结自《算法(第4版)》5.1节1.低位优先字符串排序相比较于数字,字符串在生活中出现的频率更高,更常用,如姓名、车牌和电话号码等,而字符串...
  • 所以可以按照位进行低位优先的排序 public class Exercise3 { private static int R = 2;//二进制只要2个符号 private static int[] aux; //辅助数组 private static void Sort(int[] a) { if(a.length ) ...
  • 这里是判断底层的硬件是高位优先还是低位优先: 1. 首先分配一块内存 2. 然后将一个long存放到该内存区域 3. 从该内存区域中取出该数据的一个字节 4. 根据该字节判断是否是高位或低位优先  转载于:...
  • 低位字符优先算法的基础就是键索引计数法,他的思想是从后往前对每一个字符为键都进行键索引计数排序,直到当前所选择的键为第一个字符,这样就要求全部字符串的比较部分一定是连续且相等长度的。 思路: 1.在外部...
  • 原理日后有空补上。今天该回宿舍了- - 此版本可实现相同长度的字符串数组,不同长度稍加改动即可。 C++代码如下: #include #include using namespace std;...void LSD(string a[], int size,int W) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,554
精华内容 5,821
关键字:

低位优先