Internal sort - insert sort

Internal sorting is divided into ： Insertion sort , Exchange sort , Selection sort , Merge sort , Cardinality sorting these five .

1. Insertion sort

Insert sort is divided into ： Direct insert sort , Binary Insertion Sort ,2- Path insertion sort , Shell Sort . Among them, Hill sort is the best .

• 
  
  Direct insert sort

This is easier to understand , But it's more difficult to operate , This method is not recommended .

Suppose we have such a set of numbers ：49 38 65 97 76 13 27 49

We start from the first 49 Start sorting ,（49）.

Look at the next number at a time 38, because 38 Than 49 Small , So it's in 49 front ,（38 ,49） Sort by this rule at a time .

（38 49 65）

（38 49 65 97）

（38 49 65 76 97）

（13 38 49 65 76 97）

（13 27 38 49 65 76 97）

（13 27 38 49 49 65 76 97）（ notes ： The last in the original sequence 49 With the first 49 identical , When sorting, the last of the original sequence 49 It should be first in the original sequence 49 Behind .）

Algorithm is as follows ：

Void InsertSort(SqList &L) {

 for (i= 2; i<L.Length; ++i )

 if LT(L.r[i].key,L.r[i-1].key){ 

 L.r[0] =L. r [1]; 

 L. r[i] = L.r[i-1];

 for (j =i-2;LT(L.r[0].key,L.r[i].key);--j)

 L.r[j+1] =L. r[i];

 L.r[j+1]=L.r[0]; 

 }

}InsertSort

• 
  
  Half insertion method

Half insert sort is to insert in the ordered table .

As shown in the figure ,1 2 3 4 Is an ordered table ,5 6 7 8 9 10 11 For the sub table to be sorted . The first number in the ordered table low, The last one is high, The middle number mid. The number of sub tables is the same as mid Compare , Less than mid stay mid Sort before , Greater than mid stay mid Sort later .

Algorithm ：

void BInsertSort(SqList & L ) { 

for (i=2;i<= L .length; ++i) {

L. r[0] = L. r [i]; 

low=1;high=i-1;

while (low<= high) { 

m =(low + high)/2;

ifLTL.r[0].key,L.r[m].key)high=m-1;

else low = m+1; 

}// while

for( j = i-1; j>= high +1;-- j) L.r[j+1] = L. r[j];

 L.r[high+1]= L.r[0];

}// for

}// BInsertSort

• 
  
  2- Path insertion sort （ Not very often ）

2- Path insertion sort is a development based on half insertion sort . Its purpose is to reduce the number of record moves in the sorting process , But for this, we need n A secondary space for records .

The specific way is : Set another and L.r Arrays of the same type d, First of all, will L.r[1] Assign a value to d[1l, take d[1] As a record in the middle of a well ordered sequence , And then from L.r pass the civil examinations 2 Records are inserted into d1l In an ordered sequence before or after . First combine the keywords of the records to be sorted with d1] Keyword comparison , if L.r[i].key<d[1] .key, Will L.r[i] Insert into d[1] In the previous ordered table . conversely , take L.ril Insert into d1l In the following ordered table .

When implementing the algorithm , take d As a cyclic vector , And set two pointers first and final Respectively indicate that the first record and the last record in the ordered sequence obtained in the sorting process are d Position in .

• 
  
  Shell Sort （ a key ）

principle ： First, divide the whole record to be sorted into several subsequences to be sorted separately “ Direct insert sort ” Insert sort . Sort with the same color , The interval is best odd .

Algorithm

void ShellInsert(SqList&Lintdk){(dk For span ,r[0] Is a temporary storage unit j<=0, Insert location found )

for(i=dk+1;i<=L.length;++i){( Control the number of sub tables to sort )

ifLT(L.r[i].key,L.r[i-dk].key) (L.ri It is a record to be sorted and is less than ) 

L.r[0] = L.r[i]; ( take L.r[i] Staging to L.r[0]) 

for(j=i-dk;j>0 &&LT(L.r[0].key,L.r[i].key);j - = dk)

L.r[j+dk]=L.r[i]; ( Move records larger than the inserted value backwards ) 

L.r[j+dk]=L.r[0]; ( Insert ) 

}

} ShellInsert

void ShellSort( SqList &L, int dita[], int t ) { (dita[0... t-1]  Storage span

Array of )

for ( k = 0 ; k<t; ++ k) 

ShellInsert(L, dita[k]);( from dita[ k] Get span )

}ShellSort

summary

• 
  
  Direct insertion sort is a good sort method when the number is very small , But it doesn't apply to too many .

• 
  
  Half insert sort is an improvement of direct sort , It is to find the position of records to be sorted in the ordered sub table , Use half search , Reduce comparison time .

• 
  
  2- Path insertion sort is a development based on half insertion sort . Its purpose is to reduce the number of record moves in the sorting process , But for this, we need n A secondary space for records .

• 
  
  Hill sort is to interval the sequence of numbers with odd numbers , Sorted by the number of intervals .（ It must be odd ） This method is better , But not stable . Pay attention to this method .