This is the 24th day of my participation in the August Text Challenge.More challenges in August
Following up on sorting algorithms in the last article, let’s cut to the chase.
1. Quicksort
Quicksort is an improvement on bubbling sort. Quicksort was proposed by C. A. R. Hoare in 1960. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.
Presentation:
The code is as follows:
public static void quickSort(int[] arr, int left, int right) {
int l = left;/ / left subscript
int r = right;/ / right subscripts
int pivot = arr[(left + right) / 2];// Find the middle value
// Place the value less than pivot to its left and the value greater than pivot to its right
while (l < r) {
// Search to the left of pivot until a value greater than or equal to pivot is found
while (arr[l] < pivot) {
l += 1;// Move l to the right one bit
}
// Search to the right of pivot until it finds a value less than or equal to pivot
while (arr[r] > pivot) {
r -= 1;// Move r to the left one bit
}
if (l >= r) {
// the left and right subscripts overlap
break;
}
// Swap elements
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// If the values are equal, there is no need to compare
// If arr[l]==pivot, shift r one place to the left
if (arr[l] == pivot) {
r -= 1;
}
// If arr[r]==pivot, shift L one bit to the right
if (arr[r] == pivot) {
l += 1; }}// If l==r, stagger the two subscripts, otherwise infinite recursion will occur, resulting in stack overflow
if (l == r) {
l += 1;
r -= 1;
}
// Recurse to the left
if (left < r) {
quickSort(arr, left, r);
}
// Recursive to the right
if(right > l) { quickSort(arr, l, right); }}Copy the codeTest code:
public static void main(String[] args) {
int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
Copy the codeRunning results:
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the codeQuicksort is done by dividing the array into two parts, taking the middle value as the standard, placing the smaller value to the left, the larger value to the right, and then sorting the left and right in the same way again. So in the implementation of the code, we first create two moving variables, one from the left to the right and one from the right to the left, to traverse the left and right parts of the elements. When you find an element on the left that is greater than the middle number and an element on the right that is less than the middle number, you swap. When the two variables overlap or are equal, we finish the loop, and then we recurse on the left and right.
2. Merge sort
Merge-sort is an effective sorting algorithm based on MERGE operation. It is a typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called binary merge.
Presentation:
Merge sort uses a divide-and-conquer idea, which means’ divide and conquer ‘. It is the idea of dividing a complex problem into two or more identical or similar sub-problems, and then dividing the sub-problems into smaller sub-problems… Until finally the subproblem can be solved simply and directly. If you look at this GIF, I’m sure many people will be confused. It doesn’t matter. Let’s analyze it through the static image:
Suppose we now have a sequence to sort, [5,2, 4,7, 1,3,2,2]. We need to divide the sequence into two parts: [5,2, 4,7] and [1,3,2,2], and then divide the two parts into two parts: [5,2] and [4,7]. [1,3] and [2,2]. Finally, these four parts are divided into two parts again. Finally, the whole sequence is divided into eight parts. It is important to note that there are no rules to follow in the process of dividing. The key is to merge, and in the process of merging, the elements are sorted.
The code is as follows:
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
/ / decomposition
if (left < right) {
int mid = (left + right) / 2;// Intermediate index
// Recurse to the left
mergeSort(arr, left, mid, temp);
// Decompose recursively to the right
mergeSort(arr, mid + 1, right, temp);// mid = 1; // mid = 1
// Merge each decomposition roundmerge(arr, left, right, mid, temp); }}/** * the merge method **@paramArr Array to sort *@paramLeft The initial index of the left ordered sequence *@paramRight middle index *@paramThe initial index * of the ordered sequence to the right of mid@paramTemp does the transfer array */
public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
int i = left; // Initialize I, the initial index of the left ordered sequence
int j = mid + 1;// Initialize j, the initial index of the right order (the initial position of the right order is the last position of the middle position)
int t = 0;// Points to the current index of the temp array, starting with 0
// Start by populating the left and right sides of the data (already ordered) into the temp array
// Until one of the ordered sequences on the left and right sides is processed
while (i <= mid && j <= right) {
// If the current element of the left ordered sequence is less than or equal to the current element of the right ordered sequence, the left element is filled into the temp array
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;// Index moves back
i++;/ / I backwards
} else {
// Instead, populate the temp array with the current elements of the ordered sequence on the right
temp[t] = arr[j];
t++;// Index moves back
j++;/ / j}}// Fill temp with the elements on the side with the remaining data
while (i <= mid) {
// There are still elements left in the left sequence
// Fill it all into the temp array
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
// There are still elements left in the left sequence
// Fill it all into the temp array
temp[t] = arr[j];
t++;
j++;
}
// Copy the elements of the temp array to the original array
t = 0;
int tempLeft = left;
while(tempLeft <= right) { arr[tempLeft] = temp[t]; t++; tempLeft++; }}Copy the codeThe idea of merging sort is really convoluted, so I also put a lot of comments in the code. Let’s test it out:
public static void main(String[] args) {
int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
Copy the codeRunning results:
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the codeSo let’s see, for this sort algorithm, there are two parts, decomposition and merge. First of all, decomposition, as I mentioned earlier, we need to constantly decompose the sequence to be sorted, controlled by two index variables, an initial index and an ending index. Decomposition ends only when the two indexes overlap. At this point the sequence is broken down into fifteen smaller pieces, and the decomposition is complete. Next comes the merge, which is also the most troublesome, again through the two index variables I and j. Sequence starting on the left side of the first position, j in the right sequence of the first position, then around looking for the lowest value of two sequences, into the new sequence, then may appear on one side of the elements are placed ended, but on the other side there are elements, just at this time in order to the rest of the elements in the new sequence can, Because the left and right sequences are already in order, you copy the new sequence into the old one. It is also important to note that the array index is constantly changing because the merge is done in steps rather than all at once.
His hand animation figure, around two arrows is the index variable I, j, when I refer to elements, that is, 1 and the reference element is also 2 j, found 1 small, will be 1 on the new array of the first position, at this point I should be and new array index moves to the right one, and then continue to compare, and so on, believe that everyone should be able to understand it.
3. Radix sort
Radix sort belongs to “distribution sort”, also called “bucket sort” or “bin sort”, as its name implies, it allocates the sorted elements to some “buckets” through partial information of key values. Radix sort is a stable sort, whose time complexity is O(nlog(r)m), where R is the radix taken and M is the number of heaps. In some cases, radix sort is more efficient than other stability sort. Radix sort is a classical algorithm that swaps space for time.
Presentation:
The basic idea of radix sort is to unify all the values to be compared into the same digit length, and fill zeros in front of the shorter digit. Then, the sequence is sorted one by one, starting with the lowest digit, so that the sequence becomes an ordered sequence from the lowest digit to the highest digit. Suppose we have an array to sort [53,3,542,748,14,214]. How do we sort it using radix sort? So first we have ten one-dimensional arrays like this, also called buckets in radix sort.
So the first round of sorting starts, and we go through each element, and we get the units digit. The first element we get is 53, and it has units digits of 3, so we put 53 in bucket number 3, the second element 3 has units digits of 3, so we put it in bucket number 3, and the third element 542 has units digits of 2, so we put 542 in bucket number 2, and so on. So the result is:
Once we have all the elements in the bucket, we need to retrieve the data in bucket order (that is, the subscripts of the one-dimensional array) and put it back in the original array. So it’s very simple. After retrieving the data sequentially and putting it back into the original array, the original array will become [542,53,3,14,214,748]. That completes the first round, and we move on to the second. The second sorting is similar to the first sorting, but the second sorting depends on the order of tens. The first element of the data is 542, and the ten digit is 4, so it is put into the bucket with the number of 4; The second element, 53, has ten digits of 5, so it goes into bucket number 5; The third element, 3, has ten digits of zero, so put in bucket zero, and so on. So the result is:
The data is then removed from the bucket in the same order and put into the original array, which becomes [3,14,214,542,748,53]. Then the third round of sorting is carried out to distinguish elements by hundreds, and the result is:
After fetching the data in sequence, the original array becomes [3,14,53,214,542,748]. At this point the array is sorted. We also know that the number of sort rounds for radix sort depends on the element with the largest number of digits in the array.
The code is as follows:
public static void raixSort(int[] arr) {
// The first round (sort the bits of each element)
// Define a two-dimensional array, simulate bucket, each bucket is a one-dimensional array
// In order to prevent the bucket from overflowing when data is put into the bucket, we should set the bucket capacity as large as possible
int[][] bucket = new int[10][arr.length];
// Record the actual number of elements in each bucket
// Define a one-dimensional array to record the number of elements in each bucket at a time
int[] bucketElementCounts = new int[10];
for (int j = 0; j < arr.length; j++) {
// Take the ones bit of each element
int digitOfElement = arr[j] % 10;
// Put the element into the corresponding bucket
// bucketElementCounts[digitOfElement] is the number of elements in the bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// Add the number of elements in the bucket ++
// So that the next element comes after the previous element
bucketElementCounts[digitOfElement]++;
}
// Fetch the data in bucket order and put it back into the original array
int index = 0;
for (int k = 0; k < bucket.length; k++) {
// If there is data in the bucket, put it back to the original array
if(bucketElementCounts[k] ! =0) {
// Data exists in the bucket, and the bucket is traversed
for (int l = 0; l < bucketElementCounts[k]; l++) {
// Return the element to the original arrayarr[index++] = bucket[k][l]; }}// After the first round of processing, set each bucketElementCounts[k] to 0
bucketElementCounts[k] = 0;
}
System.out.println("First round :" + Arrays.toString(arr));
// ----------------------------
// The second round (sort for the tens place of each element)
for (int j = 0; j < arr.length; j++) {
// Take the tens place of each element
int digitOfElement = arr[j] / 10 % 10;
// Put the element into the corresponding bucket
// bucketElementCounts[digitOfElement] is the number of elements in the bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// Add the number of elements in the bucket ++
// So that the next element comes after the previous element
bucketElementCounts[digitOfElement]++;
}
// Fetch the data in bucket order and put it back into the original array
index = 0;
for (int k = 0; k < bucket.length; k++) {
// If there is data in the bucket, put it back to the original array
if(bucketElementCounts[k] ! =0) {
// Data exists in the bucket, and the bucket is traversed
for (int l = 0; l < bucketElementCounts[k]; l++) {
// Return the element to the original arrayarr[index++] = bucket[k][l]; }}// After the second round, set each bucketElementCounts[k] to 0
bucketElementCounts[k] = 0;
}
System.out.println("Second round :" + Arrays.toString(arr));
// ----------------------------
// Round 3 (sort by hundreds for each element)
for (int j = 0; j < arr.length; j++) {
// Take the hundreds digit of each element
int digitOfElement = arr[j] / 100 % 10;
// Put the element into the corresponding bucket
// bucketElementCounts[digitOfElement] is the number of elements in the bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// Add the number of elements in the bucket ++
// So that the next element comes after the previous element
bucketElementCounts[digitOfElement]++;
}
// Fetch the data in bucket order and put it back into the original array
index = 0;
for (int k = 0; k < bucket.length; k++) {
// If there is data in the bucket, put it back to the original array
if(bucketElementCounts[k] ! =0) {
// Data exists in the bucket, and the bucket is traversed
for (int l = 0; l < bucketElementCounts[k]; l++) {
// Return the element to the original arrayarr[index++] = bucket[k][l]; }}// After the third round, set each bucketElementCounts[k] to 0
bucketElementCounts[k] = 0;
}
System.out.println("Round three :" + Arrays.toString(arr));
}
Copy the codeTo make it easier to understand, INSTEAD of using a loop, I’ve written out the steps of each round in detail, with detailed code comments. Next, write the test code:
public static void main(String[] args) {
int[] arr = { 53.3.542.748.14.214 };
raixSort(arr);
}
Copy the codeRunning results:
Round 1 :[542, 53, 3, 14, 214, 748] Round 2 :[3, 14, 214, 542, 748, 53] Round 3 :[3, 14, 53, 214, 542, 748]Copy the codeIf you can read the code above, then the next step is to integrate it, optimizing it through a loop.
The code is as follows:
public static void raixSort(int[] arr) {
// Get the largest number in the array
int max = arr[0];// Suppose the first number is the largest number in the array
for (int i = 1; i < arr.length; i++) {
if(arr[i] > max) { max = arr[i]; }}// Get the maximum number of digits
// Find the length of the string by concatenating an empty string into a string
int maxLength = (max + "").length();
// Define a two-dimensional array, simulate bucket, each bucket is a one-dimensional array
// In order to prevent the bucket from overflowing when data is put into the bucket, we should set the bucket capacity as large as possible
int[][] bucket = new int[10][arr.length];
// Record the actual number of elements in each bucket
// Define a one-dimensional array to record the number of elements in each bucket at a time
int[] bucketElementCounts = new int[10];
// Use the variable n to help fetch the number of elements
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// Process for the number of bits per element
int digitOfElement = arr[j] / n % 10;
// Put the element into the corresponding bucket
// bucketElementCounts[digitOfElement] is the number of elements in the bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// Add the number of elements in the bucket ++
// So that the next element comes after the previous element
bucketElementCounts[digitOfElement]++;
}
// Fetch the data in bucket order and put it back into the original array
int index = 0;
for (int k = 0; k < bucket.length; k++) {
// If there is data in the bucket, put it back to the original array
if(bucketElementCounts[k] ! =0) {
// Data exists in the bucket, and the bucket is traversed
for (int l = 0; l < bucketElementCounts[k]; l++) {
// Return the element to the original arrayarr[index++] = bucket[k][l]; }}// After each round, set each bucketElementCounts[k] to 0
bucketElementCounts[k] = 0; }}}Copy the codeTest code:
public static void main(String[] args) {
int[] arr = { 53.3.542.748.14.214 };
raixSort(arr);
System.out.println(Arrays.toString(arr));
}
Copy the codeRunning results:
[3, 14, 53, 214, 542, 748]
Copy the codeThis completes the radix sort. You don’t see the code a lot and they were afraid, bored, feel very difficult, actually cannot say nothing difficult, just want to understand the process, so I wrote a lot for sorting process analysis, and in order to make you more understanding, mastered the process, believe that understanding the code would not be difficult.
Other:
I’m going to say something else about radix sort, but why just radix sort? As we mentioned earlier, radix sort is a classic space for time algorithm, so radix sort is very fast for element sorting. We can test it (test the sort time of 800,000 data first) :
public static void main(String[] args) {
int[] arr = new int[800000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date date = new Date();
SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
String dateStr = format.format(date);
System.out.println("The time before sorting is :" + dateStr);
raixSort(arr);
Date date2 = new Date();
String dateStr2 = format.format(date2);
System.out.println("The time before sorting is :" + dateStr2);
}
Copy the codeRunning results:
The time before sorting is 17:37:21Copy the codeIt takes less than a second to sort. Let’s test the order of eight million data:
public static void main(String[] args) {
int[] arr = new int[8000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date date = new Date();
SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
String dateStr = format.format(date);
System.out.println("The time before sorting is :" + dateStr);
raixSort(arr);
Date date2 = new Date();
String dateStr2 = format.format(date2);
System.out.println("The time before sorting is :" + dateStr2);
}
Copy the codeRunning results:
The time before sorting is 17:38:04. The time before sorting is 17:38:05Copy the codeIt only takes a second to sort. Let’s test the order of 80 million data again:
public static void main(String[] args) {
int[] arr = new int[80000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date date = new Date();
SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
String dateStr = format.format(date);
System.out.println("The time before sorting is :" + dateStr);
raixSort(arr);
Date date2 = new Date();
String dateStr2 = format.format(date2);
System.out.println("The time before sorting is :" + dateStr2);
}
Copy the codeRunning results:
Before ordering time is: 17:41:07 Exception in the thread "is the main" Java. Lang. OutOfMemoryError: Java heap space at com.itcast.sort.RadixSortDemo.raixSort(RadixSortDemo.java:42) at com.itcast.sort.RadixSortDemo.main(RadixSortDemo.java:22)Copy the codeThe result is that the heap runs out of memory, so when sorting a large amount of data, radix sort is obviously not a good choice, because the condition of improving sorting efficiency is to sacrifice a large amount of memory, when there is enough data, memory space is insufficient.
4. The heap sort
Originally this article intends to introduce four kinds of sort algorithm, the last is the heap sort, but halfway through, back found unexpectedly also wrote so much, should not be given the length is too long, I’m going to put the heap sort in behind said, if you can master it in front of seven kinds of sort algorithm and can be written out at any time, also is very wonderful.
Although this article only introduces three kinds of sorting algorithm, but these three kinds of sorting algorithm have a certain difficulty, want to thoroughly master them we still need to spend more thought ah!