Easily master the basic programming algorithms (Part 2)

[[121970]]

Before writing this article, I want to talk about the basic knowledge of programmers. Many people are talking about their work experience or giving advice to graduates. I agree with their advice to students to lay a good foundation in computer in school. How can you build a building without a good foundation? With some basic knowledge, it will be twice as effective to learn deep theories. If you encounter deep theories first and then learn related foundations, it will be twice as effective. Maybe many students will say that many companies now recruit people who can get started directly. First of all, I want to say that such companies must be small companies with short-sightedness. They can't find very good talents. Even if they go, such talents will not stay for a long time, because such companies have no vision for development, and technical talents may change jobs because of no development prospects. Secondly, I want to say that if you have a good computer foundation, I believe you can successfully learn and adapt to meet the technical requirements of the company within three months.

In fact, what I want to say is that you should never ignore the basics. Without further ado, let's go straight to the basic sorting algorithm.

Basic Programming Algorithms (I)

Basic Programming Algorithms (II)

Basic Programming Algorithms (III)

Bubble Sort

Conditions of use: The elements of the collection can be compared in size

Algorithm idea: Continuously scan the records to be sorted. Each scan will find the minimum record and bring it closer to the top. Since each scan will place a record in its final and most correct position, the next scan does not need to recheck this record.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17} will be bubble sorted (I have confused the concepts here, thanks to zdd for pointing it out)

 //Bubble sort  
 void Bubble( int b[10])
 {
 int temp;
 int i;
 for (i=9;i>0;i--)
 {
 for ( int j=0;j<i;j++)
 {
 if (b[j]>b[j+1])
 {
 temp=b[j];
 b[j]=b[j+1];
 b[j+1]=temp;
 }
 }
 }
 cout<< "the sort is:" ;
 for ( int i=0;i<10;i++)
 {
 cout<<b[i]<< " " ;
 }
 cout<<endl;
 }

Performance analysis: time complexity O(n^2)

Shell sort

Conditions of use: The elements of the collection can be compared in size

Algorithm idea: First, divide the entire sequence of records to be sorted into several subsequences and perform direct insertion sorting on each of them. When the records in the entire sequence are "basically ordered", perform direct insertion sorting on all records. The subsequence is not simply "divided piece by piece", but a subsequence is composed of records separated by a certain "increment". Therefore, when comparing and sorting, the records with smaller keywords do not move forward step by step, but move at a certain increment. The "increment" shows a decreasing trend. In the end, this "increment" is always 1. At this time, the sequence is basically ordered, and only a small number of comparisons and moves are required to complete the sorting. It is difficult to grasp the setting of increments in Shell sorting. Generally, for 8 numbers, we think that the "increment" is set to: 4, 2, 1. (This is the general setting of Shell sorting). So the author here is going to formulate a formula for "increment" h(n+1)=3*h(n)+1, (stop when h>N/9) This formula may not choose the most appropriate increment, but it is applicable to the general "increment" setting. If it is 8 numbers, then the increment here is 1.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17} sorts its shell

 //Hill sort auto-increment needs to be selected by yourself  
 void ShellSort( int b[10])
 {
 int h,i;
 int n=10;
 //Through this loop, we calculate the increments to 1 and 4  
 for (h=1;h<=n/9;h=3*h+1); 
 
 //Increment loop  
 for (;h>0;h/=3)
 {
 for (i=h;i<n;i++)
 {
 int j,temp;
 temp=b[i];
 //Insert sort  
 for (j=ih;j>=0;j=jh)
 {
 if (b[j]>temp)
 {
 b[j+h]=b[j];
 }
 else  
 {
 break ;
 }
 }
 b[j+h]=temp;
 }
 }
 cout<< "the sort is:" ;
 for ( int i=0;i<10;i++)
 {
 cout<<b[i]<< " " ;
 }
 cout<<endl;
 }

Performance analysis: The time complexity for Hill sort is a bit complicated. It varies according to the specific "increment". Here, the author uses O(n^3/2) from Yan Weimin's "Data Structure"

Quick Sort

Conditions of use: Collections of comparable sizes.

Algorithm idea: Split the records to be sorted into two independent parts through a sorting process. If the keywords of one part of the records are smaller than the keywords of the other part, the two parts of the records can be sorted separately to finally reach an ordered sequence. There is a key point here, which is to select the "benchmark" for splitting. It must be that the records greater than this "benchmark" are divided into one part, and the records less than this "benchmark" are divided into another part. Here, the author defaults to taking the first record of the part as the "benchmark".

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

 //Quick sort  
 void QuickSort( int *b, int low, int high)
 {
 //Swap function  
 void Sawp( int *a, int *b);
 int Old_low=low;
 int Old_high=high;
 while (low<high)
 {
 while (*(b+high)>=*(b+low)&&low<high)high--;
 Sawp(b+low,b+high);
 while (*(b+low)=<*(b+high)&&low<high)low++;
 Sawp(b+low,b+high);
 }
 if (Old_low<low-1)
 {
 QuickSort(b,Old_low,low-1);
 }
 if (high+1<Old_high)
 {
 QuickSort(b,high+1,Old_high);
 }
 } 
 
 //Swap function  
 void Sawp( int *a, int *b)
 {
 int temp;
 temp=*a;
 *a=*b;
 *b=temp;
 }

Performance analysis: time complexity O(nlogn)

Original text: http://www.cnblogs.com/couhujia/archive/2011/03/24/1993373.html