Selection sort
core idea
Select the smallest element and swap places with the first element; Select the smallest of the remaining elements and swap places with the foremost of the current remaining elements.
Analysis of the
The number of comparisons for the selection sort is independent of the initial sort of the sequence, and is N(n-1)/2.
The number of moves is n minus 1 at most.
Thus, the time complexity is O(N^2), whether the inputs are ordered or not, and the order of the inputs only determines the number of swaps, but the number of comparisons remains the same.
Selection sort is unstable, like 5, 6, 5, 3.
code
public class SelectionSort {
public void selectionSort(int[] nums){
if(nums==null)
return;
for(int i=0; i<nums.length; i++) {int index = i;
for (int j = i; j < nums.length; j++) {
if(nums[j] < nums[index]) { index = j; } } swap(nums, i, index); }}}Copy the codeBubble sort:
core idea
Swapping adjacent elements in reverse order from left to right brings the largest element to the far right. Repeat this process over and over until there is no exchange in one loop, which means it has been ordered and exits.
Analysis of the
- When the original sequence is ordered, the number of comparisons is n-1 and the number of moves is 0, so the time complexity is O(n) in the best case.
- When sorting in reverse order, the number of comparisons is N(n-1)/2 and the number of moves is 3N(n-1)/2, so the worst-case time complexity is O(N^2).
- The average time complexity is O(N^2).
When two elements are exchanged, the order of the same elements does not change, so it is stable.
code
public class BubbleSort {
public void bubbleSort(int[] nums){
for(int i=nums.length-1; i>0; i--){boolean sorted=false;
for(int j=0; j<i; j++){if(nums[j]>nums[j+1]){
Sort.swap(nums,j,j+1);
sorted=true; }}if(! sorted)break; }}Copy the codeInsertion sort
core idea
Each time the current element is inserted into the sorted left array, the left array remains in order after insertion.
Analysis of the
Since insertion sort can only swap adjacent elements each time, reducing the number of inversions by 1, the number of swaps is equal to the number of inversions.
Therefore, the complexity of insertion sort depends on the initial order of the array.
- The array is already ordered, N minus 1 comparisons and 0 swaps, O(N) time.
- The array is completely reversed, N(n-1)/2 comparisons and N(n-1)/2 swaps, O(N^2)
- On average, time is O(N^2).
Insertion sort is stable
code
public class InsertionSort {
public void insertionSort(int[] nums){
for(int i=1; i<nums.length; i++){for(intj=i; j>0; j--){if(nums[j]<nums[j-1])
swap(nums,j,j-1);
else
break;// It has been placed in the correct position}}}}Copy the codeHill sorting
For large arrays, insertion sort is slow because it can only swap adjacent elements, reducing the number of inversions by one at a time.
core idea
Hill sort To address the limitations of insertion sort, the number of inversions is reduced by more than one at a time by swapping non-adjacent elements. Hill sort uses insertion sort to sort the sequence spaced H, decreasing H until H=1, eventually making the entire array orderly.
Time complexity
The time complexity of Hill sort is difficult to determine, and the choice of H will also change its time complexity.
The time complexity of Hill sort is less than O(N^2), and the advanced sorting algorithm is only about twice as fast as Hill sort.
The stability of
Hill sort is not stable.
code
public class ShellSort {
public void shellSort(int[] nums){
int N=nums.length;
int h=1;
while(h<N/3){
h=3*h+1;
}
while(h>=1) {for(inti=h; i<N; i++){for(intj=i; j>0; j--){if(nums[j]<nums[j-1]){
swap(nums,j,j-1);
}else{
break;// It has been placed in the correct position
}
}
}
}
}
}
Copy the codeMerge sort
core idea
Divide the array into two parts, sort them separately, and merge them.
Merge method
public void merge(int[] nums, int left, int mid, int right) {
int p1 = left, p2 = mid + 1;
int[] tmp = new int[right-left+1];
int cur=0;
// Two Pointers to the left and right subarrays, the smaller one into the auxiliary array
while(p1<=mid&&p2<=right){
if(nums[p1]<nums[p2]){
tmp[cur++]=nums[p1++];
}else{ tmp[cur++]=nums[p2++]; }}// Add the remaining array to the auxiliary array
while(p1<=mid){
tmp[cur++]=nums[p1++];
}
while(p2<=right){
tmp[cur++]=nums[p2++];
}
/ / copy
for(int i=0; i<tmp.length; i++){ nums[left+i]=tmp[i]; }}Copy the codeCode implementation
Recursive method: top down
A large array is divided into two smaller arrays by recursive calls from the top down.
public void up2DownMergeSort(int[] nums, int left, int right) {
if(left==right)
return;
int mid=left+(right-left)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums,left,mid,right);
}
Copy the codeNon-recursive: bottom up
public void down2UpMergeSort(int[] nums) {
int N = nums.length;
for (int sz = 1; sz < N; sz += sz) {
for(int lo = 0; lo < N - sz; lo += sz + sz) { merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1)); }}}Copy the codeAnalysis of the
A problem of size N is decomposed into two subproblems of size N/2 respectively, and the combined time complexity is O(N). T (N) = 2 T (N / 2) + O (N).
The time complexity is O(NlogN) and the time complexity is the same in the worst, best and average cases.
Merge sort requires order N space.
Merge sort is stable.
Quick sort
core idea
Quicksort Uses a shard element pivot to divide the array into two subarrays, with the left subarray less than or equal to the shard element and the right subarray greater than or equal to the shard element, sorting the subarrays separately, and finally sorting the whole array.
partition
Take a[L] as the shard element and scan right from the left end of the array until it finds the first element greater than or equal to it. Then scan left from the right end of the array to find the first element less than it. Swap the two elements. This process ensures that no element to the left of the left pointer I is larger than the shard element, and no element to the right of the right pointer J is smaller than the shard element. When two Pointers meet, the shard elements A [L] and a[j] swap places.
private int partition(int[] nums, int left, int right) {
int p1=left,p2=right;
int pivot=nums[left];
while(p1<p2){
while(nums[p1++]<pivot&&p1<=right);
while(nums[p2--]>pivot&&p2>=left);
swap(nums,p1,p2);
}
swap(nums,left,p2);
return p2;
}
Copy the codeCode implementation
public void sort(T[] nums, int l, int h) {
if (h <= l)
return;
int j = partition(nums, l, h);
sort(nums, l, j - 1);
sort(nums, j + 1, h);
}
Copy the codeAnalysis of the
In the best case, the array is split exactly in half each time, with a minimum of recursive calls and O(NlogN) complexity.
In the worst case, it’s an ordered array, one element at a time, O(N^2). To prevent this, the array needs to be randomly shuffled when performing quicksort.
It’s not stable.
To improve the
- Switch to Insert sort: recursive subarray size is small, use insert sort.
- Take the middle of three numbers: in the best case, take the median every time as the segmentation element, the cost of calculating the median is relatively high, so take three elements and take the median as the segmentation element.
Three way fast row
For the array with a large number of repeating elements, the array is divided into less than, equal to and greater than three parts. For the random number group with a large number of repeating elements, sorting can be completed in linear time.
public void threeWayQuickSort(int[] nums,int left,int right){
if(right<=left)
return;
int lt=left,cur=left+1,gt=right;
int pivot=nums[left];
while(cur<=gt){
if(nums[cur]<pivot){
swap(nums,lt++,cur++);
}else if(nums[cur]>pivot){
swap(nums,cur,gt--);
}else{
cur++;
}
}
threeWayQuickSort(nums,left,lt-1);
threeWayQuickSort(nums,gt+1,right);
}
Copy the codePartition based fast lookup
Partition () is used to find the KTH element of the array in linear time complexity.
Assuming the array can be dichotomized each time, the total number of comparisons is (N+N/2+N/4+..). All the way to the KTH element, which is obviously less than 2N.
public int select(int[] nums, int k) {
int l = 0, h = nums.length - 1;
while (h > l) {
int j = partition(nums, l, h);
if (j == k) {
return nums[k];
} else if (j > k) {
h = j - 1;
} else {
l = j + 1; }}return nums[k];
}
Copy the codeHeap sort
The heap
A heap can be represented as an array because a heap is a complete binary tree, and a complete binary tree can easily be stored in an array. The parent of the node at position K is at k/2, while its two children are at 2k and 2K +1, respectively. In this case, the position from the index of 1 is used to give a clearer description of the position of the nodes.
Up and down
When a node is larger than its parent, swapping the two nodes until the node is put in place is called floating up.
private void shiftUp(int k) {
while (k > 1 && heap[k / 2] < heap[k]) {
swap(k / 2, k);
k = k / 2; }}Copy the codeWhen a node is smaller than its children, comparisons and swaps are made continuously downward, and when a base point has two children, swaps are made with the largest node. This operation is called sinking.
private void shiftDown(int k){
while(2*k<=size){
int j=2*k;
if(j<size&&heap[j]<heap[j+1])
j++;
if(heap[k]<heap[j])
break; swap(k,j); k=j; }}Copy the codeHeap sort
Swapping the largest element with the last element of the array in the current heap, without deleting it, results in a decrementing sequence from end to end.
Building a heap The most straightforward way to build a heap is to float up a group of numbers from left to right. A more efficient method is to sink from right to left. The leaf nodes do not need to be sunk and can be ignored, so only half of the elements need to be traversed.
Swap the top of the heap and the worst element to sink and maintain the nature of the heap.
public class HeapSort {
public void sort(int[] nums){
int N=nums.length-1;
for(int k=N/2; k>=1; k--){ shiftDown(nums,k,N); }while(N>1){
swap(nums,1,N--);
shiftDown(nums,1,N);
}
System.out.println(Arrays.toString(nums));
}
private void shiftDown(int[] heap,int k,int N){
while(2*k<=N){
int j=2*k;
if(j<N&&heap[j]<heap[j+1])
j++;
if(heap[k]>=heap[j])
break; swap(heap,k,j); k=j; }}private void swap(int[] nums,int i,int j){
intt=nums[i]; nums[i]=nums[j]; nums[j]=t; }}Copy the codeAnalysis of the
The time to build the heap is order N.
The height of a heap is logN, so the complexity of inserting and removing the largest element in the heap is logN.
In heap sort, N nodes are sunk and the complexity is O(N logn).
Heapsort is rarely used by modern operating systems because it cannot be cached using the principle of locality, where array elements are rarely compared and swapped with neighboring elements.
To compare
| Sorting algorithm | Best time complexity | Average time complexity | Worst time complexity | Spatial complexity | The stability of | Applicable scenario |
|---|---|---|---|---|---|---|
| Bubble sort | O(N) | O(N^2) | O(N^2) | O(1) | stable | |
| Selection sort | O(N) | O(N^2) | O(N^2) | O(1) | unstable | The running time is independent of the input, and is applicable when the number of data moves is minimum and the amount of data is small. |
| Insertion sort | O(N) | O(N^2) | O(N^2) | O(1) | stable | The data is small and most of it has been sorted |
| Hill sorting | O(N) | O (N ^ 1.3) | O(N^2) | O(1) | unstable | |
| Quick sort | O(NlogN) | O(NlogN) | O(N^2) | O(logN)-O(N) | unstable | Fastest universal sorting algorithm, best choice for most cases |
| Merge sort | O(NlogN) | O(NlogN) | O(NlogN) | O(N) | stable | You need stability. Space is not very important |
| Heap sort | O(NlogN) | O(NlogN) | O(NlogN) | O(1) | O(1) | unstable |
- When the size is small, such as less than or equal to 50, insert or select sort is used.
- When the elements are basically in order, choose insert, bubble, or random quicksort.
- When the scale is large, O(NlogN) sorting algorithm is used.
- When the keywords to be sorted are randomly distributed, the average quicksort time is the shortest.
- When stability is needed, merge sort is used.
Noncomparative sort
The previous algorithms are all comparison-based sorting algorithms. Here are two non-comparison-based sorting algorithms.
Count sorting
Given the data range x1 through x2, sort the elements in the range. You can use an array of length X2 -x1+1 to store the number of occurrences of each number. And then we get the sorted result.
Bucket sort
Bucket sorting assumes that a set of numbers to be sorted are evenly and independently distributed in a range, and this range is divided into several buckets. Then, the keyword k to be sorted is mapped to the ith bucket based on some mapping function. Then the data in each bucket is combined in an orderly manner, and the elements in each bucket can be sorted, and then an ordered sequence is output.