Selection sort for the first time
Selection sort is a sort algorithm as simple as bubble sort. The idea is very simple. If the array size is N, each time you select the smallest element from the array to be sorted, put it to the left of the array. After n rounds of filtering, the array will be in order.
The illustration below
Suppose you want to select sort the following array
Iterate through the part of the array to be sorted, selecting the smallest element as 1 and placing 1 at the far left of the array
In the second round, iterate over the rest, selecting the smallest element as 2 and placing 2 to the far left.
Thus, the element selected in the third round is 3 and the element selected in the fourth round is 4…. After nine rounds of selection, the array is in order
Its code implementation is also very simple
public void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minPos = i;
for (int j = i + 1; j < array.length; j++) {
if(array[minPos] > array[j]) { minPos = j; } } swap(array, i, minPos); }}Copy the codeOptimization idea
Thinking a
Two-way choice
The optimization idea of selection sort is relatively limited. According to the optimization experience of bidirectional bubbling, we can select a maximum value and a minimum value in one round of iteration, so as to improve the efficiency of screening.
Write it in code as follows
public void selectSortDual(int[] array) {
int leftBorder = 0;
int rightBorder = array.length - 1;
while (leftBorder < rightBorder) {
int minPos = leftBorder;
int maxPos = leftBorder;
for (int j = leftBorder + 1; j <= rightBorder; j++) {
if (array[minPos] > array[j]) {
minPos = j;
}
if (array[maxPos] < array[j]) {
maxPos = j;
}
}
swap(array, leftBorder, minPos);
/* If maxPos is equal to leftBorder, the leftBorder element has been swapped to minPos */
if (maxPos == leftBorder) {
/* If maxPos is leftBorder, the following exchange for maxPos will be with minPos */
swap(array, rightBorder, minPos);
} else{ swap(array, rightBorder, maxPos); } leftBorder++; rightBorder--; }}Copy the codeIdea 2
Heap sort
In fact, heap sort is also a variant of selection sort. Heap sorting involves building a heap (big top or small top) on the array, swapping the top and bottom elements each time, logically removing the bottom elements from the heap, adjusting the rest of the heap, swapping the top elements with the current bottom elements, and so on. Each round of sorting appends the heaptop element to the ordered sequence at the end of the array, and the heaptop element is the maximum or minimum selected for each round, so heapsort is also a selective sort.
First, a brief introduction to the heap. The essence of a heap is a complete binary tree. The big top heap, on the other hand, means that the top element (the root node of the binary tree) is larger than any of the nodes in the left and right subtrees, and each of the remaining non-leaf nodes is larger than any of the nodes in the left and right subtrees. The following diagram shows the logical structure of a large top heap
You can see that the top element 9 is larger than its left and right children 8 and 7, and node 8 is larger than its left and right children 4 and 3, and 7 is larger than its left and right children 5 and 6, and 4 is larger than its left and right children 1 and 2. This makes the top of the heap element the largest element. In practice, binary heap is often stored in the form of array, as shown below
The purple numbers represent the subscripts of the elements in the array. The heap starts at the first layer, and each layer is numbered from left to right, which is where it is stored in the array. It is easy to get the following relationship:
If a node in the heap has subscript n in the array, if it has left and right child nodes, then
The subscript of the left child node is 2n + 1
The subscript of the right child node is 2n + 2
If it has a parent node, the subscript of the parent node is (n-1) / 2
Since heaps can be stored and represented as arrays, you can build a heap of arrays and then perform heap sort. The key to heap sort is to build the heap on the initial array and adjust it after swapping the top and bottom elements
The illustration below
Suppose you want to heap sort the following array
First, build the heap (build the big top heap), based on the array, first treat the array as a binary tree
The process of building the heap is as follows: from the bottom up, the first non-leaf node is found (the node without any child nodes, as shown in figure 8). From this node, all non-leaf nodes are sunk (adjusted downward). Sinking refers to comparing a node with its children and swapping if the value of the node is less than the larger of the children. For node 8, first treat node 8 and its children as a heap (local heap) and adjust it so that the local heap meets the characteristics of the big top heap. Node 8 does not need to be discovered.
Then we move forward to node 2, and we find that it is smaller than its children, and the larger of the children is 9, so we swap 2 and 9
We then process node 4 and find that it is less than 8, so we swap it and 8
Note that the sinking process should be sunk to the bottom as far as possible. After 4 and 8 are swapped, continue to process 4. When 4 is found to be smaller than its child node 6, swap 4 and 6
And then we do 1, and if we find that 1 is less than 9, we swap them
I continue with 1, I find that 1 is less than 7, I swap them
Thus, the heap construction operation is completed, and it is observed that the heap now conforms to the characteristics of the big top heap
Once the heap is built, do the following: swap the top element with the bottom element, then logically remove the bottom element from the heap, treat the remaining elements as one heap, and adjust the top element downward to make it one big top heap. It then swaps the top element with the bottom element of the current heap, removes the bottom element from the heap, and continues to adjust the remaining elements….. In this case, the sorting is done.
The illustration below
First, the state of the array after the heap is built is as follows
Swap the top and bottom of the heap elements, 9 and 4
After the exchange, the last-heap element 9 is logically removed from the heap. The heap composed of the remaining elements, because the top of the heap has changed, obviously does not meet the nature of the big top heap, so the new top is adjusted downward
Node 4 is smaller than 8, the larger of its children, so it swaps
!
Continue to adjust node 4 and find that it is smaller than child node 6, then swap it
Continue to adjust node 4 and find that it has only one left child node 3, and 4 is greater than 3, then the adjustment is complete (node 9 has been logically removed from the heap, that is, node 9 is no longer in the heap).
The remaining elements form a heap that conforms to the properties of a large top heap
Next, we continue to swap the top element with the bottom element of the current heap, swapping 8 and 3
Then the node 8 is removed from the heap, and the current top element 3 is adjusted downward. It is found that only 3 and 7 need to be swapped, and the result after adjustment is
Then swap the top and tail of the heap, that is, swap 7 and 2
Adjust the heap
Swap top and tail of heap
Adjust the heap
. And so on, we end up with an ordered array
Thus, the key to heap sorting is to build the heap and adjust the nodes downward
Write it in code as follows
public void heapSort(int[] array) {
/* Build the heap */
buildHeap(array);
/* after the loop */
for (int i = array.length - 1; i >= 0 ; i--) {
/* Swap the top element with the current bottom element */
swap(array, 0, i);
/* Adjust the heap */
adjustDown(array, 0, i - 1); }}/** * heap the array ** */
private void buildHeap(int[] array) {
/* Find the first non-leaf node from the right to the left of the array, i.e. from the bottom of the heap up, and adjust it down */
/* The first non-leaf node, which is the parent of the last node */
/* All nodes before the first non-leaf node are non-leaf nodes and need to be adjusted down */
int firstNonLeafNode = (array.length - 1) / 2;
for (int i = firstNonLeafNode; i >= 0 ; i--) {
/* For each non-leaf node, adjust down */
adjustDown(array, i, array.length - 1); }}/** * Adjust a node downward *@paramTargetPos Node (array subscript) * to be adjusted@paramEnd The end position of the heap (array subscript) *@paramThe array of the array heap represents ** */
private void adjustDown(int[] array, int targetPos, int end) {
int leftSonPos;
/* Execute a loop */ when the left son is not out of the heap
while ((leftSonPos = 2 * targetPos + 1) <= end) {
/* If the right son exists, the greater of the left son is chosen, otherwise the left son is chosen */
int maxSonPos = leftSonPos + 1 <= end ?
array[leftSonPos] > array[leftSonPos + 1]? leftSonPos : leftSonPos +1
: leftSonPos;
if (array[maxSonPos] > array[targetPos]) {
swap(array, maxSonPos, targetPos);
targetPos = maxSonPos;
} else {
/* If no child is larger than target, the adjustment ends */
break; }}}Copy the codeNote that the process of downsizing is to sink the node that needs to be adjusted to the appropriate position. Considering the optimization of the previous insertion sort, one-way assignment can also be used here to avoid the performance overhead caused by frequent swapping.
The performance test
The performance test of the algorithm for selecting sort series shows the following results
You can see heap sort outperforms simple selection sort
Extension: application of heap sort
Top K problem
Select the top K largest data from the mass data
Because the amount of data is very large, it is obviously unrealistic to sort all the data and then take the first K number, and there is no need to sort the numbers after the KTH, so sorting the data after K is obviously a waste of performance. If we look at the properties of heap sorting, we find that whether the top of a heap is a big heap or a small heap, the top of the heap is always the largest or the smallest. If a big top heap has K elements, the element at the top of the heap is the largest of K; If a small top heap has K elements, the element at the top of the heap is the smallest of K. Suppose a total of 100 data, requirements to find the largest number K, before you can think so, I’ll take before K element, I need to know the current K element is the smallest value, after each time a new element, with new elements and the minimum ratio, if a new element is less than the minimum value, add new element is less than the all of K element, The new element cannot be the largest number of the previous K, so it is discarded. If the new element is larger than the minimum value, remove the minimum value and replace it with the new element. Then select the minimum value of the current K elements and wait for the subsequent comparison. With this idea, you just need to build a small top heap of size K. First, take the first K numbers from the massive data to build a small top heap. Then the number after K is traversed, one at a time, and compared with the top of the small top heap. If the number is smaller than the top of the heap, it is discarded directly. If it is larger than the top of the heap, the number is swapped with the top of the heap and the heap is adjusted downward to maintain its small-top characteristics. Because only one element needs to be compared with the top of the heap, and the case that is smaller than the top of the heap is discarded directly, and only the case that is larger than the top of the heap needs to adjust the heap, so that the first K largest numbers can be found with high efficiency, the code implementation is as follows
/ * * *@paramArray Array to be searched *@paramK finds the first k smallest number ** */
public int[] findTheSmallestElements(int[] array, int k) {
return findTheMostElements(array, k, false);
}
/ * * *@paramArray Array to be searched *@paramK finds the first k largest number ** */
public int[] findTheBiggestElements(int[] array, int k) {
return findTheMostElements(array, k, true);
}
/** * find the first K largest, or the first K smallest number *@paramBiggest is looking for the biggest ** */
private int[] findTheMostElements(int[] array, int k, boolean biggest) {
/* Build a small top heap for the top K; If you want to find the smallest of the first K, create a big top heap
booleanheapType = ! biggest;/* Build a heap for the first k elements */
buildHeap(array,k - 1, heapType);
/* Traverses */ from the k + 1 element (subscript k)
for (int i = k; i < array.length; i++) {
/* Whether the current element needs to be inserted into the heap of the first k elements */
boolean needInsert = biggest ? array[i] > array[0] : array[i] < array[0];
if (needInsert) {
/* Insert heap */ if needed
swap(array, 0, i);
/* Adjust the heap so that it is still small top heap/big top heap */
adjustDown(array, 0, k - 1, heapType);
}
/* Otherwise, discard */
}
int[] topKElements = new int[k];
/* Take the first k elements of the array as the result */
System.arraycopy(array, 0, topKElements, 0, k);
return topKElements;
}
/ * * *@paramEndPos end heap *@paramBiggestTop Specifies whether to create a large top heap ** */
private void buildHeap(int[] array,int endPos, boolean biggestTop) {
int firstNonLeafPos = (endPos - 1) / 2;
for (int i = firstNonLeafPos; i >= 0; i--) { adjustDown(array, i, endPos, biggestTop); }}/ * * *@paramBiggestTop Specifies whether to create a large top heap ** */
private void adjustDown(int[] array, int targetPos, int endPos, boolean biggestTop) {
int leftSonPos;
while ((leftSonPos = 2 * targetPos + 1) <= endPos) {
int maxSonPos = leftSonPos, minSonPos = leftSonPos;
if (leftSonPos + 1 <= endPos) {
maxSonPos = array[leftSonPos] > array[leftSonPos + 1]? (minSonPos = leftSonPos +1) - 1 :
leftSonPos + 1;
}
boolean needSwap = biggestTop ?
array[maxSonPos] > array[targetPos] :
array[minSonPos] < array[targetPos];
int swapPos = biggestTop ? maxSonPos : minSonPos;
if (needSwap) {
swap(array, targetPos, swapPos);
targetPos = swapPos;
} else {
break; }}}Copy the codePriority queue
Queues are everywhere in life. When I take the subway, I wait in line for the bus. When I go to the canteen, I have to get the number and wait in line. The essence of a queue is a bunch of people who need to perform an action. The simplest and most common queue is one that receives services in a first-come-first-come order. But in some scenarios need to some of the people in the queue priority setting, such as bank for business, VIP customers priority queue is higher than that of ordinary customers, for example, a meal to go to the canteen, if a man has ten days didn’t have a meal, will soon be starved to death, should let him give priority to dozen rice, sure that he will come back to life. In these scenarios, the normal queue is too rigid to meet the requirements, hence the priority queue. The elements in the priority queue are not queued in a strict first-come-first-come order, but the elements with the highest priority are always queued before the elements with the lowest priority, and the elements with the same priority are queued in the first-come-first-come order. The heap, the data structure, can do this because it always puts the largest, or smallest, element at the top of the heap (at the front of the array).
A queue has two basic operations: queue entry and queue exit
Queue: A person joins a queue to queue
Out of line: When it’s someone’s turn to do something, move them out of line
Represented by the structure of the heap, as follows. Let’s start with a person of priority 1 and queue up
Then, along comes someone with priority 9
Obviously, it doesn’t satisfy the nature of the big top heap, so I’m going to adjust the new 9, and I’m going to adjust it up, and I’m going to swap 1 and 9
At this time, another 6 comes, and it is found that it still meets the characteristics of the big top heap, so no adjustment is made
If the queue exits, the top element of the heap is fetched directly, node 9 receives the service, and the array becomes
The logical structure of the heap becomes
If it is found that the characteristics of the big top heap are not met, it can be adjusted by swapping 1 and 6
Each queue exit takes the first element of the array, the top element of the heap, which ensures that each queue exit is the element with the highest current priority
Its core logic is as follows:
-
When enqueued, the new element is appended to the end of the array, the end of the heap, and needs to be adjusted up to meet the big-top heap nature.
-
To exit the queue, remove the first element of the array, treat the remaining elements as a new heap, and rebuild the heap
I will not give the specific code implementation here, interested readers can try their own