1. Review the last sorting

* Bubble sort one at a time
Select Sort One at a time and place it in the right place
Insert Sort treats an element on the left as an ordered array

Insert elements one by one into an ordered array starting with the second element
Hill Sort Insertion Sort within Step Group
Array Subscripts are naturally ordered. Note the limitations of array Subscripts: 1. Space 2. Positive integer 3. Do not repeat
Box Sorting Divide into boxes and sort the other boxes

2. Binary Search for Divide and Conquer Application

1. Background:

There is a file with 2G phone numbers in it. Look for it.
1. Memory operations are much more efficient than file operations.
2. Sort first

Assume that you have a number of 1-n, how many times can you guess it the fastest?
tips: The results will tell you
                    log2N

        2.mid = l + (r-l)/2

Note: mid=(l+r)/2 is easy to cross (65535or larger)

3. Loop, non-recursive version - >Binary lookup implementation code

int BinarySearch(int arr[], int len,int posData)
{
	int left = 0,right=len-1;
	int mid = left + (right - left) / 2;//Don't recommend left+right to easily go beyond integer range
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (arr[mid] == posData)return mid;
		else if(arr[mid]>posData){right = mid - 1;}//Update Search Scope
		else { left = mid + 1; }
	}
	return -1;
}

4. Recursive Version - >Binary Find Implementation Code

/*2.Recursive Version->Binary Lookup*/
int BinarySearch(int arr[], int left,int right,int posData)
{
	if (left > right)return -1;//Recursive Termination Conditions
	int mid = left + (right - left) / 2;
	if (arr[mid] == posData)return mid;
	else if (arr[mid] > posData) return BinarySearch(arr, left, mid - 1, posData);
	else return BinarySearch(arr, mid + 1, right, posData);
	
}

3. Merge and Sort of Divide and Conquer Application

1. Ideas:

Combine two ordered arrays into an ordered array

2. Steps:

Create Temporary Array
(2) Compare one by one to place elements from two ordered arrays in a temporary array one by one.
Put the rest in a temporary array
(4) Temporary arrays overwrite arrays to be sorted (Note: memcpy is more efficient)

Note: The order of execution can also be seen from the following recursive code, which gives priority to executing the first "minute" continuously until it can no longer be divided, then falls back to the previous level, and then feels a little like a binary tree DFS to 112 ->224 people.

3. Code implementation:

void MergeSort(int* arr, int left, int right)
{
	if (left >= right)return;//Equality and no need to divide
	int mid = left + (right - left) / 2;
	
	MergeSort(arr, left, mid);//Like dfs, we've been searching on this branch all the time
	MergeSort(arr, mid + 1, right);
	Merge(arr, left, mid, right);
}
void Merge(int* arr, int left, int mid, int right)
{
	int* pArr = new int[right - left + 1];
	int k = 0;
	int i = left;//Start of left interval
	int j = mid + 1;//Start of Right Interval
	//1. Compare in turn
	while (i <=mid&&j<=right)
	{
		if (arr[i] < arr[j])
			pArr[k++] = arr[i++];
		else
			pArr[k++] = arr[j++];//Sort from smallest to largest
	}
	//2. There will always be leftovers, just put them in order
	while (i <= mid)pArr[k++] = arr[i++];
	while (j <= right)pArr[k++] = arr[j++];
	//3. Copy back the contents of the temporary array
	memcpy(arr+left, pArr,sizeof(int)*( right - left + 1));

	delete[]pArr;
	pArr = nullptr;
}

Don't forget the remaining copies!!!

4. Fast (grouped) sorting for divide-and-conquer applications

1. Ideas:

Divide the data into two groups: the left side is smaller than the middle value and the right side is larger than the middle value

2. Step: (swap version is not required)

Basic requirements:

(1) Recursive termination conditions!!

(2) a datum point, two moving pointers (make sure the left side of i is less than privot, the right side of J is greater than privot, and the position of privot get_when they meet)

(3) Overlay is used here for less space overhead, which is clever in the middle. When J overwrites I for the first time, i's data is actually saved in the privot. The next time I overwrites J with a value greater than privot, which will make it easier for J to start the next cycle without worrying about losing data, because when I overwrites j, the last j's value already exists where I was last overwritten.

4) Be sure to pay attention to: who covers who!-> In fact, it is also good to remember that the next cycle of j, it must be found in the i cycle a larger number than privot, so assign J to just start the next cycle

Illustration examples:

 

 

 

 

 

 

 

3. Code implementation:

/*①Quick Sort*/
void quick_sort(int* a, int len)
{
	Qsort(a, 0, len - 1);
}
void Qsort(int* a, int left, int right)
{
	if (left >= right)return;  //Notice the recursive termination condition

	int i = left;//Move pointer left
	int j = right;//Move pointer right
	int privot = a[left];//Select a datum point
	while (i < j)
	{//Require that the left side of i be less than privot and the right side of J be greater than privot
		while (i < j && a[j] >= privot) j--;//When the first a[j] is smaller than privot, override
		a[i] = a[j];//->Be aware of the order of coverage. j finds that a small location for i will also facilitate the next i cycle.
		while (i < j && a[i] <= privot)i++;
		a[j] = a[i];
	}//Out of loop means i=j meets, updating the point of encounter - >privot homing
	a[i] = privot;
	
	//recursion
	Qsort(a, left, i - 1);//Sort left
	Qsort(a, i + 1, right);//Sort on the right
}