Se sabe que hay 10 constantes 32, 56, 78, 9, 21, 70, 26, 90, 66, 88. Se utilizan dos métodos de clasificación para la programación.

La llamada clasificación consiste en organizar los registros del archivo de modo que estén ordenados en orden creciente (o decreciente) de palabras clave. Su definición exacta es la siguiente:

Entrada: n registros R1, R2,..., Rn, y sus correspondientes palabras clave son K1, K2,..., Kn.

Salida: Ril, Ri2,…,Rin, tal que Ki1≤Ki2≤…≤Kin. (o Ki1≥Ki2≥…≥Kin).

Aquí presentamos brevemente varios métodos de clasificación: clasificación por inserción directa, clasificación por buscador, clasificación por burbuja, clasificación rápida y clasificación por selección directa. El código mencionado en el artículo se ha probado en IE6.

Idea básica de ordenación por inserción directa

Supongamos que los registros a ordenar se almacenan en la matriz R[1..n]. Inicialmente, R[1] forma un área ordenada y el área desordenada es R[2..n]. Desde i = 2 hasta i = n, ​​R [i] se inserta secuencialmente en el área ordenada actual R [1..i-1] para generar un área ordenada que contiene n registros.

Descripción del algoritmo

función InsertSort(arr) { //Inserción sort-gt; clasificación por inserción directa

var st = new Date(); >

p>

var temp, j;

for(var i=1; ilt; arr.length; i) {

if((arr[i) ]) lt; (arr[i-1])) {

temp = arr[i];

j = i-1;

arr[j 1] = arr[j];

j--;

}

mientras (jgt;-1 amplificador; }

status = (new Date() - st) ' ms';

return arr;

}

Idea básica de ​​Clasificación Hill

Primero tome un número entero d1 menor que n como primer incremento y divida todos los registros del archivo en grupos d1. Todos los registros cuya distancia sea múltiplo de dl se colocan en el mismo grupo. Primero realice la clasificación por inserción directa dentro de cada grupo; luego, tome el segundo incremento d2lt; d1 y repita la agrupación y clasificación anteriores hasta el incremento tomado dt=1(dtlt; dt-llt;...lt; d2lt; d1), eso es decir, hasta que todos los registros se coloquen en el mismo grupo para la ordenación por inserción directa.

Este método es esencialmente un método de inserción agrupada.

Descripción del algoritmo

función ShellSort(arr) { //Inserción sort-gt; Clasificación Hill

var st = new Date()

var incremento = arr.length;

hacer {

incremento = (incremento/3|0)

arr = ShellPass(arr, incremento);

}

mientras (incremento gt; 1)

estado = (nueva fecha() - st) 'ms';

return arr;

}

function ShellPass(arr, d) { //Función de ejecución segmentada de clasificación pura

var temp, j

for(var i=d; ilt; arr.length; i ) {

if((arr[i]) lt; (arr[i-d])) {

temp = arr[i]; j = i-d;

hacer {

arr[j d] = arr[j]; ;

}

mientras (jgt;-1 amp; amp; (temp) lt; (arr[j]));

arr [j d] = temp;

}//endif

}

return arr;

}

La idea básica de clasificación de burbujas

Organiza la matriz de registros ordenados R[1..n] verticalmente, y cada registro R[i] se considera una burbuja con un peso de R[i].key. Según el principio de que las burbujas ligeras no pueden estar debajo de las pesadas, la matriz R se escanea de abajo hacia arriba: cualquier burbuja ligera que viole este principio "flotará" hacia arriba. Esto se repite hasta que las dos últimas burbujas sean la más ligera en la parte superior y la más pesada en la parte inferior.

Descripción del algoritmo

función BubbleSort(arr) { //Exchange sort-gt; bubble sort

var st = new Date()

var temp;

var intercambio

for(var i=0; ilt; arr.length; i) {

intercambio = false ;

for(var j=arr.length-2; jgt;=i; j--) {

if((arr[j 1]) lt; (arr[ j ])) {

temp = arr[j 1];

arr[j 1] = arr[j];

intercambio = verdadero

}

}

if(!intercambio)

}

status = (new Date() - st) ' ms';

return arr;

}

Idea básica sobre clasificación rápida

Descomponer el problema original en varios subproblemas de menor tamaño pero similares en estructura al problema original. Resuelva estos subproblemas de forma recursiva y luego combine las soluciones de estos subproblemas en una solución al problema original.

Seleccione cualquier registro en R[bajo..alto] como punto de referencia (Pivote) y utilice este punto de referencia para dividir el área desordenada actual en dos subintervalos más pequeños, izquierdo y derecho, R[bajo. .pivotpos-1) y R[pivotpos 1..high], y haga que las claves de todos los registros en el subintervalo izquierdo sean menores o iguales a la clave pivot.key del registro de referencia (que puede registrarse como pivote) y todas las claves en el subintervalo derecho Las palabras clave registradas son todas mayores o iguales que pivot.key, y el pivote del registro de referencia está ubicado en la posición correcta (pivotpos). No es necesario participar en la clasificación posterior.

Descripción del algoritmo

función QuickSort(arr) { //Exchange sort-gt; quick sort

if (arguments.lengthgt; 1) {

var bajo = argumentos[1];

var alto = argumentos[2];

} else {

var bajo = 0; /p>

var alto = arr.length-1

}

if(low lt; alto){

// función Partición

var i = bajo;

var j = alto;

var pivot = arr[i]; ) {

mientras(ilt;j amp;amp; arr[j]gt;=pivote)

j--; )

arr[i ] = arr[j];

mientras(ilt;j amp;amp; arr[i]lt;=pivote)

i;

if(ilt;j)

arr[j--] = arr[i]

}//finalizar

arr[i] = pivot;

// función final

var pivotpos = i; //Partición(arr, baja, alta

); QuickSort(arr, bajo, pivotpos-1);

QuickSort(arr, pivotpos 1, alto

} else

return;

return arr;

}

Idea básica de clasificación por selección directa

La clasificación por selección directa de archivos con n registros puede pasar por n-1 selecciones directas Ordenar los resultados en orden:

①Estado inicial: el área desordenada es R [1..n] y el área ordenada está vacía.

②La primera clasificación

Seleccione el registro R[k] con la palabra clave más pequeña en el área desordenada R[1..n] y combínelo con el área desordenada El primer registro R[1] se intercambia, de modo que R[1..1] y R[2..n] se convierten en una nueva área ordenada con el número de registros aumentado en 1 y una nueva área desordenada con el número de registros reducido en 1 respectivamente.

……

③La clasificación i-ésima

Cuando comienza la clasificación i-ésima, el área ordenada actual y el área desordenada son R[1.. i -1] y R[i..n] (1≤i≤n-1). Esta operación de clasificación selecciona el registro R[k] con la clave más pequeña del área desordenada actual y lo intercambia con el primer registro R[i] en el área desordenada, de modo que R[1..i] y R[i 1 ..n] se convierten respectivamente en una nueva área ordenada con el número de registros aumentado en 1 y en una nueva área desordenada con el número de registros reducido en 1.

De esta manera, la clasificación por selección directa de archivos con n registros puede obtener resultados ordenados mediante la clasificación por selección directa n-1.

Descripción del algoritmo

función SelectSort(arr) { //Seleccione sort-gt; clasificación de selección directa

var st = new Date(); >

var temp;

for(var i=0; ilt; arr.length; i ) {

var k = i; (var j=i 1; jlt; arr.length; j ) {

if((arr[j]) lt; (arr[k]))

k = j

}

if (k != i){

temp = arr[i]

arr[i] = arr[k];

arr[k] = temp;

}

}

estado = (nueva fecha() - st) 'ms';

return arr;

}

En términos de velocidad de carrera, la clasificación rápida es la más rápida.