Sorting algorithm (third bomb) sorted by sorting and base (barrel) - base, bomb, bucket, SORT, Sort algorithm, SORTING, Third

Merge and sort

Sorting animation demo

The overall effect:

span>

Sorting details:

The principle of sorting:

Merge sorting means recursively splitting the original array in half Until it can no longer be divided (only one element is left), start to merge and sort upwards from the smallest array

1. Merge upwards When sorting, a temporary storage array is needed for sorting,

2. Compare the two arrays to be merged starting from the first place, put the smaller one in the temporary storage array, and move the pointer backward,

3. Until one of the arrays is empty, at this time, there is no need to judge which array is empty, and the remaining elements of the two arrays are directly appended to the temporary storage array.

4. Put the sorted elements of the temporary storage array into the original array. The two arrays are combined into one, and the trip is over.

My code implementation:

1 package cn.ftf.mysort; 2
3 import java.util.Arrays; 4
5 public class MyMergeSort { 6 //Improve parameters and call externally
7 public static int[] mergeSort(int[] arr) { 8 int [] temp=new int[arr .length]; 9 arr=mergeSort1(arr,0,arr.length-1 ,temp); 10 return arr; 11 } 12 //divide+conquer
13 private static int[] mergeSort1(int[] arr,int left,int right,int[] temp) {14 if(left<right) {15 int mid=(left+right)/2; 16 // divide left + rule
17 mergeSort1(arr,left,mid,temp); 18 //divide to the right + rule
19 mergeSort1(arr,mid+1,right,temp); 20 merge(arr,left,mid,right,temp); 21 } 22 return arr; 23 } 24 //Treatment
25 private static int[] merge(int[] arr,int left,int mid,int right,int[] temp) {26 System.out.println("Three boundary values: "+left+" "+mid+" "+right); 27 System.out.println(); 28 int i=left; 29 int j=mid+1; 30 int t=0; //Subscript of temporary array
31 while(i<=mid&&j<=right) {32 if(arr [i]<=arr[j]) {33 temp[t]=arr[i]; 34 i++ ; 35 t++; 36 }else {37 temp[t]=arr[j]; 38 j++; 39 t++; 40 } span>41 } 42 while(i<=mid) {43 temp[t]=arr[i]; 44 i++; 45 t++; 46 } 47 while(j<=right) {48 temp[t]=arr[j]; 49 j++; 50 t++; 51 } 52 //The following will copy the sorted temp array to the arr array
53 int arrLeft=left; 54 t=0; 55 while(arrLeft<=right) {56 arr[arrLeft]=temp[t]; 57 t++; 58 arrLeft++; 59 } 60 return arr; 61 } 62 public static void main(String[] args) {63 int [] arr= {1,7,8,9,12,2,6,10,14,18,1}; 64 arr=mergeSort(arr); 65 System.out.println(Arrays.toString(arr)); 66 } 67 }

Complexity analysis:

1. Time complexity: Regardless of whether the original array is ordered or not, it must be recursively separated and merged up and sorted, so the time complexity is always O(nlog₂n)

2. Space complexity: every time two arrays are merged and sorted, Use an array of length n as a supplement The helper array is used to save the combined sequence, so the space complexity is O(n)



Base (bucket) sorting:

Sorting algorithm diagram:

The sorting principle: [ j=1-10) in the queue, and then take out the data from the ten queues and put it back into the original array until i is greater than the maximum number of digits to be queued.

1. The maximum number of digits in the array is n, so it needs to be arranged n times. For example, the largest number in the array is 3 digits, you need to line up 3 times.

2. If there are m numbers in the array, ten arrays of length m are needed (j=0-9 ) Is used to temporarily store the number with the number j in the i digit. For example, in the first pass, the number of digits 0 will be allocated to the temp0 array, and the number of digits 1 will be allocated to the temp1 array… .

3. After the allocation is over, the data will be taken out from the tempj array in turn, following the advanced principles, for example, for the array {1 ,11,2,44,4}, after the first allocation, temp1={1,11}, temp2={2}, temp4={44,4}, after taking out the elements in sequence {1,11,2, 44, 4}, the end of the first pass

4. End after looping to n times, the sorting is complete p>

My code implementation:

 1 package cn.ftf.mysort; 2 /*
3 * Cardinality sorting (bucket sorting) 4 */
5 import java.util.Arrays; 6
7 public class MyRadixSort { 8 public static void radixSort(int[] arr) { 9 int bucket[][]=new int[10][arr.length]; 10 int maxCount=arr[0]; 11 for(int i=1;i) {12 if(maxCount< arr[i]) {13 maxCount=arr[i]; 14 } 15 } 16 //System.out.println("the maxCount is = "+maxCount);
17 int maxLength=(maxCount+"").length(); 18 //System.out.println("the maxLength is = "+maxLength);
19 int[] bucketElementCount=new int[10]; 20 for(int i= 0,n=1;i) {21 for(int j=0;j) {22 int compareValue =(arr[j]/n)%10; 23 bucket[compareValue][ bucketElementCount[compareValue]]=arr[j]; 24 bucketElementCount[compareValue]++; 25 } 26 int arrIndex=0; 27 for(int k=0;k<10;k++) {28 if(bucketElementCount[k]!=0) { 29 for(int span> l=0;l) {30 arr [arrIndex++]=bucket[k][l]; 31 } 32 } 33 bucketElementCount[k]=0; 34 } 35 } 36 } 37 public static void main(String[] args) {38 int [] arr= {53,3,542,748,14,214}; 39 radixSort(arr); 40 System.out.println(Arrays.toString(arr)); 41 } 42 }

Complexity analysis:

1. Time complexity:

　　 Each bucket allocation of keywords is required O(n) time complexity, and obtaining a new key sequence after allocation requires O(n) time complexity.

If the data to be sorted can be divided into d keywords, the time complexity of the cardinal sorting will be O(d*2n ), of course, d is much smaller than n, so it is basically linear.

The coefficient 2 can be omitted, and no matter whether the array is ordered or not, it needs to be ranked from the ones digit to the largest digit, so the time is complicated The degree is always O(d*n). Among them, n is the length of the array and d is the maximum number of digits.

2. Space complexity:

The space complexity of 　　 cardinality sorting is O(n+k), where k is the number of buckets, and n numbers need to be allocated.

Merge sorting and cardinal sorting speed test:

1 import cn.ftf.mysort.MyBubbleSort; 2 import cn.ftf.mysort.MyChooseSort; 3 import cn.ftf.mysort.MyInserSort; span> 4 import cn. ftf.mysort.MyMergeSort; 5 import cn.ftf.mysort.MyQuickSort; 6 import 6 import span> cn.ftf.mysort.MyRadixSort; 7 import cn.ftf.mysort.MyShellSort; 8 /*
9 * My sorting algorithm speed test10 */
11 public class MySortText {12 public static void main(String[] args) {13 int[] arr; 14 arr= new int[8000000]; 15 for(int i =0; i < 8000000;i++) {16 arr[i] = (int)(Math.random() * 10000); 17 } 18 firstTime=System.currentTimeMillis(); 19 MyMergeSort.mergeSort(arr); 20 secondTime=System.currentTimeMillis(); 21 System.out.println("Merge and sort time:"+(secondTime-firstTime)); 22
23 arr=new int[8000000]; 24 for(int i =0; i <8000000;i++ ) {25 arr[i] = (int)(Math. random() * 10000); 26 } 27 firstTime=System.currentTimeMillis(); 28 MyRadixSort.radixSort(arr); 29 secondTime=System.currentTimeMillis(); 30 System.out.println("Sequence of base number:"+(secondTime-firstTime)); 31 } 32
33 }

Test results:

Using merge sorting and cardinal sorting:

Used when sorting large amounts of data There are many quick sorts, and both merge sort and cardinal sort are stable sorting algorithms. The radix sort is much faster than the previous sorting algorithm, but it is implemented at the cost of taking up a lot of extra memory.

1 package cn.ftf.mysort; 2
3 import java.util.Arrays; 4
5 public class MyMergeSort { 6 //Improve parameters and call externally
7 public static int[] mergeSort(int[] arr) { 8 int [] temp=new int[arr .length]; 9 arr=mergeSort1(arr,0,arr.length-1 ,temp); 10 return arr; 11 } 12 //divide+conquer
13 private static int[] mergeSort1(int[] arr,int left,int right,int[] temp) {14 if(left<right) {15 int mid=(left+right)/2; 16 // divide left + rule
17 mergeSort1(arr,left,mid,temp); 18 //divide to the right + rule
19 mergeSort1(arr,mid+1,right,temp); 20 merge(arr,left,mid,right,temp); 21 } 22 return arr; 23 } 24 //Treatment
25 private static int[] merge(int[] arr,int left,int mid,int right,int[] temp) {26 System.out.println("Three boundary values: "+left+" "+mid+" "+right); 27 System.out.println(); 28 int i=left; 29 int j=mid+1; 30 int t=0; //Subscript of temporary array
31 while(i<=mid&&j<=right) {32 if(arr [i]<=arr[j]) {33 temp[t]=arr[i]; 34 i++ ; 35 t++; 36 }else {37 temp[t]=arr[j]; 38 j++; 39 t++; 40 } 41 } 42 while(i<=mid) { 43 temp[t]=arr[i]; 44 i++; 45 t++; 46 } 47 while(j<=right) { 48 temp[t]=arr[j]; 49 j++; 50 t++; 51 } 52 //下面将排好序的temp数组copy到arr数组中
53 int arrLeft=left; 54 t=0; 55 while(arrLeft<=right) { 56 arr[arrLeft]=temp[t]; 57 t++; 58 arrLeft++; 59 } 60 return arr; 61 } 62 public static void main(String[] args) { 63 int [] arr= {1,7,8,9,12,2,6,10,14,18,1}; 64 arr=mergeSort(arr); 65 System.out.println(Arrays.toString(arr)); 66 } 67 }

1 package cn.ftf.mysort; 2 /*
3 * 基数排序（桶排序） 4 */
5 import java.util.Arrays; 6
7 public class MyRadixSort { 8 public static void radixSort(int[] arr) { 9 int bucket[][]=new int[10][arr.length]; 10 int maxCount=arr[0]; 11 for(int i=1;i) { 12 if(maxCount<arr[i]) { 13 maxCount=arr[i]; 14 } 15 } 16 //System.out.println("the maxCount is = "+maxCount);
17 int maxLength=(maxCount+"").length(); 18 //System.out.println("the maxLength is = "+maxLength);
19 int[] bucketElementCount=new int[10]; 20 for(int i=0,n=1;i) { 21 for(int j=0;j) { 22 int compareValue=(arr[j]/n)%10; 23 bucket[compareValue][bucketElementCount[compareValue]]=arr[j]; 24 bucketElementCount[compareValue]++; 25 } 26 int arrIndex=0; 27 for(int k=0;k<10;k++) { 28 if(bucketElementCount[k]!=0) { 29 for(int l=0;l) { 30 arr[arrIndex++]=bucket[k][l]; 31 } 32 } 33 bucketElementCount[k]=0; 34 } 35 } 36 } 37 public static void main(String[] args) { 38 int [] arr= {53,3,542,748,14,214}; 39 radixSort(arr); 40 System.out.println(Arrays.toString(arr)); 41 } 42 }

1 import cn.ftf.mysort.MyBubbleSort; 2 import cn.ftf.mysort.MyChooseSort; 3 import cn.ftf.mysort.MyInserSort; 4 import cn.ftf.mysort.MyMergeSort; 5 import cn.ftf.mysort.MyQuickSort; 6 import cn.ftf.mysort.MyRadixSort; 7 import cn.ftf.mysort.MyShellSort; 8 /*
9 * 我的排序算法速度测试 10 */
11 public class MySortText { 12 public static void main(String[] args) { 13 int[] arr; 14 arr=new int[8000000]; 15 for(int i =0; i < 8000000;i++) { 16 arr[i] = (int)(Math.random() * 10000); 17 } 18 firstTime=System.currentTimeMillis(); 19 MyMergeSort.mergeSort(arr); 20 secondTime=System.currentTimeMillis(); 21 System.out.println("归并排序用时："+(secondTime-firstTime)); 22
23 arr=new int[8000000]; 24 for(int i =0; i < 8000000;i++) { 25 arr[i] = (int)(Math.random() * 10000); 26 } 27 firstTime=System.currentTimeMillis(); 28 MyRadixSort.radixSort(arr); 29 secondTime=System.currentTimeMillis(); 30 System.out.println("基数排序用时："+(secondTime-firstTime)); 31 } 32
33 }

Leave a Comment Cancel reply