Insert sort directly

Sorting problems such as inserting new data into an already arranged data column are often encountered.

  • Sort the first and the second, and form an ordered sequence

  • A third number is inserted to form a new ordered sequence.

  • For number four, number five… Repeat step 2 until the last number.

How to code:

  • Int I =1; for(int I =1; i<length; I++), I don’t have to insert that one. < span>

  • Sets the insertion number and gets the number of digits of the last number in the sorted sequence. InsertNum and j = I – 1.

  • The loop starts with the last number and moves the current number back one bit if the number inserted is less than the current number.

  • Place the current number in the empty position, which is j+1.

The code implementation is as follows:

public void insertSort(int[] a){ int length=a.length; // The length of the array is extracted for speed. int insertNum; For (int I =1; i<length; InsertNum =a[I]; Int j= I -1; While (j>=0&&a[j]>insertNum){// The sequence is looped from back to front, and the number greater than insertNum is moved back a[j+1]=a[j]; // The element moves one space j--; } a[j+1]=insertNum; // Place the number to be inserted in the position to be inserted. }}Copy the code

Hill sort

For the direct insertion sort problem, when the amount of data is huge.

  • Set the number of numbers as n, take an odd number k=n/2, divide the numbers with subscript difference of K into a group to form an ordered sequence.

  • Then take k=k/2 and divide the books with subscript difference value of K into a group to form an ordered sequence.

  • Repeat step 2 until k=1 to perform simple insertion sort.

How to code:

  • First determine the number of sub-groups.

  • Then insert sort the elements in the group.

  • Then take length/2 and repeat 1,2 steps until length=0.

The code implementation is as follows:

public void sheelSort(int[] a){ int d = a.length; while (d! =0) { d=d/2; for (int x = 0; x < d; X ++) {for (int I = x+ d; i < a.length; Int j = I - d; int j = I - d; Int temp = a[I]; // Insert element for (; j >= 0 && temp < a[j]; J -= d) {// traverses from back to front. a[j + d] = a[j]; } a[j] = temp; }}}}Copy the code

Simple selection sort

Usually used when taking the largest and smallest numbers in a sequence.

(If every comparison is swapped, then it is swapped sort; If you swap one cycle after each comparison, you are simply selecting sort.

  • Iterate through the sequence, placing the smallest number first.

  • Iterate through the rest of the sequence, placing the smallest number first.

  • Repeat the second step until only one number remains.

How to code:

  • First determine the number of cycles, and remember the current number and position.

  • Compare all the numbers following the current position with the current number, assign the decimal to key, and remember the decimal position.

  • When the comparison is complete, swap the smallest value with the value of the first number.

  • Repeat steps 2 and 3.

The code implementation is as follows:

public void selectSort(int[] a) { int length = a.length; for (int i = 0; i < length; Int key = a[I]; int key = a[I]; int position=i; for (int j = i + 1; j < length; If (a[j] < key) {key = a[j]; position = j; } } a[position]=a[i]; A [I]=key; }}Copy the code

Heap sort

Optimization of simple selection sorting.

  • Build the sequence into a big top heap.

  • Swap the root node with the last node, and then disconnect the last node.

  • Repeat steps 1 and 2 until all nodes are disconnected.

The code implementation is as follows:

Public void heapSort(int[] a){system.out.println (" start sort "); int arrayLength=a.length; For (int I =0; i<arraylength-1; I ++){// Build the heap buildMaxHeap(a,arrayLength-1-i); // Swap (a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } private void swap(int[] data, int i, int j) { // TODO Auto-generated method stub int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } private void buildMaxHeap(int[] data, Int lastIndex) {// TODO auto-generated method stub // Start from the parent of lastIndex for(int I =(lastIndex-1)/2; i>=0; I --){//k saves the node being judged int k= I; While (k*2+1<=lastIndex){int biggerIndex=2*k+1; // If biggerIndex is less than lastIndex, If (data[biggerIndex]<data[biggerIndex+1]){if(data[biggerIndex]<data[biggerIndex+1]){ //biggerIndex always records the index of the larger child node biggerIndex++; } // If (data[k]<data[biggerIndex]){// Swap them (data,k,biggerIndex); // Assign biggerIndex to k to start the next loop of the while loop, reensuring that the value of k is greater than the value of its left and right children k=biggerIndex; }else{ break; }}}}Copy the code

Five, bubble sort

Not usually.

  • Compare all the elements in the sequence in pairs, placing the largest at the end.

  • Compare all elements in the remaining sequence in pairs, placing the largest at the end.

  • Repeat the second step until only one number remains.

How to code:

  • Set the number of cycles.

  • Sets the number of digits to start the comparison and the number of digits to end it.

  • Compare them in pairs and put the smallest one first.

  • Repeat 2 or 3 steps until the number of cycles is up.

The code implementation is as follows:

public void bubbleSort(int[] a){ int length=a.length; int temp; for(int i=0; i<a.length; i++){ for(int j=0; j<a.length-i-1; j++){ if(a[j]>a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }}}}Copy the code

Quicksort

The fastest time required.

  • Pick the first number p, the number less than p on the left, and the number greater than p on the right.

  • Recursively, I’m going to do everything to the left and to the right of P until I can’t recurse.

The code implementation is as follows:

public static void quickSort(int[] numbers, int start, int end) { if (start < end) { int base = numbers[start]; // The selected base value (the first value is the base value) int temp; Int I = start, j = end; do { while ((numbers[i] < base) && (i < end)) i++; while ((numbers[j] > base) && (j > start)) j--; if (i <= j) { temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) quickSort(numbers, start, j); if (end > i) quickSort(numbers, i, end); }}Copy the code

Merge sort

The speed is second only to fast row, used when memory is low, and can be used for parallel computing.

  • Select two adjacent numbers to form an ordered sequence.

  • Select two adjacent ordered sequences to form an ordered sequence.

  • Repeat the second step until it all forms an ordered sequence.

The code implementation is as follows:

public static void mergeSort(int[] numbers, int left, int right) { int t = 1; Int size = right-left + 1; while (t < size) { int s = t; // The number of elements in each group t = 2 * s; int i = left; while (i + (t - 1) < size) { merge(numbers, i, i + (s - 1), i + (t - 1)); i += t; } if (i + (s - 1) < right) merge(numbers, i, i + (s - 1), right); } } private static void merge(int[] data, int p, int q, int r) { int[] B = new int[data.length]; int s = p; int t = q + 1; int k = p; while (s <= q && t <= r) { if (data[s] <= data[t]) { B[k] = data[s]; s++; } else { B[k] = data[t]; t++; } k++; } if (s == q + 1) B[k++] = data[t++]; else B[k++] = data[s++]; for (int i = p; i <= r; i++) data[i] = B[i]; }Copy the code

Radix sort

Used when sorting large numbers, long numbers.

  • Take the units digit of all the numbers and sort them by the units digit to form a sequence.

  • Take out the ten digits of all the newly formed numbers and sort them according to the ten digits to form a sequence.

The code implementation is as follows:

Public void sort(int[] array) { int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } int time = 0; // Determine the number of digits; while (max > 0) { max /= 10; time++; } // Create 10 queues; List queue = new ArrayList(); for (int i = 0; i < 10; i++) { ArrayList queue1 = new ArrayList(); queue.add(queue1); } // Perform time allocation and collection; for (int i = 0; i < time; I++) {// allocate array elements; for (int j = 0; j < array.length; J++) {// get the first time of the number +1 digit; int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); ArrayList queue2 = queue.get(x); queue2.add(array[j]); queue.set(x, queue2); } int count = 0; // Element counter; // Collect queue elements; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList queue3 = queue.get(k); array[count] = queue3.get(0); queue3.remove(0); count++; }}}}Copy the code

Write in the last

Welcome to pay attention to my public number [calm as code], massive Java related articles, learning materials will be updated in it, sorting out the data will be placed in it.

If you think it’s written well, click a “like” and add a follow! Point attention, do not get lost, continue to update!!