Lenguaje C de estructura de datos: más de tres algoritmos de clasificación
Clasificación rápida:
void QSort(int a[], int l, int r) //Método de intercambio de palabras clave única clasificación rápida
{
int i = l, j = r, mid = (i + j) / 2; //Intervalo de bisección [i,j]
while (i <= j) //Dejemos que El lado izquierdo de a[mid] es más pequeño que a[mid] y el lado derecho es más grande que a[mid]
{
mientras que (a[i] < a[ mid]) // Encuentra un elemento a[i] más pequeño que a[mid]
i++;
while (a[j] > a[mid]) //Encuentra un elemento a[j] Mayor que a[mid]
j--;
if (i <= j) //Intercambia a[i] y a[j], y acerca el puntero al centro
Swap(a[i++], a[j--]);
}
if (i < r)
QSort(a, i, r); // Ordena recursivamente el intervalo correcto [i, r]
if (l < j)
QSort( a, l, j); // Ordena recursivamente el intervalo izquierdo [l,j]
}
Merge sort:
void Merge(int a[ ], int l, int m , int r) //Combina los intervalos [l, r] en a en orden
{
int x[101], y[101] ; //Variable de bucle
int i, j, k;
int l1 = m - l + 1, l2 = r - m; [l, m], l2 representa La longitud del intervalo [m + 1, r]
para (i = 1; i <= l1; i++) // Copia el intervalo [l, m] en a a x
{
x[i] = a[l + i - 1];
}
para ( i = 1; i <= l2; i++) //Copia el intervalo [m + 1, r] en a a y
{
y[i] = a[m + i];
}
x[l1 + 1] = MaxInt; //Establece un número grande como marca final
y[l2 + 1 ] = MaxInt;
i = 1;
j =
1;
for (k = l; k <= r; k++) //Fusiona los dos intervalos en un intervalo ordenado
{
if (x [i] <= y[j])
{
a[k] = x[i++];
}
else
{
a[k] = y[j++];
}
}
}
void MergeSort(int a[], int l, int r) //Ordena el intervalo [l, r] de una matriz
{
int m;
if (l < r)
{
m = (l + r) / 2; //Intervalo binario [l, r ]
MergeSort(a, l, m); //Intervalo binario recursivo [l, m]
MergeSort(a, m + 1, r); + 1, r]
Merge(a, l, m, r); //Fusiona los intervalos [l, m] y [m + 1, r]
}
}
Clasificación del árbol de clasificación binaria:
struct BinaryTree //Estructura del árbol binario
{
int data , p, l, r; //campo numérico de datos, p número de nodo padre, l número de hijo izquierdo, r número de hijo derecho
};
int root = 0;< / p>
void Init(BinaryTree a[], int &n) //Lee el campo de datos e inicializa el árbol
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].data;
a [i].p = a[i].l = a[i].r = -1;
}
}
insertar vacío( BinaryTree a[], int i) //Inserte el número de nodo i en el árbol de búsqueda binario
{
int parent = -1, x = a[1]. parent siempre apunta al número de nodo principal de x
while (x != -1) //Busca hacia abajo hasta encontrar el nivel inferior
{
padre = x;
if (a[i].datos &l
t; a[x].data)
x = a[x].l;
else
x = a[x].r;
}
a[i].p = parent; //Apunta el padre del nodo i al padre
if (parent != -1) // Determinar si el árbol está vacío
{
if (a[i].data < a[parent].data) //Insertar un hijo en el nodo padre
a[padre].l = i;
else
a[padre].r = i;
}
else //Si está vacío, use el nodo i como nodo raíz
a[root].p = i;
}
void BuildTree (BinaryTree a[], int n) //Crea un árbol de búsqueda binario
{
root = 1;
for (int i = 1; i <= n; i++) //Inserta n nodos en el árbol de búsqueda binario en secuencia
{
Insert(a, i);
}
a [root].p = -1;
}
void Sort(BinaryTree a[], int i) //Salida transversal en orden
{
if (a[i].l > -1) //Atraviesa recursivamente el hijo izquierdo
Sort(a, a[i].l) ;
cout << a[i].data << " "; //Nodo de salida
if (a[i].r > -1) //Atraviesa recursivamente el hijo correcto
Sort(a, a[i].r);
}
Clasificación del montón:
void Heap(int a[], int n, int p ) //Mantener el montón máximo (mínimo), mantener el montón con P como raíz
{
int l = p * 2, r = l + 1, t = p; / /El hijo izquierdo se numera 2P, el hijo derecho es 2P+1 y el nodo raíz P se inicializa para que sea el más grande
si ((l < = n) && (a[l] > a[p])) // Encuentra el número más grande y mantiene el montón máximo (cambia a < para mantener el montón mínimo)
t = l;
if ((r <= n) && (a[r] > a[t])) //Encontrar el número más grande y mantener el montón máximo (cambiar a t = r; si (p != t) // Si el nodo raíz no es el más grande, intercambie con el más grande y luego mantenga el montón de forma recursiva { Swap(a[p], a[t]) ; Heap(a, n, t); } } void HeapSort(int a[], int n ) { int i; for (i = n / 2; i >= 1; i--) //n / 2 debe ser el nodo raíz a partir de, llámelo en secuencia Heap, cree un montón máximo Heap(a, n, i); for (i = n; i >= 2; i--) // Cada vez que el montón Intercambia la parte superior con el último nodo (i) del montón actual y luego vuelve a acumular [1, i - 1] { Intercambio(a[i], a[1] ); Montón(a, i - 1, 1); } } Clasificación por inserción: void InsertionSort(int a[], int l, int r) //Realiza clasificación por inserción en el intervalo [l, r] { int i, j, t ; for (i = l + 1; i <= r; i++) { j = i - 1; t = a[i]; while ((j >= l) && (a[j] > t)) //Mover retroceda y encuentre la posición correcta { a[j + 1] = a[j]; j--; } a[j + 1] = t; } } Todas las funciones de intercambio anteriores significan intercambiar dos variables.