Bubble sort
Principle: Compare two adjacent numbers, if the first number is greater than (less than) the number behind, then they switch positions, until the end, repeat (n-1) times, get an ordered sequence algorithm complexity: O(N ^2) sorting process:
- Source data: 7, 8, 3, 26, 99, 91
- Round 1:7, 3, 8, 26, 91, 99
- Round 2:3, 7, 8, 26, 91, 99
- Round 3:3, 7, 8, 26, 91, 99
- Round 4:3, 7, 8, 26, 91, 99
- Round 5:3, 7, 8, 26, 91, 99
public class BubbleSort extends Sort {
// Bubble sort
@Override
public void sort(int[] array) {
int length = array.length;
//recordValues(array," data: ");
for (int i = 0; i < length - 1; i++) {
for (int j = 1; j < length - i; j++) {
// If the condition is met, switch places
if (array[j - 1] > array[j]) {
int tem = array[j];
array[j] = array[j - 1];
array[j - 1] = tem; }}//recordValues(array," 1 "+(I +1)+" round: ");}}}Copy the codeInsertion sort
Principle: insert a number into an ordered sequence, get a new ordered sequence algorithm complexity: O(n^2) sorting process:
- Source data: 7, 8, 3, 26, 99, 91
- Round 1:7, 8, 3, 26, 99, 91
- Round 2:3, 7, 8, 26, 99, 91
- Round 3:3, 7, 8, 26, 99, 91
- Round 4:3, 7, 8, 26, 99, 91
- Round 5:3, 7, 8, 26, 91, 99
public class InsertionSort extends Sort {
@Override
public void sort(int[] array) {
// recordValues(array," data: ");
int length =array.length;
for(int i=1; i<length; i++){int tem =array[i];
int j=i-1;
for(; j>=0; j--){if(tem<array[j]){
array[j+1] =array[j];
}else {
break;
}
}
array[j+1] =tem;
//recordValues(array," "+(I)+");}}}Copy the codeSelection sort
Select a maximum (minimum) value from an unordered array and place it in an ordered array
- Round 1:3, 8, 7, 26, 99, 91
- Round 2:3, 7, 8, 26, 99, 91
- Round 3:3, 7, 8, 26, 99, 91
- Round 4:3, 7, 8, 26, 99, 91
- Round 5:3, 7, 8, 26, 91, 99
- Round 6:3, 7, 8, 26, 91, 99
/** * select sort */
public class SelectionSort extends Sort {
public void sort(int[] array) {
int length = array.length;
for (int i = 0; i < length; i++) {
// Select the smallest from the remaining array
for (int j = 1 + i; j < length; j++) {
if (array[j] < array[i]) {
inttem = array[i]; array[i] = array[j]; array[j] = tem; }}//recordValues(array," 1 "+(I +1)+" round: ");}}}}Copy the codeFast row
Principle: find the key value, and then divide the sequence into two sequence, one is greater than or equal to the key value, one is less than or equal to the key value, and then recurse the two sequence algorithm complexity: O(nlogn) algorithm steps:
- Find the base number and put the base in the sorted position
- An array on either side of a recursive reference
Sorting process:
- Source data: 7 8 3 26 99 91
- Baseline 7: 3, 7, 8, 26, 99, 91
- Base 8: 3, 7, 8, 26, 99, 91
- Base 26: 3 7 8 26 99 91
- Base 99: 3, 7, 8, 26, 91, 99
public class QuickSort extends Sort {
// find the benchmark
public int findPartition(int[] array, int left, int right) {
int pivot = array[left];
while (left < right) {
while (pivot <= array[right] && left < right) {
right--;
}
array[left] = array[right];
array[right] = pivot;
while (pivot > array[left] && left < right) {
left++;
}
array[right] = array[left];
array[left] = pivot;
}
array[left] = pivot;
/ / recordValues (array, "benchmark" + pivot + ":");
return left;
}
/ / fast row
private void quickSort(int[] array, int left, int right) {
if (left < right) {
int mid = findPartition(array, left, right);
quickSort(array, left, mid - 1);
quickSort(array, mid + 1, right); }}@Override
public void sort(int[] array) {
// recordValues(array," data: ");
quickSort(array, 0, array.length - 1); }}Copy the codeMerge sort
Principle: Divide-and-conquer strategy is adopted to decompose big problems into small ones and solve recursively. Algorithm complexity: O(nlogn) Algorithm steps:
- Recursively splits an array into two arrays until it can no longer be divided
- Merge and sort the split array
Sorting process:
- Source data 7, 8, 3, 26, 99, 91
- 2 is the middle point 7, 8, 3, 26, 99, 91
- 1 is the middle point 7, 8, 3, 26, 99, 91
- 0 is the midpoint 7, 8, 3, 26, 99, 91
- 0 Data merge 7, 8, 3, 26, 99, 91
- 1 data merge 3, 7, 8, 26, 99, 91
- 4 is the midpoint 3, 7, 8, 26, 99, 91
- 3 is the middle point 3, 7, 8, 26, 99, 91
- 3 data merge 3, 7, 8, 26, 99, 91
- 4 data merge 3, 7, 8, 26, 91, 99
- 2 data merge 3, 7, 8, 26, 91, 99
Simplify the sorting process:
- Source data 7 8 3 26 99 91
- Divide an array into two arrays with a third number
- 7,8,3-26,99,91
- Continue to divide the array
- Seven, eight, three, twenty-six, nine, ninety-one
- Continue to divide the array
- 7 — 8 — 3 — 26 — 99 — 91
- An array of merger
- Seven, eight, three, twenty-six, nine, ninety-one
- Continue to merge
- 3 a proposal – 26,91,99
- Continue to merge
- 3,7,8,26,91,99
public class MergSort extends Sort {
// Array merge
private void merg(int[] array, int left, int mid, int right) {
int[] arrayTem = new int[right - left + 1];
int leftIndex = left;
int rightIndex = mid + 1;
int index = 0;
while (leftIndex <= mid && rightIndex <= right) {
if (array[leftIndex] < array[rightIndex]) {
arrayTem[index] = array[leftIndex];
leftIndex++;
} else {
arrayTem[index] = array[rightIndex];
rightIndex++;
}
index++;
}
while (leftIndex <= mid) {
arrayTem[index] = array[leftIndex];
leftIndex++;
index++;
}
while (rightIndex <= right) {
arrayTem[index] = array[rightIndex];
rightIndex++;
index++;
}
index = 0;
for(; left <= right; left++) { array[left] = arrayTem[index]; index++; }}/ / sorting
private void mergSort(int[] array, int left, int right) {
if(left ! = right) {int mid = (left + right) / 2;
recordValues(array,""+mid+"Be the middle point");
mergSort(array, left, mid);
mergSort(array, mid + 1, right);
merg(array, left, mid, right);
// recordValues(array,""+mid+");}}@Override
public void sort(int[] array) {
mergSort(array, 0, array.length - 1); }}Copy the codeHeap sort
Principle: and select sort similar, but will choose the size of this step with the heap to achieve the nature of the heap
-
It’s a complete binary tree
-
Each node (non-leaf node) has a value greater than or equal to (less than or equal to) its child node
Big top pile: array [I] > = Max (array (2 + 1] I, array (I + 1) [2]) small top pile: array [I] < = min (array (2 + 1] I, array (I + 1) [2])
Algorithm complexity: O(nlogn) Algorithm steps:
- Building the heap
- Pick the maximum (small) value from the top of the heap (pay attention to heap adjustments)
public class HeapSort extends Sort {
@Override
public void sort(int[] array) {
buildMaxHeap(array);
heapSort(array);
}
/ / heap sort
private void heapSort(int[] array) {
int len = array.length;
for (int i = array.length - 1; i >= 0; i--) {
int tem = array[0];
array[0] = array[i];
array[i] = tem;
adJustMaxHeap(array, 0, --len); }}// Maximum heap adjustment
void adJustMaxHeap(int[] array, int index, int len) {
int largest = index;
int left = leftChildIndex(index);
int right = rightChildIndex(index);
if (left >= len) {
return;
}
if (array[left] > array[index]) {
largest = left;
}
if (right < len && array[right] > array[largest]) {
largest = right;
}
if(largest ! = index) {inttem = array[largest]; array[largest] = array[index]; array[index] = tem; adJustMaxHeap(array, largest, len); }}// Build the maximum heap
private void buildMaxHeap(int[] array) {
int len = array.length;
for (int i = len / 2; i >= 0; i--) { adJustMaxHeap(array,i,len); }}/ / the left child
private int leftChildIndex(int parent) {
return parent * 2 + 1;
}
/ / right child
private int rightChildIndex(int parent) {
return (parent + 1) * 2; }}Copy the codeHill sort (reduced incremental sort)
Principle: It is an optimization of insertion sort. Firstly, the whole sequence is divided into several sub-sequences for direct insertion sort respectively. After the number in the whole sequence is basically in order, the insertion sort is carried out again
- Source data: 7 8 3 26 99 91
- Step 3: 7 8 3 26 99 91
- Step 1: 3 7 8 26 91 99
public class ShellSort extends Sort {
@Override
public void sort(int[] array) {
recordValues(array,"Source data:");
int len = array.length;
for (int gap = len / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < len; i++) {
if (array[i] < array[i - gap]) {
int k = i;
int tem = array[i];
while (k - gap >= 0&& tem < array[k - gap]) { array[k] = array[k - gap]; k = k - gap; } array[k] = tem; }}/ / recordValues (array, "step" + gap + ":");}}}Copy the codeThe complexity of Hill sort is largely determined by the delta sequence selected, and there is no optimal delta sequence
Count sorting
Principle: not through data comparison to sort, after the number of data occurrence, and then according to the number of statistics discharged sequence algorithm complexity: O(N + K) algorithm steps:
- Count the number of occurrences of each data item
- Output the data in one go
public class CoutNumSort extends Sort {
public static int SIZE =100;
@Override
public void sort(int[] array) {
int[] countNum = new int[SIZE+5];
for(int i=0; i<array.length; i++){ countNum[array[i]]++; }int index =0;
for(int i =0; i<SIZE; i++){for(int j=0; j<countNum[i]; j++){ array[index]=i; index++; }}// recordValues(array," sort result ");}}Copy the codeSpatial optimization: Select the maximum and minimum values and turn the size of the statistical array to max-min+1 (this optimization is very related to the data)
public class CoutNumSort extends Sort {
public static int SIZE =100;
@Override
public void sort(int[] array) {
int min,max;
min =max=array[0];
for(int i=0; i<array.length; i++){if(min>array[i]){
min =array[i];
}
if(max<array[i]){ max=array[i]; }}int[] countNum = new int[max-min+1];
for(int i=0; i<array.length; i++){ countNum[array[i]-min]++; }int index =0;
SIZE =max-min+1;
for(int i =0; i<SIZE; i++){for(int j=0; j<countNum[i]; j++){ array[index]=i+min; index++; }}//recordValues(array," sort result ");}}Copy the codeHow to ensure that the same data is arranged according to the original data
public class CoutNumSort extends Sort {
public static int SIZE =100;
@Override
public void sort(int[] array) {
// This part is optimized for space
int min,max;
min =max=array[0];
for(int i=0; i<array.length; i++){if(min>array[i]){
min =array[i];
}
if(max<array[i]){ max=array[i]; }}int[] countNum = new int[max-min+1];
// Data statistics
for(int i=0; i<array.length; i++){ countNum[array[i]-min]++; }// Set the position and keep the original order
for(int i=1; i<countNum.length; i++){ countNum[i]+=countNum[i-1];
}
int[] result = new int[array.length];
for(int i =array.length-1; i>=0; i--){ result[countNum[array[i]-min]-1] =array[i];
countNum[array[i]-min]--;
}
// recordValues(result," sort result: ");}}Copy the codeLimitations of counting sort
Counting sort is mainly limited by the difference between the maximum and minimum values of the data. When the difference is large, it means that more space is applied, resulting in a lot of waste. However, the efficiency is relatively high when the statistics value is in a fixed range of data, such as height, score, weight and so on.
Radix sort
Principle: Sort from the lowest digit to the highest digit by comparing the value of each data bit, using the counting sort algorithm complexity: O(n*m)
- Data: 7 8 3 26 99 91
- Round 1:91 3 26 7 8 99
- Round 2:3, 7, 8, 26, 91, 99
public class RadixSort extends Sort {
@Override
public void sort(int[] array) {
recordValues(array,"Data:");
int arrayLength = array.length;
int[] temArray = new int[arrayLength];
int[] bucks = new int[10];
int[] weights = new int[8];
weights[0] = 1;
int numLength = maxLength(array);
initWeight(weights, numLength);
for (int i = 0; i < numLength; i++) {
/ / empty
for (int j = 0; j < bucks.length; j++) {
bucks[j] = 0;
}
for (int j = 0; j < array.length; j++) {
int digit = getDigit(array[j], weights[i]);
bucks[digit]++;
}
for (int j = 1; j < bucks.length; j++) {
bucks[j] += bucks[j - 1];
}
for (int j = arrayLength - 1; j >= 0; j--) {
int digit = getDigit(array[j], weights[i]);
temArray[bucks[digit] - 1] = array[j];
bucks[digit]--;
}
for (int j = 0; j < array.length; j++) {
array[j] = temArray[j];
}
recordValues(array,"The first"+(i+1) +"Wheel."); }}// The weight is initialized
private void initWeight(int[] weights, int len) {
for (int i = 1; i <= len; i++) {
weights[i] = weights[i - 1] * 10; }}// Maximum length
private int maxLength(int[] array) {
int maxNum = array[0];
for (int i = 0; i < array.length; i++) {
if(maxNum < array[i]) { maxNum = array[i]; }}return Integer.toHexString(maxNum).length();
}
// Get the number on the weight
private int getDigit(int num, int weight) {
return (num / weight) % 10; }}Copy the codeconclusion
| Sorting algorithm | Time complexity | The worst time | Spatial complexity | The stability of |
|---|---|---|---|---|
| Bubble sort | O(n2) | O(n2) | 1 | stable |
| Selection sort | O(n2) | O (n2) | 1 | stable |
| Insertion sort | O(n2) | O(n2) | 1 | stable |
| Fast row | O(nlogn) | O(n2) | logn | unstable |
| Merge sort | O(nlogn) | O(nlogn) | n | stable |
| Heap sort | O(nlogn) | O(nlogn) | 1 | unstable |
| Count sorting | O(n+k) | O(n+k) | n+k | stable |
| Radix sort | O(n*d) | O(n*d) | n+k | stable |
- Sorting algorithm When n value is small, O(n2) and O(nlogn) efficiency is similar, O(n2) even better than O(nlogn).
- When n is large, O(n2) algorithm cannot be selected. In general, fast sorting is superior to other N (logn) algorithms.