Data Structure Interview 10 — Sort 1 (Direct Insert, Hill, Bubble, Direct select Sort)

\

Note: There are related exercises in the interview book, but the idea is relatively unclear, and there are typesetting mistakes. The author has rewritten the relevant books and his own views for your reference.

Data structure interview 10 — Sort 1 (Direct insert, Hill, bubble, direct select sort)

1. Insert sort directly

[Algorithm idea] : Insert one element to be sorted into the previously sorted sub-sequence each time until all elements are inserted.

[Algorithm implementation] :

// The simplest implementation of sorting.

template <class T>
void directInsertSort(T arr[],int N)
{
       inti;
       intj;
       for( i = 1; i < N; i++)
       {
              for(j= i- 1; j >= 0 && arr[j+1] < arr[j]; j--) {swap(arr[j+1],arr[j]);
              }//endfor
       }//endfor
}
Copy the code

// Insert sort directly [mobile version]

template <class T>
void directInsertSort(T arr[], int N)
{
       inti;
       intj;
       for( i = 1; i < N; i++)
       {
              inttemp = arr[i];
              for(j = i- 1; j >= 0 && temp < arr[j]; j--)
              {
                     arr[j+1]= arr[j];  / / after the moving
              }
              arr[j+1]= temp;        // Find the insertion position.}}Copy the code

\

2. Hill sort

[Algorithm idea] : The sequence to be sorted according to the step size of the molecular sequence, the sub-sequence of direct insertion sort, and then decrease the step size until 1 (minimum step size), so that the whole sequence will be basically ordered, and then the last direct insertion sort.

[Algorithm implementation] :

template<class T>
void ShellSort(T arr[], int N)
{
       inti;
       intj;
       intstep;
       for( step = N/2; step > 0; step/=2)
       {
              for(i= step; i < N; i++) // Note that the increment step is 1.
              {
                     for(j= i-step; j >=0 && arr[j+step] < arr[j]; j-=step)
                     {
                            swap(arr[j+step],arr[j]);
                     }//endfor j
              }//endfor i
       }//endfor step
}
Copy the code

\

Hill sort, can be seen as an improved algorithm of direct insert sort, on the basis of direct insert sort more outer loop, descending step size, finally complete the sort.

3. Bubble sort

[Algorithm idea] : 1) Compare the sequence elements to be sorted in pairs. If the first element is larger than the second element, the exchange is performed; 2) After this sorting, ensure that the element with the largest value is at the bottom; 3) repeat 1), 2) until N==0.

[Algorithm implementation] :

// Classic bubbling

template<typename T>
void BubuleSort(T a[], int N)
{
       inti,j;
       for(i= 0; i < N; i++)
       {
              for(j= 0; j < N-i- 1; j++)
              {
                     if(a[j]> a[j+1])
                     {
                            swap(a[j],a[j+1]);
                     }//endif j
              }//endfor j
       }//endfor i
}
 
Copy the code

\

// Improved + whether to exchange tokens

template<typename T>
void BubuleSort(T a[], int N)
{
       inti,j;
       boolbExchange = true;         // Set to true initially
       for(i= 0; i < N && bExchange; i++)
       {
              bExchange= false;        // Set to false when entering the loop
              for(j= 0; j < N-i- 1; j++)
              {
                     if(a[j]> a[j+1])
                     {
                            swap(a[j],a[j+1]);
                            bExchange = true;// True if there is a swap.
                     }//endif j
              }//endfor j
       }//endfor i
}
Copy the code

4. Select sort

[Algorithm idea] : With direct insertion sort, the element is divided into ordered area and disordered area. The difference is that direct insertion sort inserts the first element in the unordered region into the ordered region to form a larger ordered region. And selection sort is to select the smallest element from the unordered region and put it at the end of the ordered region.

[Algorithm implementation] :

template <class T>
void SelectSort(T arr[], int N)
{
       intminPos;
       for(int i = 0; i < N; i++)
       {
              minPos= i;
              for(intj=i+1; j<N; j++)
              {
                     if(arr[j]< arr[minPos])
                     {
                            minPos= j;
                     }//endif
              }//endfor
              if(minPos! = i) {swap(arr[minPos],arr[i]);/ / exchange}}}Copy the code

\