📑 Content of this article: 23 design patterns. This column allows you to learn how to beat me - behavioral model - strategic pattern
📘 Article column: There are 23 design patterns in Java
🎬 Last updated: January 2, 2022 23 kinds of design patterns this column allows you to learn so hard that you won't beat me - structural model (Part I) - adapter mode, bridge mode, combination mode
🙊 Personal profile: a Junior Program ape who is studying in a two-year college. In line with paying attention to foundation, clock in algorithm and sharing technology, as a blogger who summarizes personal experience, although he may be lazy sometimes, he will stick to it. If you like blog very much, it is suggested to look at the following line ~ (crazy hint QwQ)
🌇 give the thumbs-up 👍 Collection ⭐ Leaving a message. 📝 One key three connection care program ape, start with you and me
🌟 preface 🌟
Six principles under 23 design modes
No matter what design mode, it is based on six design principles:
- Open and closed principle: a software entity such as class, module and function should be closed to modification and open to extension.
- Single responsibility principle: a class does one thing, and a class should have a reason for its modification.
- Richter substitution principle: the subclass should be able to completely replace the parent class. In other words, when using inheritance, only extend the new functions without destroying the original functions of the parent class.
- Dependency Inversion Principle: details should depend on abstraction, and abstraction should not depend on details. Put the abstraction layer on the high level of program design and keep it stable. The detailed changes of the program are completed by the underlying implementation layer.
- Interface separation principle: the client should not rely on the interface it does not need. If some methods of an interface are empty implemented by the client due to redundancy during implementation, the interface should be split so that the implementation class only needs the interface methods it needs.
- Dimitri's Law: the principle of least knowledge to minimize the coupling between classes; An object should have the least understanding of other objects.
📝 Strategy
Behavioral Patterns -- Strategy
outline
What is the strategy model? How to understand?
Popular understanding: for example, if we need to do the same thing but have multiple solutions, we can encapsulate these methods separately (we call each encapsulated method strategy). According to the needs of different scenarios, we can choose different strategies - call different methods to achieve our unified purpose.
Definition of policy pattern
Strategy Pattern: defines a series of algorithms, encapsulates each algorithm into a travel strategy, and each strategy can be replaced with each other. The Strategy Pattern allows each algorithm to change independently of the customers who use it.
According to our commonly used sorting algorithms, for example, there are many sorting algorithms, such as bubble sorting, quick sorting, bucket sorting, selection sorting, insertion sorting, etc. each sorting algorithm is different, but the purpose result is to sort the data, which can be defined using the above-mentioned strategy mode.
Example explanation strategy mode
Here we use different sorting methods to formulate different sorting strategies, so that they can complete the sorting function~
From simple to deep, review the 8 sorting algorithms to deepen the understanding of the strategy mode.
Before there is no design pattern, we usually design interfaces to make different classes implement corresponding interfaces and complete their own unique methods.
We can construct a SortInterface first:
/***
* @author: Alascanfu
* @date : Created in 2022/2/25 17:01
* @description: The sorting interface is used to implement the corresponding functions of different sorting methods
* @modified By: Alascanfu
**/
public interface SortInterface {
int[] sort (int[] arr);
}
In this way, we have obtained an interface for implementing our sorting function for different methods. We only need to create the corresponding entity class to implement the interface.
Here, Xiaofu will review the 8 major orders and deepen his understanding of the strategic model again~
☀️BubbleSort
Bubble sorting
Students who have studied data structure should know that bubble sorting belongs to internal sorting and exchange sorting.
Basic idea and idea of bubble sorting:
- Through the sequence to be sorted, two adjacent elements are compared from front to back. If the reverse order is found, the elements are exchanged, so that the larger values of the elements are gradually exchanged and moved backward.
/***
* @author: Alascanfu
* @date : Created in 2022/2/25 17:03
* @description: Bubble sorting
* @modified By: Alascanfu
**/
public class BubbleSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
for (int i = 0 ;i < arr.length ;i++){
for (int j = 0 ; j < arr.length - i - 1;j++){
// Compare two adjacent elements in order, and exchange if flashback
if (arr[j] > arr[j+1]){
int tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
☀️InsertSort
Insert sort
Basic idea and idea of insertion sorting:
- `By default, the first element is considered to have been sorted, and the pre judgment is carried out one by one from the second element. If the insertion position of the current data is in positive order, there is no need to move the pre element backward. On the contrary, the flashback needs to move the pre element backward and insert the data into the appropriate position.
/***
* @author: Alascanfu
* @date : Created in 2022/2/25 19:35
* @description: Insert sort
* @modified By: Alascanfu
**/
public class InsertSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
// You need to start with the second element (the element with subscript 1)
for (int i = 1 ;i< arr.length;i++){
// Record the elements that currently need to be sorted
int currentNum = arr[i];
// Sort from back to front
int j = i-1;
// If the current element is less than the value of the previous element, move back
while (j >= 0 && currentNum < arr[j]){
arr[j+1] = arr[j];
// Pointer forward
j--;
}
// Insert the element at the position where the current element needs to be inserted
arr[j+1] = currentNum;
}
return arr;
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
☀️SelectionSort
Select sort
Basic idea and idea of selection and sorting:
- The main idea of selecting sorting is to compare and sort the elements according to the current subscript element. Each traversal finds the subscript of the smallest element in the current traversal data, and exchange its subscript element with the current element.
/***
* @author: Alascanfu
* @date : Created in 2022/2/25 19:27
* @description: Select sort
* @modified By: Alascanfu
**/
public class SelectionSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
for (int i = 0 ; i < arr.length;i++){
// Initialize to set the current element subscript to the minimum element subscript
int minIndex = i;
// Start traversing to find the subscript of the smallest element, and use the rolling variable minIndex to make corresponding records
for (int j = i + 1;j < arr.length;j++){
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// Find the smallest element and exchange it with the current element
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
return arr;
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
☀️ShellSort
Shell Sort
Basic idea and idea of Hill ranking:
- The initial incremental grouping is half of the number of arrays, and each grouping is directly inserted and sorted.
- Then reduce the increment to insert and sort again, and so on until the increment is reduced to 1, only the current array has completed the sorting operation.
/***
* @author: Alascanfu
* @date : Created in 2022/2/25 21:25
* @description: Shell Sort
* @modified By: Alascanfu
**/
public class ShellSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
// Set an increment to half the length of the current array
int gap = arr.length / 2;
// Sort until the incremental grouping is reduced to 1
while (gap > 0 ){
// Insert sort for pairwise grouped elements
for (int i = gap ; i< arr.length;i++){
int gapNum = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > gapNum){
arr[gap + preIndex] = arr[preIndex];
preIndex -= gap;
}
arr[gap + preIndex] = gapNum;
}
gap /= 2;
}
return arr;
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
☀️QuickSort
Quick sort
Basic idea and idea of quick sorting:
- We can select a pivot from the array
- Traversing the array places the data larger than the cardinality on the right side of the cardinality and the data smaller than the cardinality on the left side of the cardinality. After traversing, the array is divided into left and right groups of elements.
- Treat the left and right groups of elements as arrays, and repeat the above steps until the sorting is completed.
/***
* @author: Alascanfu
* @date : Created in 2022/2/26 16:34
* @description: Quick sort
* @modified By: Alascanfu
**/
public class QuickSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
quickSort(arr,0,arr.length-1);
return arr;
}
public void quickSort(int[] arr, int start ,int end){
// Jump out condition
if (start > end){
return ;
}
// Find the coordinates of the intermediate value
int mid = partition(arr, start, end);
// Recursive solution
quickSort(arr,start,mid-1);
quickSort(arr,mid+1,end);
}
public int partition(int[] arr,int start,int end ){
int pivot = arr[start];
int left = start + 1;
int right = end ;
while (left < right){
while (left < right && arr[left] <= pivot) {
left++;
}
while (left < right && arr[right] >= pivot) {
right--;
}
if (left < right){
swap(arr,left,right);
left++;
right--;
}
}
if (left == right && arr[right] > pivot){
right--;
}
swap(arr, start, right);
return right;
}
// Exchange function
public void swap(int[] arr ,int num1 ,int num2 ){
int tmp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = tmp;
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
A simpler understanding of fast platoon
K-god's fast scheduling solution: K-god graphic fast platoon
class Solution {
public void quickSort(int arr[],int left ,int right ){
if (left >= right)return ;
int i = left;
int j = right;
while (i < j){
while (i < j && arr[j] >= arr[left])j--;
while (i < j && arr[i] <= arr[left])i++;
swap(arr,i,j);
}
swap(arr,i,left);
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
public void swap(int arr[],int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
☀️MergeSort
Merge sort
Basic ideas and ideas of merging and sorting:
- The idea of divide and rule
- We first divide the array into two areas: the left area and the right area. Repeat the above operation until it is divided into an array of one element, then sort and merge them in pairs, and finally complete the sorting operation.
/***
* @author: Alascanfu
* @date : Created in 2022/2/26 15:21
* @description: Merge sort
* @modified By: Alascanfu
**/
public class MergeSort implements SortInterface{
@Override
public int[] sort(int[] arr) {
mergeSort(arr,0, arr.length-1);
return arr;
}
public void mergeSort(int[] arr,int left ,int right ){
// Recursive termination condition
if (left == right)return ;
// Half grouping
int mid = left + (right - left)/2;
// The group on the left is divided recursively by half again
mergeSort(arr,left,mid);
// The group on the right side is divided recursively by half again
mergeSort(arr,mid+1,right);
// Sort and merge the divided groups
merge(arr,left,mid,right);
}
public void merge(int[] arr ,int left,int mid ,int right ){
// Record results
int tmp[] = new int [right - left + 1];
// Record result pointer
int resultIdx = 0 ;
// Starting position of left array pointer of half array
int cur1 = left;
// Starting position of right array pointer of half array
int cur2 = mid + 1;
// Sort and merge arrays
while (cur1 <= mid && cur2 <= right){
tmp[resultIdx++] = arr[cur1] < arr[cur2] ? arr[cur1++] : arr[cur2++];
}
// If there is data left in the divided area, fill the remaining data into the temporary result array separately
while (cur1 <= mid){
tmp[resultIdx++] = arr[cur1++];
}
while (cur2 <= right){
tmp[resultIdx++] = arr[cur2++];
}
// Fill in the results
for (int i = 0 ;i< tmp.length;i++){
arr[left + i] = tmp[i];
}
}
@Test
public void test(){
int[] arr = new int []{5,2,14,32,11,8,9,11,23};
arr = sort(arr);
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
☀️HeapSort
Heap sort
Basic idea and idea of heap sorting:
☀️BucketSort
Bucket sorting
Basic idea and idea of bucket sorting:
After reviewing the eight ranking methods, we will then understand the strategy model.
Environment encapsulation class Sort
Its function: at this time, we have encapsulated different sorting algorithms. According to the definition of policy pattern composition, we only need to encapsulate each algorithm as a policy pattern and call different sorting algorithms for different customer needs.
/***
* @author: Alascanfu
* @date : Created in 2022/3/1 15:49
* @description: Encapsulate different sorting methods selected according to the environment
* @modified By: Alascanfu
**/
public class Sort implements SortInterface{
private SortInterface sort;
public Sort(SortInterface sort) {
this.sort = sort;
}
@Override
public int[] sort(int[] arr) {
return sort(arr);
}
// Users define their own sorting strategies according to their own needs
public void setSort(SortInterface sort){
this.sort = sort;
}
}
In this class, we call setSort method to implement different sorting strategies according to the user's choice.
Of course, if the user does not choose, we can also set a default execution policy for execution.
Of course, this strategy mode is only a simple implementation, and it is also a basic strategy mode, which is more practical for preliminary understanding. The strategy mode used in the current framework is what we should learn and master deeply, and build our own corresponding strategy mode.
Build policy enumeration class SortStrategy
We can slightly modify the current strategy mode to improve it and correct the defects of the Demeter rule caused by it. Because every time we users need to call different strategies, we must know the implementation class of the corresponding strategy in advance. In order to know the situation at least, we can make the following optimization:
We first build a policy enumeration class, and then return to the environment encapsulation class. We can set the enumeration class in factory mode:
/***
* @author: Alascanfu
* @date : Created in 2022/3/1 16:17
* @description: Sorting strategy
* @modified By: Alascanfu
**/
public enum SortStrategy {
/** Bubble sorting*/
BUBBLE_SORT,
/** Insert sort*/
INSERT_SORT,
/** Merge sort*/
MERGE_SORT,
/** Quick sort*/
QUICK_SORT,
/** Select sort*/
SELECTION_SORT,
/** Shell Sort */
SHELL_SORT,
/** Heap sort*/
HEAP_SORT,
/** Bucket sorting*/
BUCKET_SORT
}
Encapsulating environment classes in factory mode
/***
* @author: Alascanfu
* @date : Created in 2022/3/1 15:49
* @description: Encapsulate different sorting methods selected according to the environment
* @modified By: Alascanfu
**/
public class Sort implements SortInterface{
private SortInterface sort;
public Sort(SortStrategy sortStrategy) {
setSort(sortStrategy);
}
@Override
public int[] sort(int[] arr) {
return sort.sort(arr);
}
public void setSort(SortStrategy sortStrategy){
switch (sortStrategy){
case BUBBLE_SORT:
sort = new BubbleSort();
break;
case INSERT_SORT:
sort = new InsertSort();
break;
case MERGE_SORT:
sort = new MergeSort();
break;
case QUICK_SORT:
sort = new QuickSort();
break;
case SELECTION_SORT:
sort = new SelectionSort();
break;
case SHELL_SORT:
sort = new ShellSort();
break;
case HEAP_SORT:
sort = new HeapSort();
break;
case BUCKET_SORT:
sort = new BucketSort();
break;
default:
throw new RuntimeException("There's no such strategy yet.")
}
}
}
Through the above operations, we only need to set the SortStrategy policy in the Sort class. Users do not need to know the specific implementation classes of different policies. The factory mode transfers all responsibilities to the Sort class. We only need to set the policy of Sort, and then we can call the sort() method.
🌟 summary 🌟
Through the rational use of policy mode and factory mode, the pressure on the user side can be greatly reduced. The user only needs to put forward the demand strategy without knowing its internal specific implementation. The factory mode delivers all responsibilities to the factory class, and the policy mode encapsulates different policy methods. In this way, the optimization is easy. In the final analysis, the policy pattern helps us solve the encapsulation classes with different processing methods for the same problem, and we can use different strategies for different requirements.
