Déchirure à la main - tri

Insérer un tri

Insérer le tri à condition queLa séquence est ordonnée lorsqu'elle n'est pas insérée.

Si c'est trié de petit à grand,Le nombre d'Inserts estkey,Rechercher de droite à gauche jusqu'àkeyValeur de,Si ce n'est pas le cas, déplacez l'original d'un bit vers l'arrière pour l'écraser,Jusqu'à ce qu'il soit satisfait ou trouvé pour l'insertion.
Répétez l'opération ci - dessus.

void InsertSort(int* a, int n)
{
    
	int i = 0;
	for (i = 0; i < n-1; i++)
	{
    
		int end=i;
		int key = a[end + 1];
		while (end>=0)
		{
    
			if (a[end] <= key)
				break;
			else
				a[end + 1] = a[end];
			end--;
		}
		a[end + 1] = key;
	}
	
}

Complexité temporelleO(n*n)
Cet ordre convient à des situations proches de l'ordre ,Dans ce casComplexité temporelle procheO(n)

Tri Hill

Il y a des séquences d'insertion qui ont évolué
Le tri de Hill comporte deux étapes ：
1.Pré - tri（ Soyez aussi ordonné que possible ）
2.Insérer un tri

Exemple：
Pré - tri： Diviser un groupe de nombres à trier en gapGroupe, Chaque groupe est inséré et trié

Prends ça.10 Le nombre de groupes est divisé en 3Groupe：
No1Groupe：2,5,3,0
No2Groupe：4,1,8
No3Groupe：6,9,7

L'ordre après le préconditionnement

Dernier tri complet des Inserts ,Pour obtenir une séquence ordonnée.
Le Code de l'exemple ci - dessus ：

void ShellSort(int* a, int n)
{
    
	int gap = 3;
	for (int i = 0; i < n-gap; i++)
	{
    
		
		int end=i;
		int key = a[end + gap];
		while (end >= 0)
		{
    
			if (a[end] <= key)
				break;
			else
				a[end + gap] = a[end];
			end -= gap;
		}
		a[end + gap] = key;
	}
	InsertSort(a, n);
}

Diagramme dynamique de l'ordre de Hill

void ShellSort(int* a, int n)
{
    
	int gap = n;
	while (gap>1)
	{
    
		gap = gap / 2;
		for (int i = 0; i < n-gap; i++)
		{
    
			int end = i;
			int key = a[end + gap];
			while (end >= 0)
			{
    
				if (a[end] <= key)
					break;
				else
					a[end + gap] = a[end];
				end -= gap;
			}
			a[end + gap] = key;
		}
	}
	
}

Sélectionner le tri

Choisir le tri est simple, Chaque fois que vous choisissez le plus petit inverse devant , Choisissez le plus grand et mettez - le à l'arrière .

void SelectSort(int* a, int n)
{
    
	int min, max;
	int begin = 0, end = n - 1;	
	while (begin < end)
	{
    
		min = max = begin;
		for (int i = begin; i <= end; i++)
		{
    
			if (a[min] > a[i])
				min = i;
			if (a[max] < a[i])
				max = i;
		}
		swap(&a[min], &a[begin]);
		//Attention!
		if (begin == max)
			max = min;
		swap(&a[max], &a[end]);
		begin++;
		end--;
	}
}

Complexité temporelleO(N)

Tri du tas

void AdjustDwon(int* a, int n, int root)
{
    
	int father = root;
	int child = 2 * father + 1;
	while (child <n)
	{
    
		if (child<n - 1 && a[child]<a[child + 1])
			child++;
		if (a[father] < a[child])
		{
    
			swap(&a[father], &a[child]);
			father = child;
			child = 2 * father + 1;
		}
		else
			return;
	}
}
void HeapSort(int* a, int n)
{
    
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
    
		AdjustDwon(a, n, i);
	}

	for (i = n - 1; i > 0; i--)
	{
    
		swap(&a[0], &a[i]);
		AdjustDwon(a, i-1, 0);
	}
}

Tri des bulles

void BubbleSort(int* a, int n)
{
    
	int begin = 0;
	int end = n - 1;
	for (int i = begin; i < n-1; i++)
	{
    
		for (int j = begin; j < end; j++)
		{
    
			if (a[j+1] < a[j])
				swap(&a[j], &a[j+1]);
		}
		end--;
	}
}

Tri rapide

L'idée de base d'un tri rapide est ： Choisissez une valeur de base , En général, la valeur de base la plus à gauche est sélectionnée , Et puis la traversée commence à droite , Supposons qu'il s'agisse d'un ordre allant du plus petit au plus grand , Alors, cherchez la petite à droite , Après avoir trouvé le petit , Cherchez le plus grand , Après avoir trouvé, les deux ont échangé . Ensuite, répétez le processus ci - dessus , Jusqu'à ce que la gauche soit supérieure ou égale à la droite , Et puis on échange avec la base .
C'est un tour.

int PartSort1(int* a, int left, int right)
{
    
	int keyi = left;
	while (left < right)
	{
    
		while (left < right && a[keyi] <= a[right])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[right]);
	keyi = left;
	return keyi;
}

Méthode de localisation des puits ： Prenez la base comme position de la fosse , Commencez à droite et cherchez la petite （Plus petit que la base）De, Remplir la fosse une fois trouvée , Cette position devient la position de la fosse , Ensuite, commencez à gauche et cherchez le grand , Ensuite, remplissez la fosse , Jusqu'à ce que la recherche soit terminée （Gauche supérieure ou égale à droite）, Remplir la base dans la fosse .

int PartSort2(int* a, int left, int right)
{
    
	int keyi= left;
	int temp = a[left];
	while (left < right)
	{
    
		while (left<right&&a[right] >= temp)
		{
    
			right--;
		}
		a[keyi] = a[right];
		keyi = right;
		while (left < right && a[left] <= temp)
		{
    
			left++;
		}
		a[keyi] = a[left];
		keyi = left;
	}
	a[keyi] = temp;
	return keyi;
}

Méthode du pointeur avant et arrière：
Le pointeur avant commence à la position avant la base , Le pointeur arrière commence à la position de base . Le pointeur avant est plus petit , Quand j'ai trouvé l'enfant , Pointeur arrière plus un , Les valeurs indiquées par les pointeurs avant et arrière sont ensuite échangées , Puis le pointeur avant continue à chercher la petite , Jusqu'à ce que la recherche soit terminée .

int PartSort3(int* a, int left, int right)
{
    
	int keyi = left;
	int front = keyi + 1;
	int back = keyi;
	while (front <= right)
	{
    
		if (a[front] <= a[keyi])
		{
    
			back++;
			swap(&a[front], &a[back]);
		}
		front++;
	}
	swap(&a[back], &a[keyi]);
	keyi = back;
	return keyi;
}

Ce qui précède décrit un cycle de tri , Après chaque tour , Peut déterminer la position de la base après l'ordre , La base gauche est plus petite que ça , À droite, c'est plus grand que ça , Continuez à trier à gauche , La droite continue à trier . Arrête de trier quand il en reste un à trier .

void QuickSort(int* a, int left, int right)
{
    
	if (left >= right)
		return;
	int keyi = left;
	//keyi = PartSort1(a, left, right);
	//keyi = PartSort2(a, left, right);
	keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

Ce genre de tri n'est pas encore possible , Parce que sa pire complexité temporelle est O(N*N), La base que nous prenons est de préférence la valeur médiane du Groupe avec des nombres ordinaux , Mais cette valeur n'est pas facile à trouver dans le désordre ,À ce stade, nous utilisons3 Méthode de centrage des nombres , Mettez la valeur la plus latérale , La valeur la plus à droite , Et une valeur intermédiaire ,3 Pour comparer , Le plus grand est la base . Pour être sûr que c'est toujours la méthode ci - dessus , Nous échangeons la base contre le nombre le plus à gauche .

int ThreeIn(int* a, int left, int right)
{
    
	int middle = left + (right - left) / 2;
	if (a[middle] < a[left])
	{
    
		if (a[left] < a[right])
			return left;
		else if (a[middle] < a[right])
			return right;
		else
			return middle;
	}
	else
	{
    
		if (a[middle] < a[right])
			return middle;
		else if (a[left] < a[right])
			return right;
		else
			return left;
	}
}
void QuickSort(int* a, int left, int right)
{
    
	if (left >= right)
		return;
	int keyi = left;
	int x = ThreeIn(a, left, right);
	swap(&a[keyi], &a[x]);
	//keyi = PartSort1(a, left, right);
	//keyi = PartSort2(a, left, right);
	keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

Complexité temporelleO(N*logN)

Sur la base de l'extrême gauche , Pourquoi commencer à droite en premier ？

InLAvecR Il n'y a rien à discuter pendant l'échange , Le plus important, c'est quand on se rencontre et qu'on échange la base ：
1.RRencontreL,En ce momentL Pour le plus petit ou la base ,Après l'échange,Gauche petite droite grande.
2.LRencontreR:
(1)LAvecRPas d'échange.
R La position est petite ,R Il y a de grandes , Il y a de petits , Peut être échangé avec la valeur de base .
(2)LAvecREchange
Après l'échangeR Ou continuer à se déplacer dans de petits endroits ,Et puis(1)C'est pareil.

Nous discuterons de choisir la gauche comme valeur de base , Ou discuter de la rencontre
1.LRencontreR
(1) Je me suis rencontré sans échange , Impossible de déterminer la taille de la valeur de base lors de la rencontre .
(2)LAvecR On se retrouve après l'échange , La rencontre est grande , Impossible d'échanger avec la valeur de base .
2.RRencontreL
RRencontreLDescriptionRAvecLJ'ai échangé., La valeur de base est petite ,Peut être échangé.
En résumé: Le fait de commencer à gauche ne garantit pas entièrement que l'endroit où vous vous rencontrerez sera petit .
Tri rapide sous forme non récursive
1. Mise en œuvre avec pile
Stocke les limites supérieure et inférieure d'un ensemble de nombres avec une pile , Si vous choisissez la base à partir de la gauche , Selon les caractéristiques de la pile , Nous stockons d'abord la limite gauche , Et la limite droite . Chaque tri sort de la pile 2Données. Lorsque vous stockez une limite dans la pile, voulez - vous que la limite principale ait des éléments directement .

void QuickSortNonR1(int* a, int left, int right)
{
    

	Stack p;
	InitStack(&p);
	StackPush(&p, left);
	StackPush(&p, right);
	while (!StackEmpty(&p))
	{
    
		right = StackTop(&p);
		StackPop(&p);
		left = StackTop(&p);
		StackPop(&p);
		int keyi = PartSort3(a, left, right);
		if (keyi + 1 < right)
		{
    
			StackPush(&p, keyi+1);
			StackPush(&p, right);
		}
		if (keyi - 1 > left)
		{
    
			StackPush(&p, left);
			StackPush(&p, keyi-1);
		}
	}
	StackDestroy(&p);
}

2.Mise en œuvre en file d'attente
Selon la nature de la file d'attente , Stockez d'abord la limite droite , Et la limite gauche . Le processus suivant est similaire à la pile

void QuickSortNonR2(int* a, int left, int right)
{
    
	Queue p;
	QueueInit(&p);
	QueuePush(&p, right);
	QueuePush(&p, left);
	while (!QueueEmpty(&p))
	{
    
		right = QueueFront(&p);
		QueuePop(&p);
		left= QueueFront(&p);
		QueuePop(&p);
		int keyi = PartSort3(a, left, right);
		
		if (keyi - 1 > left)
		{
    
			
			QueuePush(&p, keyi - 1);
			QueuePush(&p, left);
		}
		if (keyi + 1 < right)
		{
    
			
			QueuePush(&p, right);
			QueuePush(&p, keyi + 1);
		}
	}
	QueueDestroy(&p);

}

Ordre de fusion