This is the fourth day of my participation in the August Text Challenge.More challenges in August
Count sorting
Preface:
This is a way of sorting without comparison, but is a huge waste of space. (Write embedded partners will be angry!)
Principle:
The number of occurrences of each integer in the sequence is counted and the index of each integer in the ordered sequence is derived
Example:
Int Max = array[0]; int Max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; Int [] counts = new int[1 + Max]; For (int I = 0; i < array.length; i++) { counts[array[i]]++; Int index = 0; // int index = 0; for (int i = 0; i < counts.length; i++) { while (counts[i]-- > 0) { array[index++] = i; } } // O(n)Copy the codeAlgorithm analysis:
The implementation of this version has the following problems: it cannot sort negative integers; Extremely waste of memory space; It’s an unstable order.
(The people who use this are amazing.)
Counting sort – improved thinking
Originally we used the index of the array as the value of the original sequence, but there are no negative numbers in the array, so there is no way to compare negative numbers in the sequence.
Now let’s take the first position in the array which is the smallest number in the sequence, and take advantage of the difference between that number and the array index,
If you can’t solve negative numbers, let’s solve instability
Int Max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; Int [] counts = new int[max-min + 1]; For (int I = 0; i < array.length; i++) { counts[array[i] - min]++; } for (int I = 1; i < counts.length; i++) { counts[i] += counts[i - 1]; Int [] newArray = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) { newArray[--counts[array[i] - min]] = array[i]; } // Assign an ordered array to array for (int I = 0; i < newArray.length; i++) { array[i] = newArray[i]; }}Copy the codeRadix sort
Preface:
Radix sort, the so-called radix is his ones place, tens place, hundreds place, through the order of ten thousands of each digit size, finally get the size of all the digits.
Principle:
Radix sort is very suitable for integer sort (especially for non-negative integers), so we only demonstrate the radix sort execution flow for non-negative integers: the ones digit, the tens digit, the hundreds digit, the thousands digit, the tens digit… Sort (from lowest to highest)
When sorting digits, we use counting sort
Example:
Int Max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; }} // Single digit: Array [I] / 1%10 = 3 // ten: array[I] / 10%10 = 9 // hundreds: array[I] / 100%10 = 5 // thousands: array[I] / 1000%10 =... for (int divider = 1; divider <= max; divider *= 10) { countingSort(divider); } protected void countingSort(int Divider) {int[] counts = new int[10]; For (int I = 0; i < array.length; i++) { counts[array[i] / divider % 10]++; } for (int I = 1; i < counts.length; i++) { counts[i] += counts[i - 1]; Int [] newArray = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) { newArray[--counts[array[i] / divider % 10]] = array[i]; } // Assign an ordered array to array for (int I = 0; i < newArray.length; i++) { array[i] = newArray[i]; }}Copy the codeRadix sort – another way to think about it
So let’s put it vertically in the units digit
Then, we put the numbers through one by one, and at the end of the day, we’ll have the sequence
Example:
Int Max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; Int buckets[][]=new int[10][array.length]; Int bucketSizes[]=new int[buckets. Length]; for (int divider = 1; divider <= max; divider *= 10){ for (int i=0; i<array.length; i++){ int a=array[i] / divider % 10; buckets[a][bucketSizes[a]++]=array[i]; } int index=0; for (int i=0; i<buckets.length; i++){ for (int j=0; j<bucketSizes[i]; j++){ array[index++]=buckets[i][j]; } bucketSizes[i]=0; }}Copy the code