“This is the 12th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

Radix sort

All the values to be compared are unified into the same digit length, and the digits with shorter digits are supplemented with zero. Then, starting with the lowest order, the order is sorted once. After sorting from the lowest to the highest bits, the sequence becomes an ordered sequence.

The cardinality sorting method can be LSD (Least Significant Digital) or MSD (Most Significant Digital). LSD starts with the right Most significant key, while MSD starts with the left Most significant key. This paper adopts LSD to sort.

For example: sort arrays 53,3,542,748,14,214 in ascending order using radix sort:

First, we initialize 10 arrays (buckets) and place them into an array. The buckets have 10 subscripts from 0 to 9, representing the number of bits.

The first round of sorting: the buckets are allocated according to the values of the units digit, and put into the buckets with corresponding subindices according to the values of the units digit, as shown in the figure below. Then, the buckets from 0 to 9 are taken out in sequence (first-in, first-out) and put back into the array. At this time, the order of the array is 542,53,3,14,214,748

The second round of sorting: first empty the data in the bucket, then allocate the bucket according to the value of the ten digit, put it into the bucket with the corresponding subindex according to the value of the ten digit, as shown in the figure below, and then take out the 10 buckets from 0 to 9 in order of adding (first-in, first-out), and put it back into the array. At this time, the order of the array is 3,14,214,542,748,53

Third round sorting: first empty the data in the bucket, then allocate the bucket according to the value of the hundreds, and put the bucket with the corresponding index according to the value of the hundreds, as shown in the figure below. Then take out the 10 buckets from 0 to 9 in order of adding (first-in, first-out), and put them back into the array. At this time, the order of the array is 3,14,53,214,542,748

Cardinality sort complete code

-(void)radixSort:(NSMutableArray*)arr{//1. Int Max = [self getMaxBit:arr]; NSMutableArray<NSMutableArray*> * bucket = [NSMutableArray New]; //2. Initialize a bucket. for (int i = 0; i<10; i++) { NSMutableArray*a = [NSMutableArray array]; [bucket addObject:a]; } int index = 1; int flag = 0; While (flag < Max) {flag ++; For (int I = 0; int I = 0; i<arr.count; i++) {//5612 int value = [arr[i] intValue] / index % 10; [bucket[value] addObject:arr[i]]; [arr removeAllObjects]; [arr removeAllObjects]; for (int i = 0; i<bucket.count; i++) { NSMutableArray*bucketItem = bucket[i]; while (bucketItem.count>0) { [arr addObject:bucketItem[0]]; [bucketItem removeObjectAtIndex:0]; } } index = index*10; } // getMaxBit (NSMutableArray*)arr{int Max = [arr[0] intValue]; for (int i = 1; i<arr.count; i++) { if (max<[arr[i] intValue]) { max = [arr[i] intValue]; } } NSString*str = [NSString stringWithFormat:@"%d",max]; return (int)str.length; }Copy the code

Performance of radix sort

D for array elements with the highest number of digits, and n for the number of elements.

Other sorting algorithms

Sorting algorithm :1) Direct insertion sort

Sorting algorithm :2) Hill sort

Sorting algorithm :3) Bubble sort

Sorting algorithm :4) quick sort

Sorting algorithm :5) select sorting

Sorting algorithm :6) merge sort

Sorting algorithm :7) radix sort

Sorting algorithm :8) heap sort