CrLf

好像还可以继续优化，可惜没有微秒和纳秒，比较不出来

GNU

回复 16# CrLf


PowerShell的 Measure-Command 可以获取到 Ticks
1 Ticks = 100 纳秒 = 1/10000 毫秒

523066680

回复 17# GNU


      他们当然知道如何获取更详细的时间单位，说的是那个网站的在线测试的时间单位精度有限。
再说线下比较还可以增加测试次数和列表数据量。所以不同的结论需要结合前后文(Context)。

happy886rr

回复 11# 523066680
是否可以用快速排序

523066680

回复 19# happy886rr


    ? 贴了一个别人的，好像是快速排序

aa77dd@163.com

C

void q_sort(char* arr[], const int len) {

    typedef struct _Range {
        int start, end;
    } Range;

    Range new_Range(int s, int e) {
        Range r;
        r.start = s;
        r.end = e;
        return r;
    }

    if (len <= 0)
        return;

    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        char* mid = arr[range.end], * cp;
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (GTR(mid, arr[left]) && left < right)
                left++;
            while (!GTR(mid, arr[right]) && left < right)
                right--;
            cp = arr[left], arr[left] = arr[right], arr[right] = cp;
        }
        if (!GTR(mid, arr[left]))
            cp = arr[left], arr[left] = arr[range.end], arr[range.end] = cp;
        else
            left++;
        r[p++] = new_Range(range.start, left - 1);
        r[p++] = new_Range(left + 1, range.end);
    }
}

int GTR(char* s1, char* s2) {

    char * p1 = s1, * p2 = s2;

    while (1) {

        if (!*p1 && !*p2) return 1;

        if (!*p1) p1 = s2;

        if (!*p2) p2 = s1;

        if (*p1 > *p2)
            return 1;
        else if (*p1 < *p2)
            return 0;
        else p1++, p2++;

    }
}

char* largestNumber(int* nums, int numsSize) {

    char strs [numsSize][11], * strPtrs[numsSize], * cp1, * cp2, * strRet = malloc(10 * numsSize + 1), ch;

    int i, j, k, t;

    for (i = 0; i < numsSize; i++) {

        t = *(nums + i);
        j = 0;
        k = -1;

        // digits convert to string
        do {
            strs[i][j++] = '0' + t % 10;
        } while ((t /= 10) > 0);
        strs[i][j] = '\0';

        // reverse string
        *(strPtrs + i) = cp1 = *(strs + i);
        while (--j > ++k)
            * (cp1 + j) ^= *(cp1 + k), * (cp1 + k) ^= *(cp1 + j), * (cp1 + j) ^= *(cp1 + k);

    }

    q_sort(strPtrs, numsSize);

    // printf("After q_sort\n");
    // for (i = numsSize - 1; i >= 0; i--) printf("%s\n", strPtrs[i]);

    cp2 = strRet;

    if (strPtrs[numsSize - 1][0] == '0') {
        *strRet = '0';
        *(strRet + 1) = '\0';
        return strRet;
    }

    for (i = numsSize - 1; i >= 0; i--) {

        cp1 = *(strPtrs + i);
        while (ch = *(cp1++)) *(cp2++) = ch;

    }
    *cp2 = '\0';

    return strRet;
}
复制代码

CrLf

回复 19# happy886rr


    感觉排序方式不是最重要的，个人经验，结构优化的收益远比冒泡和快速排序之间的效率差异大得多：

1、用结构体 struct_num 保存数字和进位，排序时用 (long long) 数值比较大小，等到输出时再转为字符串
2、分设 10 个数组 hash 表，用于保存由 0-9 开头的数字组成的数组，这样只需要对 1-9 各组单独排序即可
3、函数自实现/内联，就题解题，节省函数调用开销
复制代码

aa77dd@163.com

回复 22# CrLf

没仔细看你的代码, 估计用到了这种方式

比较 830 和 8308

预处理时, 计算出了大于 各数位数 的最小的 10 的幂
830(1000), 8308(10000)

比较时:
互相乘以对方的特征幂 再加上对方, 得到等位数拼接串:

830 * 10000 + 8308 <--> 8308 * 1000 + 830

最后得到比较结果
为防止 int 类型溢出, 必须用超出 int 范围的类型处理

字符数组指针方式比较仍然烦琐

aa77dd@163.com

回复 3# CrLf

多测试几次就能做到, 我用同一个代码提交了多次

最慢时 184ms, 最快时 116ms

在 my submissions 里记录了每一次提交测试的结果

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    

nums = nums.map(function(num) {
  return '' + num;
});
    

    var rs=[],re=[],p=0;
    rs[p] = 0;
    re[p++]= nums.length-1;

    var ss,ee,t;
    while (p) {

        ss = rs[--p];
        ee = re[p];

        if (ss >= ee)
            continue;

        var mid = nums[ee];

        var left = ss, right = ee - 1;
        while (left < right) {
            while (nums[left] + mid > mid + nums[left] && left < right)
                left++;
            while (mid + nums[right] >= nums[right] + mid && left < right)
                right--;
            t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
        }
        if (mid + nums[left] >= nums[left] + mid) {
            t = nums[left];
            nums[left] = nums[ee];
            nums[ee] = t;
        } else
            left++;

        rs[p] = ss;
        re[p++] = left - 1;

        rs[p] = left + 1;
        re[p++] = ee;

    }
    if (nums[0] == 0) return '0';
    return nums.join('');
};
复制代码

xxpinqz

为啥你们脑袋这么好使呢，在这论坛混了这么久，还是只会bat。

523066680

回复 25# xxpinqz

个人意见：
    多学几种语言，批处理之后，推荐ruby 或者 python，最好先熟悉C语言。
然后如果要自己打造应用，C# 或者 C++

刚工作那会儿有大量时间，我很后悔在批处理特效上面花太多时间，我不是说特效没卵用，而是搞图形的话应该一开始就上C/C++，可惜，当时缺少视野。
然后花了小量时间学Python，放弃后转而投入大量业余时间学Perl，这是手感上和批处理最像的。不过我觉得时间成本不太划算，C#、C++可以做更多的事。

最后，关于语言的吐槽，推荐一本书：《程序员的呐喊》

xxpinqz

回复 26# 523066680

过谦了。
谢谢你的建议。奶瓶、尿布得花费好大精力了，实在力所不及。
学无先后，达者为师。你也不必介怀当年所耗费精力，毕竟假设的条件就是假设。
而且也说不准你这学习的精神就是你当年留下的烙印。况且能在喜欢的事情上下功夫，本身就是一种乐趣~
发现本帖跑题的都是我~~~

这书在豆瓣上评价不错，有空看看，爱看书，但都是0.1桶水。。

CrLf

回复 24# aa77dd@163.com


    要看稳定值，我看到120毫秒那个档很集中，绝不是偶然，一定有什么我还没想到的办法

codegay

回复 26# 523066680


    这书扫完了。这作者的套路就是放地图炮喷或者狂奶某个语言，然后再指责别人狂热不可理喻，能在言语上无论如何都让自己站在比较优越的位置。本身就是个语言宗教粉，但是会标榜自己是自由主义。

happy886rr

故题重游，C语言版：
Submission Details
221 / 221 test cases passed.
Status: Accepted
Runtime: 0 ms

char outStr[];
int CompNums(const void* a, const void* b){
	char* str1=*(char**)a;
	char* str2=*(char**)b;
	int i, L1=strlen(str1), L2=strlen(str2);
	for(i=0; i<10; i++){
		if(*str1=='\0'){str1-=L1;}
		if(*str2=='\0'){str2-=L2;}
		if(*str1 != *str2){break;}
		str1++, str2++;
	}
	return *str2-*str1;
}
char* largestNumber(int* nums, int numsSize) {
	int i;
	outStr[0]=0;
	char* p[numsSize];
	for(i=0; i<numsSize; i++){p[i]=(char*)malloc(sizeof(char)*16);sprintf(p[i], "%d\0", nums[i]);}	
	qsort(p, numsSize, sizeof(char*), CompNums);
	for(i=0; i<numsSize; i++){strcat(outStr, p[i]);}
	return outStr[0]=='0'?"0":outStr;
}
复制代码

>>>
补充，针对本帖所有回帖的C代码，在100万次的测试当中，只有21楼aa77dd@163.com兄的代码速度最快，100万次耗时0.7秒，本人用itoa函数也只能做到100万次耗时1.1秒。其他C语言方案均耗时数秒，并且存在严重漏洞。
>>>
另外小于5000次的测试根本无法体现性能，几乎都是0毫秒。只在百万次的测试上个别方案才会出现极大的漏洞。