Easily master the basic programming algorithms (I)

Easily master the basic programming algorithms (I)

[[121968]]

I haven't updated my blog for a long time. One reason is that the technologies used in the projects I developed are all old technologies, and the knowledge I came into contact with is all industry logic processes, so I just made a summary and didn't share it. Another reason is that I am currently relearning C++ language and some basic computer knowledge (algorithms, etc.).

The following code is C++ code. Let’s get straight to the point.

Basic Programming Algorithms (I)

Basic Programming Algorithms (II)

Basic Programming Algorithms (III)

Binary Search

Also called binary search.

Conditions of use: ordered set.

Algorithm idea: first determine the range (interval) where the record to be searched is located, and then gradually narrow the range until it is found or not found.

The key point is to compare the keyword recorded in the middle position with the given value. If it is greater than the given value (here we assume that the set is arranged from small to large), then the interval range can be narrowed (start of the set --> previous position in the middle), and the keyword recorded in the middle position of the interval is compared with the given value, and the cycle is repeated until the position is found or not found.

Example programming: Here is an integer data int a[10]={1,5,10,13,17,23,65,77,81,93};

(1) This is recursion (thanks to fellow user zdd for pointing out the error in the judgment condition here, which should be changed to if(min>max))

  1. //Binary search  
  2. //The array must be in a certain order  
  3. //Parameters: ***, minimum, target (parameter type is integer)  
  4. int BinarySearch( int min, int max, int num)
  5. {
  6. if (min==max) return -1;
  7. int mid=(min+max)/2;
  8. if (a[mid]==num) return mid;
  9. elseif(a[mid]<num)
  10. {
  11. return BinarySearch(mid+1,max,num);
  12. }
  13. else  
  14. {
  15. return BinarySearch(min,mid-1,num);
  16. }
  17. }

(2) Non-recursive

  1. //Non-recursive algorithm  
  2. int BinarySearch_F( int num)
  3. {
  4. int min=0;
  5. int max=9;
  6. int mid;
  7. while (min<=max)
  8. {
  9. mid=(min+max)/2;
  10. if (a[mid]==num) return mid;
  11. elseif(a[mid]>num)max=mid-1;
  12. else min=mid+1;
  13. }
  14. return -1;
  15. }

Performance analysis: time complexity O(logn)

Insertion Sort

Conditions of use: Collections of comparable sizes.

Algorithm idea: insert a record into the sorted ordered sequence to get a new ordered sequence with the number of records increased by 1. The record to be inserted is compared with the sorted sequence in turn. If the sequence number is greater than the record to be inserted, the sequence is moved back one position until a sequence smaller than the record to be inserted is found. At this time, it is inserted into the next position of the sequence, and the above operation is repeated until all positions are inserted.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17} to sort it

  1. //Insert sort  
  2. //Here temp is the sentinel position  
  3. //From childhood to adulthood  
  4. void InsertSort() {
  5. int temp;
  6. int j;
  7. for ( int i=1;i<10;i++) {
  8. temp=b[i];
  9. for (j=i-1;j>=0;j--) {
  10. if (b[j]>temp) {
  11. b[j+1]=b[j];
  12. }
  13. else {
  14. break ;
  15. }
  16. }
  17. b[j+1]=temp;
  18. }
  19. cout<< "the sort is:" ;
  20. for ( int i=0;i<10;i++) {
  21. cout<<b[i]<< "" ;
  22. }
  23. cout<<endl;
  24. }

Performance analysis: time complexity O (n^2)

Binary Insertion Sort

Conditions of use: Collections of comparable sizes.

Algorithm idea: The basic idea is similar to that of simple insertion sort. The only difference is to find the insertion position. Simple insertion sort uses sequential comparison. Binary insertion sort is improved here, and the sequential search is improved into a binary search.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17} to sort it

  1. void BinaryInsertSort() {
  2. int temp,min,max,mid; int j;
  3. for ( int i=1;i<10;i++) {
  4. min=0;max=i-1;
  5. temp=b[i];
  6. while (min<=max) {
  7. mid=(min+max)/2;
  8. if (b[mid]>temp) {
  9. max=mid-1; }
  10. else { min=mid+1;
  11. }
  12. }
  13. for (j=i-1;j>=max+1;j--) {
  14. b[j+1]=b[j];
  15. }
  16. b[max+1]=temp;
  17. }
  18. cout<< "the sort is:" ;
  19. for ( int i=0;i<10;i++) {
  20. cout<<b[i]<< "" ;
  21. }
  22. cout<<endl;
  23. }

Performance analysis: time complexity O (n^2)

Although the time complexity here is the same as that of simple insertion sort, the number of comparisons used to find the insertion position is significantly reduced.

Original text: http://www.cnblogs.com/couhujia/archive/2011/03/23/1991110.html

<<:  Heap sort algorithm popularization tutorial

>>:  Easily master the basic programming algorithms (Part 2)

Recommend

Where will Changhong’s state-owned enterprise reform path go in the future?

In the era of mobile Internet, companies seeking ...

How to use Zhihu for marketing promotion? Zhihu marketing promotion methods!

What is it like for a brand to do marketing on Zh...

Yan Jie 14-day extreme waist and abdomen shaping

Yan Jie's 14-day ultimate waist and abdomen s...

5 steps to operate Internet users!

As the link closest to users, user operations are...

How to create a personal IP? 3800 words super detailed tutorial

I thought about a hundred or eighty projects, but...

How does Baidu bidding analyze the market?

Before bidding analysis, you should first pay att...

How do smartwatches and fitness trackers reveal our mental state?

Planner: Chinese Medical Association Reviewer: Li...

How to master TCM differentiation in 24 days at Yichengyoudao Academy

How to master TCM syndrome differentiation in 24 ...

Are there any reasons why SEM promotions are not effective?

Why does the problem of poor SEM promotion effect...

Seven Reasons to Use AngularJS to Develop Your Next Web App

[[149184]] Original text: 7 Reasons to use Angula...

8 directions to create Douyin catering influencers!

From Haidilao, McDonald's, to Coco, Naixue...