Welcome to pay attention to the public number fun, learning together with communication progress!
Sorting algorithm is one of the most basic algorithms in Data Structures and Algorithms.
Sorting algorithms can be divided into internal sorting and external sorting.
Internal sort is the sorting of data records in memory.
And the external sort is because the sort of data is very large, one can not hold all the sort records, in the process of sorting need to access the external memory.
Common internal sort algorithms are: insertion sort, hill sort, selection sort, bubble sort, merge sort, quick sort, heap sort, radix sort and so on.
Here’s a picture:
About time complexity:
- Square order (O(n2)) sort all kinds of simple sort: direct insertion, direct selection and bubble sort.
- Linear logarithmic order (O(nlog2n)) sort quicksort, heap sort and merge sort;
- O(n1+§)), § is a constant between 0 and 1. Hill sorting
- Linear order (O(n)) sort radix sort, in addition to bucket, box sort.
On stability:
-
Stable sorting algorithms: bubble sort, insertion sort, merge sort and radix sort.
-
Not stable sorting algorithms: selection sort, quicksort, Hill sort, heap sort.
1. Bubble sort
1.1 Algorithm Steps
-
Compare adjacent elements. If the first one is bigger than the second, swap them both.
-
Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
-
Repeat this step for all elements except the last one.
-
Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
1.2 Animation Demonstration
1.3 Reference Code
Public class BubbleSort implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
for(int i = 1; i < arr.length; I++) {// set a flag iftrue, it indicates that there is no exchange in this cycle, that is, the sequence to be sorted has been ordered and the sorting has been completed. boolean flag =true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false; }}if (flag) {
break; }}returnarr; }}Copy the code2. Select sort
2.1 Algorithm Steps
-
First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence
-
Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
-
Repeat the second step until all elements are sorted.
2.2 Animation Demonstration
2.3 Reference Code
Public class implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // There are N-1 rounds of comparisonsfor(int i = 0; i < arr.length - 1; i++) { int min = i; // The number of comparisons per round N- Ifor (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[min]) {// Record the subscript min = j of the smallest element that can be found; }} // Swap the minimum value found with the value at position Iif (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
returnarr; }}Copy the code3. Insert sort
3.1 Algorithm Steps
-
Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.
-
Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
3.2 Animation Demonstration
3.3 Reference Code
Public class InsertSort implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length); // Select the appropriate place to insert from the element with subscript 1, since there is only one element with subscript 0 and the default is orderedfor(int i = 1; i < arr.length; Int TMP = arr[I]; Int j = I; int j = I; int j = I;while(j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // There is a smaller number, insertif (j != i) {
arr[j] = tmp;
}
}
returnarr; }}Copy the code4. Hill sort
4.1 Algorithm Steps
-
Select an incremental sequence T1, T2… , where Ti > tj, tk = 1;
-
Sort the sequence k times according to the number of incremental sequences k;
-
In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
4.2 Animation Demonstration
4.3 Reference Code
Public class implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
returnarr; }}Copy the code5. Merge sort
5.1 Algorithm Steps
-
Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;
-
Set two Pointers, starting at the start of two sorted sequences;
-
Compare the elements pointed to by the two Pointers, select the smaller element into the merge space, and move the pointer to the next position;
-
Repeat step 3 until a pointer reaches the end of the sequence;
-
Copies all remaining elements of the other sequence directly to the end of the merged sequence.
5.2 Animation Demonstration
5.3 Reference Code
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else{ result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); }}while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
returnresult; }}Copy the code6. Quicksort
6.1 Algorithm Procedure
-
Pick an element from the sequence, called pivot;
-
Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
-
Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value;
6.2 Animation Demonstration
6.3 Reference Code
Public class implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
return quickSort(arr, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
returnarr; } private int partition(int[] arr, int left, int right) {private int partition(int[] arr, int left, int right) { int index = pivot + 1;for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
returnindex - 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code7. The heap sort
7.1 Algorithm Procedure
-
Create a heap H[0…… n-1];
-
Swap the heap head (maximum) with the heap tail;
-
Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.
-
Repeat step 2 until the heap size is 1.
7.2 Animation Demonstration
7.3 Reference Code
Public class implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Copy the code8. Counting sort
8.1 Algorithm Steps
-
Take O(n) time to scan the entire sequence A to get min and Max
-
Create a new array B of length (max-min + 1)
-
The element of index in array B records the number of occurrences of an element in A
-
Finally output the sequence of target integers, the specific logic is to traverse the number group B, output the corresponding elements and the corresponding number
8.2 Animation Demonstration
8.3 Reference Code
Public class implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if(maxValue < value) { maxValue = value; }}returnmaxValue; }}Copy the code9. Bucket sorting
9.1 Algorithm Procedure
-
Set a fixed number of empty buckets.
-
Put the data into the corresponding bucket.
-
Sort the data in each bucket that is not empty.
-
Concatenate the data in the bucket that is not empty to obtain the result
9.2 Animation Demonstration
9.3 Reference Code
Public class BucketSort implements IArraySort {private static final InsertSort InsertSort = new InsertSort(); @Override public int[] sort(int[]sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if(value > maxValue) { maxValue = value; } } int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1; int[][] buckets = new int[bucketCount][0]; // Allocate data to buckets using mapping functionsfor (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue; } // sort each bucket, using insertSort bucket = insertsort.sort (bucket);for(int value : bucket) { arr[arrIndex++] = value; }}returnarr; } /** * Automatic capacity expansion, * * @param arr * @param value */ private int[] arrAppend(int[] arr, int value) {arr = array.copyof (arr, arr.length + 1); arr[arr.length - 1] = value;returnarr; }}Copy the code10. Radix sort
10.1 Algorithm Steps
-
All values to be compared (positive integers) are unified into the same digit length, with the shorter digit preceded by zeros
-
Sort the order one by one, starting with the lowest rank
-
From the lowest order to the highest order, the sequence becomes an ordered sequence
10.2 Animation Demonstration
10.3 Reference Code
Public class RadixSort implements IArraySort {@override public int[] sort(int[])sourceArray) throws Exception {// Copy arR without changing parameter contents int[] arr = array.copyof (sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
returnradixSort(arr, maxDigit); Private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if(maxValue < value) { maxValue = value; }}return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for(long temp = num; temp ! = 0; temp /= 10) { lenght++; }return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for(int i = 0; i < maxDigit; I++, dev *= 10, mod *= 10) {// in the case of negative numbers, multiply the number of queues, where [0-9] corresponds to negative numbers, Int [][] counter = new int[mod * 2][0];for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for(int value : bucket) { arr[pos++] = value; }}}return arr;
}
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
returnarr; }}Copy the codeNote: This article ideas from: github.com/hustcc/JS-S… Hustcc.
My website
My official website guan2ye.com
My blog.csdn.net/chenjianand CSDN address…
My address book Jane www.jianshu.com/u/9b5d1921c…
My githubgithub.com/javanan
My code cloud address is gitee.com/jamen/
Aliyun.guan2ye.com/
** Personal wechat official account: Dou_zhe_wan ** Welcome to follow
