Bubble sort / heap sort

Bubble sort ： Each cycle is compared in pairs , Move the big back , The final maximum is placed last ,n Data needs running n-1 Trip to .

 

The code is as follows ：

// Bubble sort    Time complexity O（n^2）  Spatial complexity O（1）   stability ： Stable 
void BubbleSort(int* arr, int len)
{
	assert(arr != NULL);
	for (int i = 0; i < len-1; ++i)
	{
		for (int j = 0; j < len - 1 - i; ++j)
		{
			if (arr[j+1] < arr[j])
			{
				int tmp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

I think most people just start writing code of the above type , But then someone optimized the bubble , But the optimization can be said to be very small

// Bubble sort    Time complexity O（n^2）  Spatial complexity O（1）   stability ： Stable 
void BubbleSort(int* arr, int len)
{
	assert(arr != NULL);

	bool tag = true;// Mark    First, set the initial value to true 
	// Traversal from beginning to end is generally , No swap operation , It can be regarded as completely orderly 
	// On the other hand ： Just one swap operation , It cannot be regarded as completely orderly 
	for (int i = 0; i < len-1; ++i)
	{
		tag = true;
		for (int j = 0; j < len - 1 - i; ++j)
		{
			if (arr[j+1] < arr[j])
			{
				int tmp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tmp;
				tag = false;
			}
		}
		if (tag)
		{
			break;
		}
	}
}

Is to add a bool type , As long as the head to tail traversal is general , No swap operation , It can be regarded as completely orderly , immediate withdrawal .

Heap sort ：

First figure out what is a big top pile , Small cap pile

Big pile top ： The value of the parent node is greater than that of the child node （ Sort from small to large with big top ）

 

Small cap pile ： The value of the parent node is less than that of the child node （ Sort from large to small with a small top stack ）

 

1. We need to first think of the raw data as a complete binary tree

 2. Adjust from the last non leaf node , Adjust to large top reactor

 

At this point, we will find that the value of the root node is the largest value in the array

 3. Exchange the values of the root node and the last node , Then kick the tail node out of our sorting array

 

 4. repeat 2,3 step

The code is as follows ：

// One time adjustment function   Time complexity O（logn）
void HeapAdjust(int arr[], int start, int end)
{
	//assert
	int tmp = arr[start];    
	for(int i=start*2+1; i<=end; i=start*2+1)//start*2+1  Equivalent to start The left child of this node 
	{                     //i<end   sign out for loop    What triggers is the situation 1
		if(i<end && arr[i+1] > arr[i])//i<end  Represents the existence of right children , And the value of the right child is greater than that of the left child 
		{
			i++;// Now , Give Way i Point to the right child 
		}
		// here i It must have pointed to the older child 

		if(arr[i] > tmp)// The son is greater than the father 
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;// sign out for loop , Trigger condition 2
		}
	}

	arr[start] = tmp;
}

// Heap sort ： Time complexity O（n*logn）   Spatial complexity O（1）   stability ： unstable 
void HeapSort(int *arr, int len)
{
	//1. The whole is adjusted from the last non leaf node from inside to outside 
	// First, you need to know the subscript of the last non leaf node 
	for(int i=(len-1-1)/2; i>=0; i--)// Because the last non leaf node must be   The parent node of the last leaf node 
	{
		HeapAdjust(arr, i, len-1);// Call our adjustment function once   // The third value here is special , There are no rules , Then give the maximum value directly len-1
	}

	// here , It has been adjusted to a large top pile 

	// Next , The value of the root node is exchanged with the value of the current last node , Then remove the tail node 
	for(int i=0; i<len-1; i++)
	{
		int tmp = arr[0];
		arr[0] = arr[len-1-i];//len-1-i  Is our current tail node subscript 
		arr[len-1-i] = tmp;

		HeapAdjust(arr, 0, (len-1-i)-1);//len-1-i  Is our current tail node subscript , Then give it -1 It's equivalent to removing it from our cycle 
	}

}