Optimize common java sorting algorithms
- 2021-10-16 01:51:08
- OfStack
Bubble sorting
The idea of bubble sorting:
Compare the size of the current element with its next 1 element at a time, and exchange the two elements if the first 1 element is larger than the next 1 element.
In this way, after one scan, you can ensure that the last element 1 of the array is the largest element in the array.
Then the next scan will be one less in length than the last one, because the last one element of the array is already the largest, that is, the last one element has been ordered.
Optimization 1: The idea of optimization is to traverse the group once every scan. If there is no exchange of array elements after a certain scan, then the elements of the array are already orderly, so you can jump out of the loop directly, and there is no need to continue scanning.
Optimization 2: If the tail of the array is already locally ordered, then after 1 scan, there is no need to scan the part that is locally ordered at the tail. The specific method is to record the position of the previous exchange, and then let the next scan to the position of the previous record, because the elements after the recorded position have been ordered.
The primitive way of writing
// Conventional writing
public static void bubbleSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
Optimization 1
// Optimization 1
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
Optimization 2
// Optimization 2
public static void bubbleSort3(int[] array) {
int end = array.length-1;
for (int i = end; i > 0 ; i--) {
int lastIndex = 1;
for (int j = 0; j < end; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
lastIndex = j + 1;
}
}
end = lastIndex;
}
}
Select sort
The idea of selective sorting is similar to the idea of bubble sorting. After another scan, find the largest element in the array, and put the largest element at the end of the array. When scanning the array for the second time, the length of the previous scan is reduced by 1
Of course, you can also realize selective sorting in a different way-scan the array every time, then find out the smallest element, put the smallest element at the first place of the array, not at the first place of the scan array next time, and put the second smallest element at the second place of the array.
Method 1
public static void selectSort1(int[] array) {
for (int end = array.length - 1; end > 0; end--) {
int maxIndex = 0;
for (int start = 0; start <= end; start++) {
if (array[maxIndex] < array[start]) {
maxIndex = start;
}
}
int tmp = array[end];
array[end] = array[maxIndex];
array[maxIndex] = tmp;
}
}
Method 2
public static void selectSort2(int[] array) {
for (int start = 0; start < array.length; start++) {
int minIndex = start;
for (int end = start; end < array.length; end++) {
if (array[end] < array[minIndex]) {
minIndex = end;
}
}
int tmp = array[minIndex];
array[minIndex] = array[start];
array[start] = tmp;
}
}
Heap sort
Stacking can be regarded as an optimization of selective sorting. The array is built into a large pile in situ, and the largest element is placed at the last position of the array. adjust makes the array continue to keep a large root pile, and the next exchange is to exchange with the penultimate element of the array. The idea and the previous two sort of algorithm thinking 1, is also to find the most value, and the array of the beginning or end of the exchange, the next exchange time to ignore the exchange of elements.
Of course, you can also build a small heap. The top of the pile is already the smallest, so it is only necessary to compare the sizes of the left child and the right child at the top of the pile. If the left child is larger than the right child, exchange and let the right child adjust keep a small pile (because the exchanged right child may not meet the small pile).
Build a large pile to realize stacking
public static void heapSort1(int[] array) {
// Build a large pile
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown(array, p, array.length);
}
// Exchange
int end = array.length - 1;
while (end > 0) {
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
adjustDown(array, 0, end);
end--;
}
}
public static void adjustDown(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
Build small piles to realize stacking
public static void adjustDown1(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] > array[child + 1]) {
child++;
}
if (array[child] < array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
public static void heapSort2(int[] array) {
// Build a small pile
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown1(array, p, array.length);
}
// Exchange
int startIndex = 1;
while (startIndex + 1 < array.length) {
if (array[startIndex] > array[startIndex + 1]) {
int tmp = array[startIndex];
array[startIndex] = array[startIndex + 1];
array[startIndex + 1] = tmp;
adjustDown1(array,startIndex+1,array.length);
}
startIndex++;
}
}
Insert sort
The idea of insertion sorting is similar to playing cards, where the left hand holds the row in order, and the right hand holds the card and compares it with the previous card, and then inserts it into the appropriate position.
Optimization 1:
The idea of Optimization 1 is to change comparison into movement. Every time you get an element, you have to compare it with the previous elements. If there are more reverse pairs of arrays, you have to compare and exchange it every time. Therefore, we can record the value of the current element first, move the number before the element greater than the element back by 1 digit, and then insert it, so that the number of comparisons and exchanges will be reduced.
Optimization 2:
To find the position where the current element is to be inserted in the previous ordered elements, can you use a 2-point lookup to achieve it? So we can use 2-point search to continue to optimize 1.
Realization
public static void insertSort1(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = start;
while (cur > 0 && array[cur] < array[cur - 1]) {
int tmp = array[cur];
array[cur] = array[cur - 1];
array[cur - 1] = tmp;
cur--;
}
}
}
Optimization 1
public static void insertSort2(int[] array){
for (int start = 1; start < array.length; start++) {
int cur = start;
int tmp = array[start];
while (cur>0 && tmp < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
}
Optimization 2
public static void insertSort3(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = array[start];
int insertIndex = searchIndex(array, start);
for (int i = start; i > insertIndex; i--) {
array[i] = array[i - 1];
}
array[insertIndex] = cur;
}
}
public static int searchIndex(int[] array, int index) {
int start = 0;
int end = index;
while (start < end) {
int mid = (start + end) >> 1;
if (array[index] < array[mid]) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
Merging sort
The idea of merging and sorting is to divide the current sequence into two sub-sequences until the number of elements in the sub-sequence is 1, and then merge the two sub-sequences into an ordered sequence.
Optimize:
It can be seen that the size of the additional array applied for each merge is the length of the left subsequence + the length of the right subsequence (end-start + 1), and the value of the additional array is assigned to the corresponding position of the original array after merge.
Then we can make optimization, we can operate directly on the original array, copy the value of the left sub-sequence every time, compare it with the value of the right sub-sequence, and directly overwrite the original value. In this way, the extra space for each application is doubled compared with the space for the original application.
Recursive implementation of merge sorting
// Optimization 1
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
Optimization
// Optimization 1
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
Look at the sort of O (n)
// Optimization 1
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
Of course, besides comparison-based sorting, there are also non-comparison-based sorting.
Counting and sorting: The core idea is to count the number of times each integer appears in the sequence, and then deduce the index of each integer in the ordered sequence. The specific method is to find out the largest element in the sequence first, open up the array space with the largest element +1, count the number of times each element appears counts [array [i]] + +, and then traverse the coutns array, find out the elements that are not 0, and output the corresponding subscripts, or put the subscripts back into the array array, which is equivalent to the array array.
Cardinal sorting: All elements are unified into the same digit length, and the shorter digits are preceded by zeros. Then, starting with the lowest bit, sort once in turn, so that the original array becomes an ordered sequence from the lowest bit sorting 1 until the highest bit sorting is completed.
Bucket sorting: Create a fixed number of buckets, you can use arrays or linked lists as buckets, according to the rules of 1, the elements in the sequence are evenly distributed to the corresponding buckets, and then the elements in each bucket are sorted separately, and finally all the elements of non-empty buckets are merged into an ordered sequence.
Summarize
That's all for this article. I hope it will be helpful to you, and I hope you can pay more attention to more contents of this site!