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.
Sort 2(merge, fast, heap sort)
5. Merge sort
【 Algorithm idea 】 : Using the algorithm idea of divide and conquer, the original array is divided into A,B two subarrays, and then A,B two subarrays continue to divide into A1L,A1R, B1L,B1R four subarrays, continue to divide until the number of elements in the array is 1, that is, the array is orderly; And then merge the contiguous array data.
The core is divided into 3 steps:
The first, Divided, corresponds to the function Divided().
Second, Conquer and do related processing.
Third, Merge, corresponding to the MergeArray() function.
Step diagram:
| The array subscript | a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | a[9] | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Element value | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
| Divided | 1 | first | * * * * | * * * * | * * * * | mid | * * * * | * * * * | * * * * | * * * * | last |
| 2 | first | * * * * | mid | * * * * | last | * * * * | * * * * | * * * * | * * * * | * * * * | |
| 3 | first | mid | last | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | |
| 4 | first&mid | last | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | |
| * * * * | |||||||||||
| Merge | 5 | first&mid | last | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| 6 | first | mid | last | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | |
| * * * * | |||||||||||
| Divided | 7 | * * * * | * * * * | * * * * | first&mid | last | * * * * | * * * * | * * * * | * * * * | * * * * |
| Merge | 8 | * * * * | * * * * | * * * * | first&mid | last | * * * * | * * * * | * * * * | * * * * | * * * * |
| Merge | 9 | first | * * * * | mid | * * * * | last | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | |||||||||||
| Divided | 11 | * * * * | * * * * | * * * * | * * * * | * * * * | first | * * * * | mid | * * * * | last |
| 12 | * * * * | * * * * | * * * * | * * * * | * * * * | first | mid | last | * * * * | * * * * | |
| 13 | * * * * | * * * * | * * * * | * * * * | * * * * | first&mid | last | * * * * | * * * * | * * * * | |
| * * * * | |||||||||||
| Merge | 14 | * * * * | * * * * | * * * * | * * * * | * * * * | first&mid | last | * * * * | * * * * | * * * * |
| 15 | * * * * | * * * * | * * * * | * * * * | * * * * | first | mid | last | * * * * | * * * * | |
| * * * * | |||||||||||
| Divided | 16 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | first&mid | last |
| Merge | 17 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | first&mid | last |
| Merge | 18 | * * * * | * * * * | * * * * | * * * * | * * * * | first | * * * * | mid | * * * * | last |
| * * * * | |||||||||||
| Merge | 19 | first | * * * * | * * * * | * * * * | mid | * * * * | * * * * | * * * * | * * * * | last |
[Algorithm implementation] :
template <typename T>
void MergeSort(T a[], int N)
{
int*pTmpArray = new int[N]; // Temporary storage. Archived with!
if(pTmpArray== NULL)
{
cout<< "Allocate Error!" << endl;
}
intfirst = 0;
intlast = N- 1;
Dirvied(a,first,last,pTmpArray);
delete[]pTmpArray;
}
// Merge arrays
template <typename T>
void MergeArray(T a[], int first, int mid, int last, int tempArr[])
{
inti = first;
intj = mid+1;
intm = mid;
intn = last;
intk = 0;
// Neither array is empty
while(i<= m && j <= n)
{
if(a[i]< a[j])
{
tempArr[k++]= a[i++];
}
else{ tempArr[k++]= a[j++]; }}// The following two loops represent an empty array.
while(i<= m)
{
tempArr[k++]= a[i++];
}
while(j<= n)
{
tempArr[k++]= a[j++];
}
// Temporarily stored elements are dumped into array A.
for(i = 0; i < k; i++)
{
a[first+i]= tempArr[i]; // Note the starting point here.}}// Decompose [recursive function]
template <typename T>
void Dirvied(T a[], int first, int last,int tempArr[])
{
intmid;
if(first< last)
{
mid= (first + last)/2;
Dirvied(a,first,mid,tempArr);// Left half.
Dirvied(a,mid+1,last,tempArr);// Right half.
MergeArray(a,first,mid,last,tempArr); }}Copy the code\
6. Quicksort
[Algorithm idea] : Adopt divide-and-conquer algorithm idea: 1) Select pivot element initially and record pivot element and left, traverse from back to front first, the value less than the pivot is exchanged with the left position element; It then traverses from front to back, swapping elements larger than the pivot with elements in the right position until left>=right completes the traversal. 2) After a traversal, it is guaranteed that the elements to the left of the pivot are less than the pivot value and the elements to the right of the pivot are greater than the pivot value. Note the position of the pivotPos after the switch. 3) Recursively call 1) and 2) for the elements on the left of pivotPos and the elements on the right of Pivot. Until all ordered after the end.
The core is divided into 3 steps:
The first, Divided, corresponds to the function Divided().
Second, Conquer and do related processing.
Third, Merge. Divide() ensures that some elements are ordered after each Divide() (large and small on one side).
| pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| * * * * | 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
| pivot=72 | < – 48 | * * * * | * * * * | < – 42 | * * * * | left=right | * * * * | * * * * | 88 – > | * * * * |
| * * * * | < – 48 | 6 | 57 | < – 42 | 60 | 72 | 83 | 73 | 88 – > | 85 |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=48 | 48 | 6 | 57 | 42 | 60 | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | < – 42 | * * * * | left=right | 57 – > | 60 | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | < – 42 | 6 | 48 | 57 – > | 60 | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=42 | 42 | 6 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | < – 6 | 42 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=57 | * * * * | * * * * | * * * * | 57 | 60 | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | 57 | 60 | * * * * | * * * * | * * * * | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=83 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 83 | 73 | 88 – > | 85 |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 73 | 83 | 88 – > | 85 |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=73 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 73 | 83 | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 73 | 83 | * * * * | * * * * |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * |
| pivot=88 | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 88 | 85 |
| * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | * * * * | 85 | 88 |
| Sorting result | 6 | 42 | 48 | 57 | 60 | 72 | 73 | 83 | 85 | 88 |
[Algorithm implementation] :
// Select pivots and divide by pivots [left is smaller than pivot element, right is larger than pivot element]
template <typename T>
int Partition(T a[], int left, int right)
{
swap(a[left],a[(left+right)/2]);// Switch the middle element as the pivot element.
T pivot = a[left]; // Hold pivot elements temporarily for comparison
while(left< right)
{
while(left< right && a[right] >= pivot)
{
--right;
}
a[left]= a[right]; //[left] stores values smaller than the pivot element;
while(left< right && a[left] <= pivot)
{
++left;
}
a[right]= a[left]; //[right] stores values larger than the pivot element;
}
a[left]= pivot; // Place the pivot in a new position
return left;
}
// a recursive function
template <typename T>
void QuickCurve(T a[], int left, intright)
{
intpivotPos = 0;
if(left < right)
{
pivotPos= Partition (a,left,right); // Get the position of the pivot split to divide the left and right.
QuickCurve(a,left,pivotPos- 1); // Right margin -1
QuickCurve(a,pivotPos+1,right);// Left margin +1}}/ / fast row
template <typename T>
void QuickSort(T a[], int N)
{
QuickCurve(a,0,N- 1);//left=0, right=N-1
}
Copy the code\
7. The heap sort
[Algorithm elicitation] : it is an improved algorithm of simple selection sorting algorithm. In simple selection sorting, each comparison selects a minimum value, but the comparison of the next trip will repeat the previous comparison result, there is repetition. Heapsort improves on this in that every time you select the minimum value, you adjust the other values based on the result.
[Concept of heap] : heap is a complete binary tree with the following properties, each node is greater than or equal to the value of the left and right child nodes, called the big top heap; Each node is less than or equal to the values of the left and right child nodes, called the small top heap.
[Algorithm idea] : Taking the small top heap as an example, (1) first construct a small top heap, that is, the top of the heap is the minimum value of all elements; (2) Second, swap the top element with the end element, which stores the smallest element at the end of the heap; (3) Remove the last element of the heap, and repeat operations (1) and (2) for the remaining N-I elements to complete the sorting.
[Algorithm implementation] :
// Build and adjust the small top heap.
// The big top heap can be adjusted in the same way as the small top heap.
//arr[j] > arr[j], arr[j] <= temp
template<typename T>
void heapAdjust(T arr[], int i, int N)
{
intj;
inttemp = arr[i]; // Temporary storage requires node information.
j= i*2+1; // Left child node
while(j< N)
{
if(j+1< N && arr[j+1] < arr[j])
{
j++; // Take the smallest of the left and right children.
}
if(arr[j]>= temp)
{
break; // Small top heap, if the child has a large value, then terminate the loop.
}
// Find if there is a child node of child node.
arr[i]= arr[j];
i= j;
j= 2*i + 1;
}//endwhile
arr[i]= temp; // Store the new location.
}
// heap sort.
template<typename T>
void heapSort(T arr[], int N)
{
// Build a small top heap, initially messy, adjusted to a small top heap
for(int i = N- 1; i >= 0; i--)
{
heapAdjust(arr,i/2,N- 1);// Start in the middle.
}
for(int i = N- 1; i >= 0; i--)
{
swap(arr[i],arr[0]);
heapAdjust(arr,0,i); // The size of the termination is I, and only the root node is adjusted each time.}}Copy the code
\