Sort 3-select sort and merge sort (recursive implementation + non recursive implementation)

Preface

One 、 Selection sort

Selection sort ： It refers to the largest... In the array to be sorted each time （ Small ） Array elements of values , Exchange the value of this array element with the value of the first array element that is not sorted .

Because it's easy to understand , Then I'll go directly to the code （ A new version of ） The maximum and minimum values are arranged together

void SelectSort(int *arr, int n)
{
    	
	for (int i = 0; i < n - 1;i++)
	{
    
		int maxi = i;
		int mini = i;
		for (int j = i + 1; j < n; j++)
		{
    
			// Looking for big 
			if (arr[j]>arr[maxi])
			{
    
				maxi = j;
			}
			// Looking for a small 
			if (arr[j] < arr[mini])
			{
    
				mini = j;
			}
		}
		Swap(&arr[i], &arr[maxi]);
		if (i==mini)// Determine whether the minimum value is on the first element of the unordered array 
		{
    
			mini = maxi;
		}
		Swap(&arr[n - 1], &arr[mini]);
		n--;
		}
	}
}

details ： In the above code , When the minimum value is at the first element of the unsorted array , We need to judge , Otherwise, the sorting fails , So I added one in the above code if sentence .

summary ：

1. Time complexity ：O(N²)
2. Spatial complexity ：O(1)
3. stability ： unstable

Two 、 Merge sort

Merge sort ： The principle is to assume that the initial sort contains n Elements , It can be seen as n Subsequence , The length of each subsequence is 1, Then merge in pairs , obtain 【n/2】 A length of 2 or 1 An ordered subsequence of ; Merge in pairs ,…, repeat , Until you get a length of n The ordered sequence of .

Recursive implementation

1. decompose ： First decompose the initial sequence into n Subsequence , Just like a tree
2. Merge ： Then merge into ordered subsequences , repeat （ Like the post order traversal of a tree ）
3. We merge into the new array always , Then copy it to the original array

Code ：

void _MergeSort(int* a, int left, int right, int* tmp)
{
    
	if (left >= right)
		return;
 	// Position of decomposition 
	int mid = （left + right） >> 1;
 
	// [left, mid]
	// [mid+1, right]
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);
 
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	// Merge 
	while (begin1 <= end1 && begin2 <= end2)
	{
    
		if (a[begin1] <= a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	// If a subsequence is merged , There is still a part of another subsequence that has not been merged , Then merge directly 
	while (begin1 <= end1)
	{
    
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
    
		tmp[index++] = a[begin2++];
	}
	// Copy to the original array 
 	for(int j=left;j<=right;j++)
 	{
    
 		a[j]=tmp[j];
 	}
	//memcpy(a+left, tmp+left, sizeof(int)*(right - left+1));
}
  
void MergeSort(int* a, int n)
{
    
	assert(a);
	int* tmp = (int*)malloc(sizeof(int)*n);// Open up space 
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);// Finally, free up space 
}

summary :

1. The disadvantage of merging is that it requires O(N) Spatial complexity of , The thinking of merge sort is more about solving the problem of external sort in disk .
2. Time complexity ：O(N*log₂^N)
3. Spatial complexity ：O(N)
4. stability ： Stable

Iterative implementation （ Non recursive ）

This is our big dish , In the non recursive implementation, we use some ideas of hill sorting （ grouping ）, But our grouping is direct consolidation , There is no decomposition in recursion .

1. hold n Subsequences are grouped in pairs , Direct sort merge into ordered （n/2） Subsequence , So back and forth .
2. At this time, we define a number （gap） To divide them , And after every major merger gap Will change , So that the next segmentation .
3. Each subsequence is an interval to be merged

details ：
The above picture is a normal situation , Abnormal conditions are as follows

Synthesize the situation in the above figure ： We need to judge and correct .

1. Situation one and situation three , We can if fall , When there is no second interval to be sorted , Just jump out and merge
2. For case two , We can modify the range of the interval

Code ：（ Pay attention to the division of intervals ）

void _MergeSort(int* a,int* tmp,int begin1,int end1,int begin2,int end2)
{
    
	int i = begin1;
	int j = begin1;
	while(begin1 <= end1 && begin2 <= end2)
	{
    
		//  obtain a[begin1] and a[begin2] The smaller number in the , Move the smaller value 
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//  take [begin1,end1] Put the remaining number in tmp Array 
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	//  take [begin1,end1] Put the remaining number in tmp Array 
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//  take tmp Copy the values of the array to a Array 
	memcpy(a+j, tmp+j, sizeof(int) * i);
}
void MergeSortNonR(int* a,int* tmp,int n)
{
    
	int gap = 1;
	while(gap < n)
	{
    
		int i = 0;
		for(i = 0;i < n;i += 2 * gap)
		{
    
			int begin1 = i,end1 = i + gap - 1,begin2 = i + gap,end2 = i + 2 * gap - 1;
			//  The second interval does not exist 
			if(begin2 >= n)
				break;
			//  The second interval data is not enough gap individual , Correct the range 
			if(end2 >= n)
				end2 = n - 1;
			_MergeSort(a,tmp,begin1,end1,begin2,end2);
		}
		gap *= 2;
	}
}

summary

If you have any questions, please point them out , Learning together , See you next time .