Eight sorting algorithms
| Sorting algorithm | Average time complexity | The stability of |
|---|---|---|
| Bubble sort | O(n^2) | stable |
| Selection sort | O(n^2) | unstable |
| Direct insertion sort | O(n^2) | stable |
| Hill sorting | O (n ^ 1.5) | unstable |
| Quick sort | O(N*logN) | unstable |
| Merge sort | O(N*logN) | stable |
| Heap sort | O(N*logN) | unstable |
| Radix sort | O(d(n+r)) | stable |
1. Bubble sort
Basic Principles:
An array of raw data is scanned multiple times from front to back, and each scan is called one. When the order of two adjacent data is found to be inconsistent with the size order required by sorting, the two data are switched. If you sort from smallest to largest, then the smaller pieces of data move forward one by one, like bubbles floating upwards.
Here is:
Process analysis:
From the example above we can see the number of comparisons per round:
| Number of traversals I | Number of traversal comparisons per pass j |
|---|---|
| 0 | 5 |
| 1 | 4 |
| 2 | 3 |
| 3 | 2 |
| 4 | 1 |
We can see from the table that there is such a relationship between the number of traversal trips I and the comparison times j of each trip: I +j=nums.length-1, so we get I and j. The value range of I is [0,nums.length-1), and the value range of j is [I +1,nums.length-1].
code
public static int[] bubbleSort(int[] nums) {
for (int i = 0; i < nums.length-1; i++) {/ / number
for (int j = i+1; j <= nums.length-1; j++) {// Number of comparisons per trip
if (nums[i] > nums[j]) {
inttemp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}}return nums;
}
Copy the codeOptimization of bubble sort
Improve by 1.0
- Original bubble sort such problems: such as a set of number 5,8,6,3,9,2,1,7} {after to the sixth bubble sort, the figures in the array is sorted, but in the original bubble sort, he will also continue to compare the seventh round, obviously this is not necessary.
- Improvement: We use a Boolean flag to indicate whether the array is already ordered. The initial value is true. If the array is unordered, then swapping occurs. If flag is true after one comparison, then the array is already sorted, and there is no need to sort the remaining number of trips. Jump out of the outer loop and return the result.
Improved code
public static int[] bubbleSort(int[] nums) {
for (int i = 0; i < nums.length-1; i++) {
boolean flag = true;// Order flags, each round starts with true
for (int j = i+1; j <= nums.length-1; j++) {
if (nums[i] > nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
// There is an element swap, indicating that the array is unordered
flag = false; }}if (flag) {// If flag is true at the end of a trip, then the array is sorted.
break; }}return nums;
}
Copy the codeImprove by 2.0
- For example, the array to be sorted is
,4,2,1,5,6,7,8 {3}And we can see the last of this set of numbers{5,6,7,8}Already ordered, we don’t need to bubble sort them anymore, so we can improve on that. - Improvement: The key to this problem lies in our understanding ofSequence ordered regionThe demarcation. According to the current logic,Length of ordered regionAnd bubble sortTrain numberEqual, but actually maybe the length of the ordered region is greater than the number of rounds. For example, in the problem description, the following
Five, six, seven, eightWe’re actually in the ordered region. After each sequence, we can record the position of the last swap element, which is the edge of the unordered sequence, and the rest of the sequence is sorted.
Code:
public static int[] bubbleSort(int[] nums) {
int lastLocation = 0;// The position of the last swap element
int isSorted = nums.length -1;// The ordered range boundary, the initial value is the array maximum index nums. length-1
for (int i = 0; i < nums.length-1; i++) {
boolean flag = true;// Order flags, each round starts with true
for (int j = 0; j < isSorted; j++) {/ / note
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
// There is an element swap, indicating that the array is unordered
flag = false;
lastLocation = j;
}
}
isSorted = lastLocation;
if (flag) {// If flag is true at the end of a trip, then the array is sorted.
break; }}return nums;
}
Copy the code2. Select sort
Basic Principles:
Selection sort is a simple and intuitive sorting method. The core idea is: find the minimum value from the number to be sorted each time, put the minimum value in front of the number to be sorted, so as to determine the ordered position of a number. Then, in the remaining unsorted numbers, find a minimum value and put it in front of the remaining numbers, so as to determine the ordered position of the second number. In this way, n numbers can be sorted from largest to smallest by repeating them n-1 times.
Here is:
Process analysis
After each selection sort, we need to remember the index of the least valued element and place the element in its position at the top of the remaining unsorted array. We can see that there is a relationship between the number of sorting trips I and the length of the remaining array j: I +j=arr. Length-1 (I starts from 0).
The value of I is [0,n-1). The value of j is [I +1,n-1]. N is the length of the array.
Code:
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length -1; i++) {
int minIndex = i;// Initial minimum subscript
for (int j = i+1; j <= arr.length -1; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Record the new minimum subscript}}// After a sort, swap the smallest element to the front of the array.
if(minIndex ! = i){inttemp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}return arr;// returns the sorting result
}
Copy the code3. Insert sort
Basic Principles:
In the set of numbers to be sorted, assuming that the first n-1 number is already sorted, insert the NTH number into the previous n-1 ordered array so that the n number is exactly sorted, and repeat until all numbers are sorted.
Here is:
Process analysis
As can be seen from the figure, in the initial array, the ordered part of the array is the first element 8, and then we successively insert the remaining 2,6,1,7,0 into the corresponding positions of the ordered array. Therefore, we need to perform a total of 5 insertion operations, that is, the number of sort runs I is: [1,arr. Length-1], the insertion position needs to be compared with the i-1 element before the current position I, that is, the value range of j is: [0,i-1].
code
public static int[] insertSort(int[] arr) {
int i,j,temp;
for (i = 1; i <= arr.length - 1; i++) {
temp = arr[i];// The current number to be inserted
for (j = i - 1; j >=0; j--) {
if (arr[j] > temp) {// If the element to be inserted is smaller than its predecessor, the insertion position is still in front.
arr[j+1] = arr[j];
} else {// If the value of the current element to be inserted is >= the element at the current comparison position, then the appropriate insertion position is found, and the loop is broken.
break;
}
}
arr[j+1] = temp;// Insert into the right position
}
return arr;
}
Copy the code4. Hill sort
Basic Principles:
In the set of numbers to be sorted, the array is divided into subsequences according to a certain increment, and the subsequences are sorted by insertion. Then gradually reduce the increment and repeat the above operation until the increment is 1. At this point, the data sequence is basically in order. Finally, insert sort is performed.
Illustration:
Code:
public static int[] shellSort(int[] arr) {
int temp,i,j;
int incre = arr.length;// Initial increment
while (true) {
incre /= 2;// The increment is halved each time
// Insert sort is used for each trip
for (i = incre; i < arr.length; i++) {
temp = arr[i];// The element to insert
for (j = i - incre; j >=0; j -= incre) {
if (arr[j] > temp) {// If the current element to be inserted is smaller than the element before it, the insertion position is still ahead.
arr[j+incre] = arr[j];
}else{// If the value of the current element to be inserted is >= the element at the current comparison position, then the appropriate insertion position is found, and the loop is broken.
break;
}
}
arr[j+incre] = temp; // Insert into final position
}
//System.out.println(Arrays.toString(arr));
if(incre == 1) {break;// Break the loop}}return arr;
}
Copy the code5. Quicksort
Basic principle: divide and conquer
- First, a number is taken from the array as the key value;
- Anything less than this number is to its left, anything greater than or equal to this number is to its right;
- Repeat the second step for the left and right small sequences until each interval has only one number.
Illustration:
Code:
/** quicksort */
public static void quickSort(int[] arr,int left,int right) {
if(left<right){
int mid = getLastLocation(arr, left, right);
quickSort(arr, left, mid-1);// The left part of the pivot does the same
quickSort(arr, mid+1, right);// The right part of the pivot does the same}}/** * Find the final position of pivot */
public static int getLastLocation(int[] arr,int left,int right) {
int pivot = arr[left];// The initial reference value is the first element of the array
while (left < right){
// Find a value smaller than pivot from right to left
while (left < right && arr[right] >= pivot) {// the value >=pivot is encountered,
right--;// Move the right pointer left
}
// Otherwise the right pointer points to the value
arr[left] = arr[right];// Place it to the left of pivot.
// Look left/right for a value greater than pivot
while (left < right && arr[left] <= pivot) {// The value <=pivot is encountered
left++;// Move the left pointer right
}
// Otherwise left points to the value >pivot
arr[right] = arr[left];// Place it to the right of pivot
}
arr[left] = pivot;// Place the pivot in the final position found
System.out.println(pivot + Final position:+ left);
return left;// Returns the current final pivot position.
}
Copy the code6. Merge sort
Basic idea:
Merge-sort is a sorting method based on the idea of merging. It adopts the classic divide-and-conquer strategy (divide problems into small problems and solve them recursively). The conquer phase “tinkered” with the answers obtained in the conquer phases, i.e. divide and conquer.
Here is:
Step by step can be understood as the process of recursively dismantling the molecular sequence, recursion depth is log2n.
In the treatment stage, we need to merge two ordered sub-sequences into one ordered sequence. For example, in the last combination in the figure above, we need to merge the 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]. The specific implementation steps are as follows:
Code implementation:
import java.util.Arrays;
public class MergeSort{
public static void main(String[] args){
int[] arr = {8.4.5.7.1.3.6.2};
mergeSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
/** merge sort */
public static void mergeSort(int[] arr, int left, int right){
if (left<right) {
int mid = left + (right - left) / 2;
mergeSort(arr,left,mid);
mergeSort(arr,mid + 1, right); merge(arr,left,mid,right); }}/** merge an ordered subsequence */
public static void merge(int[] arr,int left,int mid,int right){
int[] temp = new int[arr.length];// Temporary array
int l = left;// Left sequence pointer
int r = mid+1; // Right sequence pointer
int t = 0;// Temporary array pointer
while(l<=mid && r<=right){// Insert into the temp array in size order.
if (arr[l] <= arr[r]) {// The left sequence is small
temp[t] = arr[l];
t++;
l++;
}else{// Right sequence is smalltemp[t] = arr[r]; t++; r++; }}while(l<=mid){// Insert the remaining elements into temp
temp[t] = arr[l];
t++;
l++;
}
while(r<=right){// The left sequence is merged and the right sequence is left. Insert the remaining elements into temp
temp[t] = arr[r];
t++;
r++;
}
t = 0;/ / reset
while(left <= right){// Copy temp into arR.arr[left++] = temp[t++]; }}}Copy the code7. The heap sort
The basic principle of
- Disordered number fabric is constructed into binary heap. If you need to sort from smallest to largest, build a large root heap. Small root heaps are built for those that need to go from large to small.
- Iteratively remove the top element of the heap and replace it with the end of the binary heap. The adjustment produces a new heap top.
Here is:
As shown in the figure above, after removing the heap vertex of node 10, a new node with a value of 9 is adjusted to replace it and become the new heap top, and so on. After removing 9, 8 is adjusted to become the new heap top……
Because of this feature of the binary heap, each time the old top is removed, the new top is adjusted to be the node next in size to the old top. So as long as the top of the heap is repeatedly deleted and the binary heap is repeatedly adjusted, the set obtained will become an ordered set, and the process is as follows. Delete node 9 and node 8 becomes the new heap top.
Delete node 8 and 7 to become the new heap top:
Delete node 7 and 6 to become the new heap top:
In turn, what started as a large pile of roots has become an ordered collection of smaller and larger roots. The binary heap is actually stored in an array, the elements of which are arranged as follows.
Code:
import java.util.Arrays;
1. Organize unordered numbers into binary heaps. If you need to sort from smallest to largest, build a large root heap. Small root heaps are built for those that need to go from large to small. * 2. Iterate over the top of the heap and replace to the end of the binary heap. The adjustment produces a new heap top. * /
public class HeapSort {
public static void main(String[] args) {
int[] arr = {2.3.8.1.4.9.10.7.16.14};
System.out.println(Arrays.toString(arr));
heapSort(arr, arr.length);
System.out.println(Arrays.toString(arr));
}
/** * Maintain heap properties *@paramArray arr *@paramN Array length *@paramIndex Index of the node to be maintained */
public static void heapify(int[] arr,int n,int index) {
int largest = index;
int lson = index * 2 +1;// The left child of the current parent node
int rson = index * 2 +2;// The right child of the current parent node
if (lson < n && arr[largest] < arr[lson]) {// There is a left child and the left child is larger than the parent node
largest = lson;// Update the maximum node subscript
}
if (rson < n && arr[largest] < arr[rson]) {// There is a right child and the right child is larger than the parent node
largest = rson;// Update the maximum node subscript
}
if(largest ! = index) {// Swap the largest of the three to the parent node.
int temp = arr[index];
arr[index] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);/ / recursion}}/** * heap sort *@param arr
* @param n
*/
public static void heapSort(int[] arr,int n) {
//1. Build a large root heap
//int i;
for (int i = (arr.length - 2) / 2; i >=0; i--) {
heapify(arr, n, i);
}
//2
// Loop the top and last node of the heap so that the maximum value is placed at the end of the array
for (int i = n-1; i > 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
/ / adjust the heap
heapify(arr, i, 0);// Maintain the heaptop element}}}Copy the code8. Radix sort
Schematic rationale:
Code:
/** Base sort */
public static void radixSort(int[] arr) {
// Get the maximum number of digits in the array
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i] > max){ max = arr[i]; }}// Get the largest number of digits
int maxLength = (max + "").length();
// Define a two-dimensional array representing buckets. Each bucket is a one-dimensional array
// The size of each bucket is set to the length of the arR array
// Space for time
int[][] bucket = new int[10][arr.length];
// To keep track of how many pieces of data are in each bucket, define a one-bit array to keep track of how many pieces of data are in each bucket
int[] bucketElementCount = new int[10];
for (int i = 0,n = 1; i < maxLength; i++, n*=10) {
// Sort the digits of each number. The first digit is a bit, the second digit is ten...
for (int j = 0; j < arr.length; j++) {
// Fetch the n bits of each element. N =1 represents the ones bits
int digitOfElement = arr[j] / n % 10;
// Put it into the corresponding bucket
bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
bucketElementCount[digitOfElement]++;
}
// Add the data to the array in the order of the bucket
int index = 0;
// Iterate over a bucket and add the data in the bucket to the original array
for (int k = 0; k < bucketElementCount.length; k++) {
// If there is data in the bucket, it is added to the original array
if(bucketElementCount[k] ! =0) {
// Loop the bucket
for (int l = 0; l < bucketElementCount[k]; l++) {
// Take the element and put it into arRarr[index++] = bucket[k][l]; }}// After round I +1, we need to say that each bucketElementCount[k] = 0
bucketElementCount[k] = 0;
}
System.out.println("The first"+(i+1) + "Round, sort processing:"+ Arrays.toString(arr)); }}Copy the code