Gnawing down the big bone - sorting (I)

1. The concept of sorting and its application

1.1 The concept of sequencing

The essence of sorting is to filter , Life is inseparable from sequencing

Sort ： So called sorting , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order .

stability ： Assume in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , The relative order of these records remains the same , In the original sequence ,r[i]=r[j], And r[i] stay r[j] Before , In the sorted sequence ,r[i] Still in r[j] Before , We call this sort algorithm stable ; Otherwise it is called unstable .

Internal sorting ： Sorting in which all data elements are placed in memory .

External sorting ： Too many data elements to be in memory at the same time , According to the requirements of the sorting process, data sorting cannot be moved between internal and external storage .
 

1.2 Sorting application

When buying things, the sales volume is sorted , Comprehensive ranking , Good reviews, etc
University ranking, etc
Video recommendation stream , Recommendation algorithm Leaderboard with goods

 

1.3 Common sorting algorithms

---

 

2. Implementation of common sorting algorithms

2.1 Insertion sort

2.1.1 The basic idea ：

Direct insertion sort is a simple insertion sort method , Its The basic idea yes ：
Insert the records to be sorted into an ordered sequence one by one according to their key values , Until all the records are inserted , We get a new ordered sequence .

In practice, we play poker （ Fight the landlord and manage the cards ） when , We use the idea of insertion sort

Look at... In ascending order , The descending order is the reverse
Orderly ：
2 6 7 9

Number to be inserted ： 10 5 0
A single trip is orderly ： Ordered interval , Inserting a number is still in order
 

2.1.2 Direct insert sort ：

When inserting the i(i>=1) Element time , Ahead array[0],array[1],…,array[i-1] It's in order , Use at this time array[i] The sort code of and array[i-1],array[i-2],… Compare the sort code order of , Find the insertion position array[i] Insert , The elements in the original position move backward in order

Summary of the features of direct insertion sort ：

1. The closer the set of elements is to order , The more time efficient the direct insertion sort algorithm is
2. Time complexity ：O(N^2)
   The optimal ： Orderly or near orderly O(N)
   The worst ： The reverse
3. Spatial complexity ：O(1), It's a stable sort algorithm
4. stability ： Stable

// Direct insert sort 
void InsertSort(int* a, int n)
{
    
	// A loop is a whole sequence 
	//n-2 It's the penultimate position , Because it is the end+1 Insert in front , therefore end It's not worth it for The cycle stops 
	// Array subscript is from 0 At the beginning 
	for (int i = 0; i < n - 1; ++i)
	{
    
		// Ideas ：[0,end] Orderly , hold end+1 The value of the position is inserted , Still in order 
		int end = i;
		// Define a tmp Variable , Store the value you are about to insert 
		int tmp = a[end + 1];// hold end The latter one is inserted into the front 

		// Single pass sorting 
		while (end >= 0)
		{
    
			if (tmp < a[end])
			{
    
				a[end + 1] = a[end];
				--end;
			}
			else
			{
    
				// If the inserted value is 0,-- To -1 First jump out and then assign value , Otherwise 0 Will fail to insert 
				break;
			}
		}
		a[end + 1] = tmp;
	}
	
}

Be careful ： Its sort is not directly exchangeable , It's a end+1 Insert into the previous ordered sequence

 

2.1.3 Shell Sort ( Reduced delta sort )

Hill ranking is also known as Reduction increment method .

Hill's ranking method The basic idea yes ：

1. Choose an integer first , Divide all the records in the file to be sorted into groups , All records at a distance of are in the same group , And sort the records in each group .
2. then , take , Repeat the above work of grouping and sorting . When they arrive in =1 when , All records are arranged in a unified group .

Ideas ： Pre sort （ Close to order ） Group insertion prearrangement , Divide into gap Group （ Spacing is gap Is a set of data ）, For these gap Insert and sort the group data separately Direct insert sort （ Orderly ）

Hill sorted Feature summary ：

1. Hill sort is an optimization of direct insert sort .

2. When gap > 1 It's all pre sorted , The goal is to make arrays more ordered .
   When gap == 1 when , The array is nearly ordered , This will soon .
   So on the whole , Can achieve the effect of optimization . We can compare the performance test after implementation .

3. The time complexity of Hill sort is not easy to calculate , because gap There are many ways to get the value of , Makes it difficult to calculate , Therefore, the time complexity of hill sorting given in many trees is not fixed ：

// Shell Sort 
void ShellSort(int* a, int n)
{
    
	// When one group is finished, the next group 
// // Control multiple groups 
// int gap = 3;
// //gap There are several groups of data 
// for (int j = 0; j < gap; ++j)
// {
    
// for (int i = j; i < n - gap; i += gap)
// {
    
// // Single trip , The same idea as direct insertion sorting 
// int end = i;
// int tmp = a[end + gap];
//
// while (end >= 0)
// {
    
// if (tmp < a[end])
// {
    
// a[end + gap] = a[end];
// end -= gap;
// }
// else
// {
    
// break;
// }
// }
// a[end + gap] = tmp;
// }
// }
// 


	// simplify 
	// One after another , Groups walk alternately 
	int gap = n;
	//gap>1 It is pre sort 
	//gap The last time is equal to 1, Is to insert sort directly （ Keep order ）
	while (gap > 1)
	{
    
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
    
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
    
				if (tmp < a[end])
				{
    
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

Be careful ：
gap The bigger it is , Big numbers get to the back faster , Small numbers go faster to the front , But the less close to order
gap The smaller it is , The closer to order
When gap be equal to 1 when , Direct sorting

 

2.2 Selection sort

2.2.1 The basic idea ：

Each time, select the smallest from the data elements to be sorted （ Or maximum ） An element of , Store at the beginning of the sequence , Until all the data elements to be sorted are finished .

2.2.2 Direct selection sorting :

Ideas ：
Select the first number , Then use traversal to compare the following numbers in turn , If there is something smaller than the first number, exchange it , If there is nothing smaller than the number to be compared, traverse the smallest of the remaining numbers and put them in front

Go through it and choose
Go through it and choose the smallest one first , Go through it again and choose the smaller one , In turn

In the element set array[i]–array[n-1] Select the largest key in ( Small ) Data elements
If it's not last of the these elements ( first ) Elements , Then it is combined with the last element in the group （ first ） Element exchange
In the remaining array[i]–array[n-2]（array[i+1]–array[n-1]） Collection , Repeat the above steps , Until the set remains 1 Elements

Be careful ： Looking for subscript , swapping

Select the sorted directly Feature summary ：

1. It's very easy to understand how to think directly , But the efficiency is not very good . It is seldom used in practice
2. Time complexity ：O(N^2)
3. Spatial complexity ：O(1)
4. stability ： unstable

void Swap(int* p1, int* p2)
{
    
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// Direct selection sorting 
void SelectSort(int* a, int n)
{
    
	assert(a);

	//begin,end It's an array subscript [] Number in Li , Subscript from 0 Start , So the last one is n-1
	int begin = 0, end = n - 1;
	
	// When will it come to an end? ： An odd number of encounters , Even missed 
	while (begin < end)
	{
    
		// The starting position is given to the first number , Then start with the second number 
		int mini = begin, maxi = begin;

		for (int i = begin + 1; i <= end; ++i)
		{
    
			// Traverse , contrast ,
			if (a[i] < a[mini])
				// to update 
				mini = i;

			if (a[i]>a[maxi])
				maxi = i;
		}// At this point, the maximum and minimum values have been found , Store separately maxi And mini in 

		// In exchange for 
		Swap(&a[begin], &a[mini]);
  	// If begin and maxi overlap , Need to fix 
		if (begin == maxi)
		{
    
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		// At this time, it only traverses once , It needs to be traversed again 
		++begin;
		--end;
	  }
	}

And Heap sort contrast ： O(N^2) The advantages are simple , But it's slow

And Direct insert sort contrast ： It's better to insert ( It's just that the ranking advantage with hill is weak ）
Selection sorting is almost the slowest It is best to N^2,
The slowest N^2

 

2.2.3 Heap sort

Heap sort (Heapsort) It's the use of stacked trees （ Pile up ） A sort algorithm designed by this data structure , It's a sort of selective sort .
It selects data through the heap . It's important to note that in ascending order you have to build lots of , Build small piles in descending order .

Select the sorted directly Feature summary ：

1. Heap sort uses heap to select numbers , It's a lot more efficient .
2. Time complexity ：O(N*logN)
3. Spatial complexity ：O(1)
4. stability ： unstable

void AdjustDwon(int* a, int size, int parent)
{
    
	int child = parent * 2 + 1;
	while (child < size)
	{
    

		if (child + 1 < size && a[child + 1] > a[child])
		{
    
			++child;
		}

		if (a[child] > a[parent])
		{
    
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
    
			break;
		}
	}
}

//  Descending  --  Build a small pile 
//  Ascending  --  Build a pile 

void HeapSort(int* a, int n)

{
    

	for (int i = (n-1-1)/2; i >= 0; --i)

	{
    

		AdjustDwon(a, n, i);

	}



	// O(N*logN)

	int end = n - 1;

	while (end > 0)

	{
    

		Swap(&a[0], &a[end]);

		AdjustDwon(a, end, 0);

		--end;

	}

}