Implementing Radix Sort Algorithm in Java
Radix sort is a non-comparison integer sorting algorithm that processes digits from the least significant to the most significant. It distributes each number into "buckets" based on the current digit, then collects them back into the original array in bucket order, repeating until all digits are processed. It is suitable for integers with few digits and has high efficiency. The basic idea is "distribute-collect-repeat": distribute numbers into corresponding buckets by the current digit (units, tens, etc.), collect them back into the array in bucket order, and repeat for all digits. Taking the array [5, 3, 8, 12, 23, 100] as an example, it is sorted after three rounds of processing: units, tens, and hundreds. In Java code, the maximum number determines the highest digit, and `(num / radix) % 10` is used to get the current digit. ArrayLists are used as buckets to implement distribution and collection. The time complexity is O(d(n+k)) (where d is the number of digits of the maximum number and k=10), and the space complexity is O(n+k). This algorithm is stable and suitable for integer sorting. Negative numbers can be separated into positive and negative groups, sorted separately, and then merged.
Read MoreImplementing the Insertion Sort Algorithm in Java
Insertion sort is a simple and intuitive sorting algorithm. Its core idea is to insert unsorted elements one by one into their correct positions in the sorted part, similar to organizing playing cards. It is suitable for small-scale data and has a simple implementation. Basic idea: Starting from the second element, mark the current element as the "element to be inserted". Compare it with the elements in the sorted part from back to front. If the sorted element is larger, shift it backward until the insertion position is found. Repeat this process until all elements are processed. In Java implementation, the element to be inserted needs to be saved, and the insertion is completed by looping through comparisons and shifting elements backward. The time complexity of the algorithm is: best O(n) (when already sorted), worst and average O(n²); space complexity O(1) (in-place sorting); stable sort, suitable for small-scale data or nearly sorted data. Its core lies in "gradual insertion", with simple implementation. Its stability and in-place nature make it perform well in small-scale sorting.
Read More