对大整数排序-yiteyi-C++库

给定一系列 N 正整数，其中每个整数最多可以有10位数字 ^6. ，按升序打印数组元素。

null

Input: arr[] = {54, 724523015759812365462, 870112101220845, 8723} Output: 54 8723 870112101220845 724523015759812365462Explanation:All elements of array are sorted in non-descending(i.e., ascending)order of their integer valueInput: arr[] = {3643641264874311, 451234654453211101231,                4510122010112121012121}Output: 3641264874311 451234654453211101231 4510122010112121012121

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 幼稚的方法 是使用任意精度的数据类型，例如智力用python或 大整数 用Java编写的类。但这种方法不会有成效，因为字符串到int的内部转换，然后执行排序，将导致二进制系统中加法和乘法的计算速度减慢。 高效的解决方案： 由于整数的大小非常大，所以它甚至无法容纳 好久好久 C/C++的数据类型，所以我们只需要将所有数字作为字符串输入，并使用比较函数对它们进行排序。以下是比较功能的要点：-

如果两个字符串的长度不同，那么我们需要比较长度来决定排序顺序。
如果长度相同，那么我们只需要按字典顺序比较两个字符串。

假设：没有前导零。

C++

                         // Below is C++ code to sort the Big integers in                       
                         // ascending order                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // comp function to perform sorting                       
                         bool                                     comp(                                     const                                     string &left,                                     const                                     string &right)                       
                         {                       
                                                 // if length of both string are equals then sort                       
                                                 // them in lexicographically order                       
                                                 if                                     (left.size() == right.size())                       
                                                 return                                     left < right;                       
           
                                                 // Otherwise sort them according to the length                       
                                                 // of string in ascending order                       
                                                 else                       
                                                 return                                     left.size() < right.size();                       
                         }                       
           
                         // Function to sort arr[] elements according                       
                         // to integer value                       
                         void                                     SortingBigIntegers(string arr[],                                     int                                     n)                       
                         {                       
                                                 // Copy the arr[] elements to sortArr[]                       
                                                 vector<string> sortArr(arr, arr + n);                       
           
                                                 // Inbuilt sort function using function as comp                       
                                                 sort(sortArr.begin(), sortArr.end(), comp);                       
           
                                                 // Print the final sorted array                       
                                                 for                                     (                                     auto                                     &ele : sortArr)                       
                                                 cout << ele <<                                     " "                                     ;                       
                         }                       
           
                         // Driver code of above implementation                       
                         int                                     main()                       
                         {                       
                                                 string arr[] = {                                     "54"                                     ,                                     "724523015759812365462"                                     ,                       
                                                 "870112101220845"                                     ,                                     "8723"                                     };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 SortingBigIntegers(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

python

                         # Below is Python code to sort the Big integers                       
                         # in ascending order                       
                         def                                     SortingBigIntegers(arr, n):                       
                                   
                                                 # Direct sorting using lamda operator                       
                                                 # and length comparison                       
                                                 arr.sort(key                                     =                                     lambda                                     x: (                                     len                                     (x), x))                       
           
                         # Driver code of above implementation                       
                         arr                                     =                                     [                                     "54"                                     ,                                     "724523015759812365462"                                     ,                       
                                                 "870112101220845"                                     ,                                     "8723"                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         SortingBigIntegers(arr, n)                       
           
                         # Print the final sorted list using                       
                         # join method                       
                         print                                     " "                                     .join(arr)                       

Javascript

                         <script>                       
                         // Below is Javascript code to sort the Big integers in                       
                         // ascending order                       
           
                         // comp function to perform sorting                       
                         function                                     comp(left, right)                       
                         {                       
           
                                                 // if length of both string are equals then sort                       
                                                 // them in lexicographically order                       
                                                 if                                     (left.length == right.length)                       
                                                 return                                     left < right;                       
           
                                                 // Otherwise sort them according to the length                       
                                                 // of string in ascending order                       
                                                 else                       
                                                 return                                     left.length - right.length;                       
                         }                       
           
                         // Function to sort arr[] elements according                       
                         // to integer value                       
                         function                                     SortingBigIntegers(arr, n)                       
                         {                       
           
                                                 // Copy the arr[] elements to sortArr[]                       
                                                 let sortArr = [...arr]                       
           
                                                 // Inbuilt sort function using function as comp                       
           
                                                 sortArr.sort(comp);                       
           
                                                 // Print the final sorted array                       
                                                 for                                     (ele of sortArr)                       
                                                 document.write(ele +                                     " "                                     );                       
                         }                       
           
                         // Driver code of above implementation                       
                         let arr = [                                     "54"                                     ,                                     "724523015759812365462"                                     ,                       
                                                 "870112101220845"                                     ,                                     "8723"                                     ]                       
                         let n = arr.length                       
           
                         SortingBigIntegers(arr, n);                       
           
                         // This code is contributed by gfgking.                       
                         </script>                       

Output: 54 8723 870112101220845 724523015759812365462

时间复杂性： O（sum*log（n）），其中sum是所有字符串长度的总和，n是数组的大小 辅助空间： O（n） 类似帖子： 对大数数组排序本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章