c Diseño del curso de estructura de datos

1. Clasificación de burbujas

Algoritmo: la idea central es escanear la lista de datos y buscar dos elementos adyacentes que estén desordenados. Cuando encuentre ambos elementos, intercambie las posiciones de los elementos y continúe escaneando. Repita la operación anterior hasta que todos los elementos estén ordenados

bubblesort(struct rec r[], int n)

{

int i, j ;

struct rec w;

unsigned long int compare=0, move=0;

for(i=1;ilt;=n-1; i )

for(j=n;jgt;=i 1;j--)

{

if(r[j].keylt;r [j -1].key)

{

w=r[j];

r[j]=r[j-1];

r[j-1]=w;

movimiento=movimiento 3;

}

comparar;

}

printf("

BubbleSort comparar= ld, mover= ld

", comparar, mover);

}

2. Ordenación por inserción directa

Algoritmo: después del procesamiento i-1, se ha ordenado L[1..i-1]. El i-ésimo paso solo inserta L[i] en la posición apropiada de L[1..i-1], haciendo de L[1..i] una secuencia ordenada nuevamente. Para lograr este objetivo, podemos utilizar la comparación secuencial. Primero compare L[i] y L[i-1]. Si L[i-1]≤ L[i], entonces L[1..i] ha sido ordenado y, de lo contrario, el i-ésimo paso de procesamiento ha finalizado; intercambio Para las posiciones de L [i] y L [i-1], continúe comparando L [i-1] y L [i-2] hasta encontrar una determinada posición j (1≤j≤i-1), tal que L[j ] ≤L[j 1]

insertsort(struct rec r[], int n)

{

int i, j;

unsigned long int compare=0, move=0;

for(i=2;ilt;=n;i)

{compare;

r[0]=r[i];

mover;

j=i-1;

mientras(r[0] .key { r[j 1]=r[j];

j--;

mover;

comparar;}

r[ j 1]=r[0];

mover;

}

printf("

InsertSort comparar= ld , move= ld

", comparar, mover);

}

3. Ordenación por selección simple

Algoritmo: primero encuentre el Encuentre los datos más pequeños y luego intercambie estos datos con los primeros datos, luego encuentre los segundos datos más pequeños y luego intercámbielos con los segundos datos, y así sucesivamente;

selectsort(struct rec r[], int n)

{

unsigned long int compare=0, move=0;

int i, j, k;

struct rec w;

for(i=1; ilt; =n-1; i )

{ k =i;

for(j=i 1;jlt;=n;j)

{ si(r[j].keygt;r[k].key) {k =j; comparar; }

w=r[i];

r[i]=r[k];

r[k]=w ;

mover=mover 3;

}

}

printf("

SeleccionarOrdenar comparar= ld , move= ld

", comparar, mover);

}

4. Algoritmo de clasificación rápida: primero verifique la lista de datos si el número de datos en es menor que dos, el programa saldrá directamente. Si hay más de dos datos, elija un punto de división para dividir los datos en dos partes. Los datos más pequeños que el punto de división se colocan en un grupo, el resto se coloca en otro grupo y luego los dos conjuntos de. Los datos se ordenan respectivamente.

Por lo general, los datos en los puntos de división se seleccionan al azar. De esta forma, independientemente de si tus datos han sido ordenados o no, los tamaños de las dos listas de palabras en las que dividas serán similares. Siempre que los tamaños de las dos sublistas sean similares

q(struct rec r[], int s, int t)

{

int i= s, j =t;

if(slt;t)

{

r[0]=r[s]; p>

hacer{

mientras(jgt;iamp;amp;r[j].keygt;=r[0].key)

{j--;

a; }

if(ilt; j)

{ r[i]=r[j];

i;

c; }

mientras(ilt;jamp;amp;r[i].keylt;=r[0].key)

{i;

a; }

if(ilt; j)

{ r[j]=r[i];

j-- ;

c; }

} mientras(ilt;j);

r[i]=r[0]; p>c;

q(r, s, j-1);

q(r, j 1, t

}

}

5. Clasificación en montón

(1) Idea básica:

La clasificación en montón es una clasificación por selección de árbol. Durante el proceso de clasificación, R. [1. .N] se considera una estructura de almacenamiento secuencial de un árbol binario completo, y la relación intrínseca entre el nodo padre y el nodo hijo en el árbol binario completo se utiliza para seleccionar el elemento más pequeño.

(2). Definición de montón: La secuencia de N elementos K1, K2, K3,...,Kn se llama montón si y sólo si la secuencia satisface las características:

Ki≤K2i Ki ≤K2i 1(1≤ I≤ [N/2])

sift(struct rec r[], int l, int m)

{

int i,j;

struct rec w;

i=l; j=2*i;

w=r [ i];

mientras(jlt;=m)

{

if(jlt;mamp;amp;r[j].keylt;r[ j 1].key) { j ;

}

if(w.keylt; r[j].key)

{

r[i]=r[j];

i=j;

j=2*i;

}

else j=m 1;

}

r[i]=w;

}

heapsort(struct rec r[ ] , int n)

{

unsigned long int compare=-1, move=-1;

struct rec w;

int i;

int a;

for(i=n/2;igt;=1;i--) a=sift(r,i,n);

comparar;

mover;

for(i=n;igt;=2;i--)

{

w=r[i];

r[i]=r[1];

r[1]=w;

a= tamizar(r, 1, i-1);

comparar =a;

mover =a; >}