Four, sorting algorithm details
4.1 Bubble Sorting
4.1.1 Basic Ideas
By treating the sorting sequence from front to back (starting with the element with the smaller subscript), the values of adjacent elements are compared in turn, and if the reverse order is found, the values of the element with the larger value are gradually moved from front to back, like bubbles rising up under the water.
4.1.2 optimization
In the sorting process, each element keeps approaching its position. If there is no exchange after a comparison, it means that the sequence is orderly. Therefore, a flag should be set in the sorting process to determine whether elements have been exchanged. Thus reducing unnecessary comparisons. (The optimization mentioned here can be done after bubble sort is written).
4.1.3 diagram
Summary:
- We loop through the size of the array -1 times.
- The number of sequences per trip is gradually decreasing.
- If we find that no swap has occurred in a particular sort, we can end the bubble sort early. This is optimization.
4.1.4 Code implementation
package com.company.sort;
import java.lang.reflect.Array;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args){
int[] arr = new int[] {3.9, -1.10, -2};
System.out.println("Pre-sort");
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println("After sorting");
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr){
// Sort (arr. Length -1)
for (int i = 0; i < arr.length -1; i++){
// Each sort is fixed to a maximum (minimum) value
for (int j = 0; j < arr.length -1 - i; j++){
if(arr[j] > arr[j+1]) {// Define an auxiliary variable used to exchange data
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
Copy the codeAfter the optimization:
public static void bubbleSort(int[] arr){
// Sort (arr. Length -1)
for (int i = 0; i < arr.length -1; i++){
System.out.println(Arrays.toString(arr));
// Each sort is fixed to a maximum (minimum) value
Boolean flag = false; // Indicates whether the order has been swapped
for (int j = 0; j < arr.length -1 - i; j++){
if(arr[j] > arr[j+1]) {// Define an auxiliary variable used to exchange data
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
// Modify the flag to indicate that the switch has been performed
flag = true; }}if(! flag){// The array is already in order
break; }}}Copy the code4.1.5 Code runtime test
Add code to test bubble sort time:
public static void main(String[] args){
// Test bubble sort speed (O(n^2))
// Create an array of 80000 random data
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++){
arr[i] = (int)(Math.random() * 8000000); // generate the number randomly at [0,8000000]
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH-mm-ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("The time before sorting is equal to" + date1Str);
bubbleSort(arr);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("The sorted time is equal to" + date2Str);
}
Copy the codeConclusion: The time complexity of bubble sort is O(n^2). 80000 random number, bubble sort time in about 20s.
4.2 Select Sorting
4.2.1 Basic idea
The minimum value is selected from ARR [0]~ ARR [n-1] for the first time and exchanged with ARR [0]; the minimum value is selected from ARR [1]~ ARR [n-1] for the second time and exchanged with ARR [1]; the minimum value is selected from ARR [2]~ ARR [n-1] for the third time and exchanged with ARR [2]… , the minimum value is selected from arR [i-1]~ ARr [n-1] for the i-th time, and exchanged with ARr [i-1]… , the minimum value is selected from ARR [n-2]~ ARR [n-1] for the n-1st time, and exchanged with ARR [n-2]. After a total of n-1 times, an ordered sequence is obtained from the smallest to the largest according to the sorting code.
4.2.2 diagram
Description:
- There are (arr. Length-1) sorts.
- For each sort, there is another loop, with the pseudo-code for the loop as follows:
- Assume that the current number is the minimum;
- Then compare the current number with each of the following numbers. If there is a number smaller than the current number, record the subscript of the number and re-assign the minimum value;
- After iterating through the array, we get the minimum value and the index of the order;
- Swap the position of the current value with the minimum value.
Holdings optimization
When the minimum value determined by a certain sort is the same as the current value, the fourth step of the above step is omitted.
4.2.4 Code implementation
package com.company.sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args){
int[] arr = new int[] {10.20, -10.3.18.40};
selectSort(arr);
}
public static void selectSort(int[] arr){
// sort arr. Length -1
for (int i = 0; i < arr.length - 1; i++){
// Start the current value as the minimum value, and compare with each subsequent number to find the minimum value and index of this cycle.
int min = arr[i];
int minIndex = i;
for (int j = i + 1; j < arr.length; j++){
if(min > arr[j]){ min = arr[j]; minIndex = j; }}// Swap the current value with the minimum value
arr[minIndex] = arr[i];
arr[i] = min;
// Prints the result of each sort run
System.out.println("The first"+(i+1) +"Sorting result:"+Arrays.toString(arr)); }}}Copy the codeOptimization:
public static void selectSort(int[] arr){
// sort arr. Length -1
for (int i = 0; i < arr.length - 1; i++){
// Start the current value as the minimum value, and compare with each subsequent number to find the minimum value and index of this cycle.
int min = arr[i];
int minIndex = i;
for (int j = i + 1; j < arr.length; j++){
if(min > arr[j]){ min = arr[j]; minIndex = j; }}// Swap the current value with the minimum value
// Optimize, if the current value and the minimum value are the same, do not swap
if(minIndex ! = i){ arr[minIndex] = arr[i]; arr[i] = min; }// Prints the result of each sort run
System.out.println("The first"+(i+1) +"Sorting result:"+Arrays.toString(arr)); }}Copy the code4.2.5 Code runtime test
Conclusion: The time complexity of selection sort is O(n^2). 80000 random number, select sort time in 2s, faster than bubble!! .
4.3 Insert Sorting
4.3.1 Basic Idea
Read the n to sort elements as an ordered list and an unordered list, at the beginning of the order in the table contains only one element, disorder in the table contains a element of n – 1, each time in the process of sorting table to retrieve the first element from the chaos, combine its number in comparing with orderly table element number, in an orderly table to insert it into the appropriate position, making it the new order list.
4.3.2 diagram
4.3.3 Code implementation
package com.company.sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args){
// Create an array of 80000 random data
int[] arr = new int[8];
for (int i = 0; i < 8; i++){
arr[i] = (int)(Math.random() * 1000); // generate the number randomly at [0,8000000]
}
insertSort(arr);
}
public static void insertSort(int[] arr){
// Insert (arr. Length-1) unordered number
for (int i = 1; i < arr.length; i++){
//1. Save the unordered number insertVal
//2. Compare the numbers to be inserted with the previous ordered array
//3. Insert when insertVal is greater than a value
int insertVal = arr[i];
int insertIndex = i ; // Record the subscript of the number of inserts
// optimize to determine the conditions for insertion
if(insertVal < arr[insertIndex -1]) {// When insertVal is greater than or equal to the specified value, the insertion position is found
while (insertIndex >= 1 && insertVal < arr[insertIndex -1]){
arr[insertIndex] = arr[insertIndex - 1]; // When insertVal is less than the specified value, the specified value is moved one bit later
insertIndex--; // move the subscript forward
}
// Insert tval into the insertIndex position
arr[insertIndex] = insertVal;
// Prints the result of each sort run
System.out.println("The first"+i+"Sorting result:"+ Arrays.toString(arr)); }}}}Copy the code4.3.4 Code runtime test
Conclusion: The time complexity of selection sort is O(n^2). 80000 random number, select sort time around 4s, between bubble and select sort!! .
4.4 Shell Sorting
4.4.1 Basic Ideas
Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates. Through this strategy, hill sort makes the whole array in the initial stage basically orderly from a macroscopic point of view, with the small ones basically in front and the large ones basically in back. Then you reduce the increment until you get to 1, which in most cases is fine tuning and doesn’t involve too much data movement.
4.4.2 diagram
4.4.3 Code implementation
In the hill sort sense, we tend to process each group, group by group, but in code implementation, we don’t have to process each group and then go back to the next group (and then add a for loop to process the groups) like [5,4,3,2,1,0], First increment set gap=length/2=3, then 3 groups [5,2] [4,1] [3,0], implementation does not need to cycle by group processing, we can start from the gap element, one by one across the group processing. When inserting an ordered sequence, the element swap method can be used to find the final position, or the array element movement method can be used to find.
Exchange method:
/** * Hill sort uses the swap method when inserting an ordered sequence. *@param arr
*/
public static void shellSort1(int[] arr){
// 1. First group arRs by incremental gap
// Initialize the increment and gradually decrease it
int temp = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//2. Insert the gap element one by one
for (int i = gap; i < arr.length; i++){
int j = i;
while (j-gap >=0 && arr[j] < arr[j-gap]){
// Swap elementstemp = arr[j-gap]; arr[j-gap] = arr[j]; arr[j] = temp; j -= gap; }}}}Copy the codeMobile method:
/** * Hill sort uses the move method when inserting an ordered sequence. *@param arr
*/
public static void shellSort2(int[] arr){
// 1. First group arRs by incremental gap
// Initialize the increment and gradually decrease it
for (int gap = arr.length / 2; gap > 0; gap /= 2) {//2. Insert the gap element one by one
for (int i = gap; i < arr.length; i++){
int insertVal = arr[i];
int insertIndex = i;
if(insertVal < arr[i -gap]){
while ((insertIndex - gap >= 0) && insertVal < arr[insertIndex -gap]){ arr[insertIndex] = arr[insertIndex - gap]; insertIndex -= gap; } arr[insertIndex] = insertVal; }}}}Copy the code4.4.4 Code runtime test
The time of Hill sort swap method and ordinary insertion sort is about 4s; The speed of hill sorting and moving method is very fast. The sorting time of 80000 random numbers is less than 1s, and the time complexity is O(N*logN). The move method is recommended.
4.5 Quick Sorting
4.5.1 Basic Idea
Quicksort uses the idea of divide-and-conquer.
- Find a reference value (pivot), typically selecting the first element of the array to be sorted.
- Partition the array by placing everything less than or equal to the base on the left and everything greater than the base on the right.
- Repeat step 1,2 to partition the left and right sub-partitions until each partition has only one number.
4.5.2 of graphic
4.5.3 Code implementation
package com.company.sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args){
// Create an array of 80000 random data
int[] arr = new int[8];
for (int i = 0; i < 8; i++){
arr[i] = (int)(Math.random() * 1000); // generate the number randomly at [0,8000000]
}
quickSort(arr,0,arr.length - 1);
}
/** * the sorting process *@paramArr Array to be partitioned *@paramLeft Minimum subscript * of the array to be partitioned@paramRight The maximum index of the array to be partitioned is */
public static void quickSort(int[] arr, int left, int right){
if(isEmpty(arr)){
return;
}
if (left < right){
int temp = partition(arr,left,right);
quickSort(arr,left,temp - 1);
quickSort(arr,temp + 1,right); }}public static boolean isEmpty(int[] arr){
return arr == null || arr.length == 0;
}
/** * Partition process *@paramArr Array to be sorted *@paramLeft Minimum subscript * of the array to be sorted@paramRight Maximum index of the array to be sorted *@returnAfter the order of the base number of position subscript, convenient next partition */
public static int partition(int[] arr, int left, int right){
int pivot = arr[left]; // Define the base number, which defaults to the first element of the array
while (left < right){ // Conditions for loop execution
// Since the default base number is on the far left, the criteria for entering the while loop are first compared from the right
// If the current arR [right] is greater than the base number, move the right pointer to the left one bit, and ensure that left
while (left < right && arr[right] > pivot){
right--;
}
// If the current arr[right] is less than or equal to the base value, then the current number is filled directly to the left pointer (starting at the base value), and the left pointer is moved one bit to the right
// The current arr[right] position is empty, need to find a number from the left more than the base number to fill.
if(left < right){
arr[left++] = arr[right];
}
System.out.println("Right pointer assignment"+ Arrays.toString(arr));
// The next step is to find the number greater than the base number on the left to fill in the right position.
If arr[left] is less than the base, move the left pointer one bit to the right
while (left < right && arr[left] < pivot){
left++;
}
// The current arr[left] value is greater than the base number, and the value needs to be filled to the left position, and the right pointer is moved one bit to the left.
if(left < right){
arr[right--] = arr[left];
}
System.out.println("Left pointer assignment"+Arrays.toString(arr));
}
// When the loop ends, the left and right Pointers have already met. And the place where they meet is an empty place,
// At this point, fill the base number into the position and return the subscript of the position to prepare for the partition.
arr[left] = pivot;
System.out.println("Last assignment"+Arrays.toString(arr));
returnleft; }}Copy the code4.5.4 Code runtime test
Quicksort has an O(N*logN) time complexity, and in fact, quicksort is usually significantly faster than other O(N logN) algorithms. Test 8000000 data sort, time is less than 1s, very fast!!
4.6 Merge Sorting
4.6.1 Basic Idea
Merge sort is a sorting method based on the idea of merge. The algorithm uses the classic divide-and-conquer strategy to divide problems into small problems and solve them recursively, while the conquer phase “patches” the answers obtained in the two stages together. Divide and conquer)
4.6.2 diagram
Diagram 1:
In the cure stage, we need to merge two ordered sub-sequences into one ordered sequence. For example, in the last merge in the figure above, we need to merge two ordered sub-sequences [4,5,7,8] and [1,2,3,6] into the final sequence [1,2,3,4,5,6,7,8]. Let’s see the implementation steps.
Diagram 2:
4.5.3 Code implementation
package com.company.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergeSort {
public static void main(String[] args){
// Test bubble sort speed (O(n^2))
// Create an array of 80000 random data
int[] arr = new int[8];
for (int i = 0; i < 8; i++){
arr[i] = (int)(Math.random() * 8); // generate the number randomly at [0,8000000]
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH-mm-ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("The time before sorting is equal to" + date1Str);
int[] temp = new int[arr.length];
mergeSort(arr,0,arr.length - 1,temp);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("The sorted time is equal to" + date2Str);
System.out.println("Sorted array"+Arrays.toString(arr));
}
/ * * *@Description: merge sort *@Param:
*@return:
*@Author: your name
*@date: * /
public static void mergeSort(int[] arr,int left,int right,int[] temp){
if(left < right){
int mid = (left + right) / 2; // Intermediate index
// The right-hand side is recursively processed
mergeSort(arr,mid + 1,right,temp);
// The left side is recursively processed
mergeSort(arr,left,mid,temp);
/ / mergemerge(arr,left,mid,right,temp); }}/ * * *@Description: Merge method *@Param: * left Initial index of the left ordered sequence * min Intermediate index * right right index * temp temp variable *@return: void
*@Author: your name
*@date: * /
public static void merge(int[] arr,int left,int mid,int right,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 ordered sequence on the right
int t = 0; // Initializes the temp array index
// Step 1:
// Place the left and right ordered sequences in the temp array according to the rule
// Until one of the left and right sequences is processed
while (i <= mid && j <= right) {
// If the current element of the left sequence is less than or equal to the current element of the right sequence
// Fill the temp array with the current element of the left sequence
// simultaneously t++, i++
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t++;
i++;
}else { // otherwise fill the temp array with the current elements of the sequence on the right, t++,j++temp[t] = arr[j]; t++; j++; }}// Step 2:
// If there are any remaining elements in the left sequence, fill the remaining elements into the temp array
while (i <= mid){
temp[t] = arr[i];
t++;
i++;
}
// If there are any remaining elements in the right sequence, fill the remaining elements into the temp array
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
// Step 3:
// Assign temp array to arR, pay attention to index!!
t = 0;
int tempLeft = left;
while(tempLeft <= right){ arr[tempLeft] = temp[t]; tempLeft++; t++; }}}Copy the codeReference:
www.cnblogs.com/chengxiao/p…
Juejin. Cn/post / 684490…
www.cnblogs.com/MOBIN/p/468…