Complejidad del algoritmo de clasificación
Dado que el programa es relativamente sencillo, no se añaden comentarios. Todos los programas proporcionan códigos de ejecución completos y se ejecutan correctamente en mi entorno VC
. Debido a que no hay contenido relacionado con MFC y WINDOWS, no debería haber problemas en la plataforma BORLAND C.
Al final del código se proporciona un diagrama del proceso en ejecución, que espero sea útil para la comprensión. Este es el algoritmo más primitivo y conocido por ser el más lento. El origen de su nombre es que funciona como burbujeante: =Count-1;jgt;i;j--){if(pData[j]lt;pData[j-1]){iTemp=pData[j-1] ;pData[j-1]=pData[j] ;pData[j]=iTemp;}}}}voidmain(){intdata[7]={10,9,8,7,6,5,4};BubbleSort (data,7);for(inti=0; ilt;7;i){coutlt;lt;data[i]lt;lt;;}coutlt;lt;endl;system(PAUSE);}Orden inverso (peor caso escenario)
Primera ronda: 10, 9, 8, 7-gt; 10, 9, 7, 8-gt; intercambiar 3 veces)
No. Segunda ronda: 7, 10, 9, 8-gt; 7, 10, 8, 9-gt; p>
Primera ronda: 7, 8, 10, 9-gt; 7, 8, 9, 10 (1 intercambio)
Número de ciclos: 6 veces
Número de intercambios: 6 veces
Otros:
Primera ronda: 8, 10, 7, 9-gt; 9-gt; 7, 8, 10, 9 (Intercambio 2 veces)
Segunda ronda: 7, 8, 10, 9-gt; 10, 9 (intercambio 1 vez)
(Este es el escritor original - 7, 8, 10, 9-gt; 7, 8, 10, 9-gt; 7, 8, 10, 9 ( intercambiado 0 veces), la segunda ronda debería ser así)
Tercera ronda: 7, 8, 9, 10-gt; 7, 8, 9, 10 (intercambio 1 vez)
Número de ciclos: 6 veces
Número de intercambios: 3 veces
Hemos dado el segmento del programa anterior, y ahora lo analizamos: Aquí, las partes principales que afectan el El rendimiento de nuestro algoritmo son bucles e intercambios.
Obviamente, cuantas más veces, peor será el rendimiento. En el programa anterior, podemos ver que el número de bucles es fijo, 1 2... n-1.
La fórmula escrita es 1/2*(n-1)*n.
Ahora tenga en cuenta que damos la definición del método O:
Si hay una constante K y un punto de partida n0, de modo que cuando ngt;=n0, hay f( n)lt;= K*g(n), entonces f(n) = O(g(n)). (Jaja, no digas que no has aprendido bien las matemáticas, ¡las matemáticas son muy importantes para la programación!)
Ahora veamos 1/2*(n-1)*n, cuando K =1/2 , n0=1, g(n)=n*n, 1/2*(n-1)*nlt;=1/2*n*n=K*g(n). Entonces f(n)
=O(g(n))=O(n*n). Entonces la complejidad del bucle de nuestro programa es O (n*n).
Mira el intercambio nuevamente.
Como se puede observar en la tabla que sigue al programa, los bucles en los dos casos son los mismos pero los intercambios son diferentes. De hecho, el intercambio en sí tiene una gran relación con el grado de ordenación de la fuente de datos. Cuando los datos están en orden inverso, el número de intercambios es el mismo que el del ciclo (se intercambiarán cada juicio de ciclo). p>
La complejidad es O(n*n). Cuando los datos estén en secuencia positiva, no habrá intercambio. La complejidad es O (0). Está en un estado intermedio cuando está fuera de servicio. Es por esta razón que normalmente comparamos algoritmos por el número de ciclos. El procedimiento del método de intercambio es el más claro y sencillo. Cada vez, el elemento actual se compara con los elementos posteriores uno por uno y se intercambia. #includelt;iostream.hgt;voidExchangeSort(int*pData,intCount){intiTemp;for(inti=0;ilt;Count-1;i){//***(count-1) rondas, cada ronda obtiene un mínimo Valor for(intj=i 1;jlt;Count;j){// Encuentre el valor mínimo de los números restantes cada vez, compárelo con el valor mínimo actual, si es pequeño, intercambie if(pData[j]lt;pData [ i]){iTemp=pData[i]; pData[i]=pData[j]; pData[j]=iTemp;}}}}voidmain(){intdata[]={10, 9, 8, 7, 6,5,4};ExchangeSort(datos,tamañode(datos)/tamañode(int));for(inti=0;ilt;tamañode(datos)/tamañode(int);i){coutlt;lt;datos[i ] lt;lt;;}coutlt;lt;endl;system(PAUSE);}Primera ronda: 9, 10, 8, 7-gt; 8, 10, 9, 7-gt; Intercambiar 3 veces)
Segunda ronda: 7, 10, 9, 8-gt; 7, 9, 10, 8-gt;
Primera ronda: 7, 8, 10, 9-gt; 7, 8, 9, 10 (1 intercambio)
Número de ciclos: 6 veces
Tiempos de intercambio: 6 veces
Otros:
Primera ronda: 8, 10, 7, 9-gt; ; 7, 10, 8, 9 (1 intercambio)
Segunda ronda: 7, 10, 8, 9-gt; intercambiar una vez)
Primera ronda: 7, 8, 10, 9-gt; 7, 8, 9, 10 (intercambiar una vez)
Número de bucles: 6 veces
Número de intercambios: 3 veces
Desde la tabla en ejecución, el intercambio es casi tan malo como el burbujeo. Y efectivamente lo es. El número de bucles es el mismo que el del burbujeo.
También es 1/2*(n-1)*n, por lo que la complejidad del algoritmo sigue siendo O(n*n). Como no podemos darle todos los escenarios,
sólo podemos decirle que son igualmente malos en el intercambio (en algunos casos un poco mejores, en otros casos un poco peores). Ahora finalmente podemos ver una pequeña esperanza: el método de selección, que mejora un poco el rendimiento (en algunos casos)
Este método es similar a nuestros hábitos de clasificación artificial: selecciona el orden homogéneo más pequeño de los datos Un valor intercambiar, seleccionar la más pequeña de las partes restantes y cambiarla por la segunda, y así sucesivamente.
#includelt;iostream.hgt;voidSelectSort(int*pData,intCount){intiTemp;intiPos;for(inti=0;ilt;Count-1;i){iTemp=pData[i];iPos=i;for(intj= i 1;jlt;Count;j){if(pData[j]lt;iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp ;}}voidmain(){intdata[]={10,9,8,7,6,5,4};SelectSort(data,7);for(inti=0;ilt;7;i)coutlt;lt; data[i]lt;lt;;coutlt;lt;\n;}Orden inverso (peor de los casos)
Primera ronda: 10, 9, 8, 7-gt (iTemp=9) 10; , 9, 8, 7-gt; (iTemp=8) 10, 9, 8, 7-gt; (iTemp=7) 7, 9, 8, 10 (intercambiados una vez)
Segunda ronda: 7, 9, 8, 10-gt; 7, 9, 8, 10 (iTemp=8)-gt; (iTemp=8) 7, 8, 9, 10 (intercambiados una vez)
Primera ronda : 7, 8, 9, 10-gt; (iTemp=9) 7, 8, 9, 10 (0 intercambios)
Número de ciclos: 6 veces
Número de intercambios : 2 veces
Otros:
Primera ronda: 8, 10, 7, 9-gt; (iTemp=8) 8, 10, 7, 9-gt ; 7) 8, 10, 7, 9-gt; (iTemp=7) 7, 10, 8, 9 (intercambiados una vez)
Segunda ronda: 7, 10, 8, 9-gt; =8) 7, 10, 8, 9-gt; (iTemp=8) 7, 8, 10, 9 (1 intercambio)
Primera ronda: 7, 8, 10, 9-gt; iTemp=9) 7, 8, 9, 10 (1 intercambio)
Número de ciclos: 6 veces
Número de intercambios: 3 veces
p>
Desafortunadamente, el número de bucles requeridos por el algoritmo sigue siendo 1/2*(n-1)*n. Entonces la complejidad del algoritmo es O (n*n).
Veamos su intercambio. Dado que cada bucle externo solo produce un intercambio (solo un valor mínimo). Entonces f(n)lt;=n
Entonces tenemos f(n)=O(n). Por tanto, cuando los datos son caóticos, el número de intercambios se puede reducir hasta cierto punto.
El método de inserción es más complicado. Su principio de funcionamiento básico es extraer la tarjeta, encontrar la posición correspondiente en la tarjeta anterior para insertarla y luego continuar con la siguiente tarjeta #includelt; voidInsertSort (int*pData, intCount). ) {intiTemp; intiPos; for(inti=1;ilt;Count;i){iTemp=pData[i];//Guarde el número que se insertará iPos=i-1;//El número de números de matriz que se insertarán while((iPosgt;=0) amp;amp;(iTemplt;pData[iPos])){//Inicie la comparación desde el último (el número más grande) y mueva los números mayores hacia atrás pData[iPos 1]= pData[iPos];iPos--;} pData[iPos 1]=iTemp; //Insertar posición del número}}voidmain(){intdata[]={10, 9, 8, 7, 6, 5, 4}; (datos, 7); for(inti =0;ilt;7;i )coutlt;lt;datalt;lt;;coutlt;lt;\n;}Otros:
Primera ronda: 8, 10 , 7, 9-gt; 8, 10, 7, 9 (intercambio 0 veces) (ciclo 1 vez)
Segunda ronda: 9, 10, 8, 7-gt; 7 (intercambio 1 vez) (Ciclo 2 veces)
Primera ronda: 8, 9, 10, 7-gt; 7, 8, 9, 10 (intercambio 1 vez) (Ciclo 3 veces)
Ciclo Número de veces: 6 veces
Número de intercambios: 3 veces
Otros:
Primera ronda: 8, 10, 7, 9-gt; 8, 10, 7, 9 (intercambio 0 veces) (ciclo 1 vez)
Segunda ronda: 8, 10, 7, 9-gt; 1 vez) (ciclo 2 veces) )
Primera ronda: 7, 8, 10, 9-gt; 7, 8, 9, 10 (1 intercambio) (1 ciclo)
Número de intercambios: 2 veces
El análisis de comportamiento al final de lo anterior en realidad crea una ilusión, haciéndonos pensar que este algoritmo es el mejor. entre los algoritmos simples, de hecho, no lo es.
Debido a que el número de bucles no es fijo, aún podemos usar el método O. Se puede ver en los resultados anteriores que el número de ciclos f(n)lt;=
1/2*n*(n-1)lt;=1/2*n*n. Por lo tanto, su complejidad sigue siendo O (n * n) (tenga en cuenta que, de hecho, si no se muestra la diferencia entre estas clasificaciones simples, el número de intercambios aún se puede derivar de esta manera). Ahora mire el intercambio. Desde la apariencia, el número de intercambios es O (n) (la derivación es similar al método de selección), pero cada vez tenemos que realizar el mismo número de '=. ' operaciones como el bucle interno. Para un intercambio normal necesitamos tres '='s
Y aquí evidentemente hay unos cuantos más, así que perdemos el tiempo.
Al final, personalmente creo que entre los algoritmos de clasificación simples, el método de selección es el mejor. Entre los algoritmos de clasificación avanzados, solo presentaremos este, y también es el más rápido que conozco (según la información que he leído).
Aún funciona como un árbol binario. Primero, elegimos un valor intermedio. En el programa central, usamos el valor intermedio de la matriz y luego colocamos el más pequeño a la izquierda y el más grande a la derecha (la implementación específica es buscar). de ambos lados, y después de encontrar un intercambio de pareja). Luego utilice este proceso en ambos lados (el método más sencillo: la recursividad).
1. Clasificación rápida: // Este código se puede compilar correctamente, pero se produce un error tan pronto como se ejecuta. Hay algunos problemas con los detalles internos y aún no he encontrado una solución.
#includelt;iostream.hgt;voidrun(int*pData,intleft,intright){inti,j;intmiddle,iTemp;i=left;j=right;middle=pData[left];do{ while((pData[i] lt; middle)amp; (ilt; right))//Escanee el número i mayor que la mediana desde la izquierda mientras ((pData[j]gt; middle)amp; (jgt; left))//Escanee desde izquierda Búsqueda derecha de números j--; if (ilt; = j) // Encontré un par de valores {//Exchange iTemp=pData[i]; =iTemp;i;j--;}} while(ilt;=j);//Si los subíndices escaneados en ambos lados están entrelazados, deténgase (completar una vez)//Cuando la parte izquierda tenga un valor (leftlt;j) , recurse la mitad izquierda if (leftlt; j) run (pData, left, j); // Cuando la parte derecha tiene un valor (rightgt; i), recurre la mitad derecha if (rightgt; i) run (pData, i, derecha } voidQuickSort( int*pData, intCount){run(pData, 0, Count-1);}voidmain(){intdata[]={10, 9, 8, 7, 6, 5, 4}; (data, 7); for(inti=0;ilt;7;i)coutlt;lt;data[i]lt;lt;;// El código del autor original aquí es incorrecto, el resultado se debe a la fecha [i] , y la salida del nombre de la matriz de fecha es la dirección coutlt ;lt;\n;}No doy un análisis del comportamiento aquí, porque es muy simple. Analicemos el algoritmo directamente: primero, consideramos la situación más ideal<. /p>
1. El tamaño de la matriz es una potencia de 2, siempre puede ser divisible por 2 si se divide de esta manera. Supongamos que es la k-ésima potencia de 2, es decir, k=log2(n).
2. Cada vez el valor que elegimos resulta ser el valor medio, de modo que la matriz se puede dividir en partes iguales.
El primer nivel de recursividad, se repite n veces, el segundo nivel se repite 2*(n/2)...
Entonces *** hay n 2(n/ 2 ) 4(n/4) ... n*(n/n) = n n n ... n=k*n=log2(n)*n
Entonces la complejidad del algoritmo es O(log2 ( n)*n)
Otras situaciones solo serán peores que esta situación. El peor de los casos es que cada vez que el medio seleccionado sea el valor mínimo o máximo, se convertirá en
. En el método de intercambio (peor debido al uso de recursividad). Pero, ¿qué posibilidades crees que esto suceda? Jaja, no tienes que preocuparte por este problema en absoluto. La práctica ha demostrado que, en la mayoría de los casos, la clasificación rápida es siempre la mejor.
Si le preocupa este problema, puede utilizar la clasificación en montón, que es un algoritmo O(log2(n)*n) inestable, pero suele ser más lento.
Para una clasificación rápida (porque es necesario reorganizar el montón). Burbujeo bidireccional
Normalmente el burbujeo es unidireccional, pero aquí es bidireccional, lo que significa que se debe realizar el trabajo inverso.
#includelt;iostream.hgt;inlinevoidexchange(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubblesort(int*array,intnum){inti,j, k, bandera=0; para (i=0; ilt; num; i ){printf (d, matriz[i]);}printf (\n); /El número de todos los números es num flag=0; for(j=i;jlt;num-i-1;j){//El orden de los números inferiores se organizará cada vez que se cicle el ciclo, por lo que inicialmente j = i;if(array[j]gt;array[j 1]){exchange(amp;array[j],amp;array[j 1]);flag=1;}}for(k=num-1- i -1;kgt;i;k--){//El orden de los datos superiores también se ordenará cada vez que se repite, por lo que inicialmente k=num-i-2if(array[k]lt;array[k- 1 ]){exchange(amp;array[k],amp;array[k-1]);flag=1;}}if(flag==0){//Si la bandera no ha cambiado, significa que no se ha producido el intercambio de datos Luego se completa la clasificación return;}}}voidmain(){intdata[]={10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -10, -1} ; bubblesort (data, 12) ;for(inti=0;ilt;12;i)coutlt;lt;datalt;lt;;coutlt;lt;\n;} Creo que no es necesario analizar este programa, puedes solo échale un vistazo. Si no lo entiendes, puedes preguntar en el foro.
Archivo MyData.h
//////////////////////////////// // /////////////////////////
clase CMyData
{
público:
CMyData(int Index, char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize };
const char* GetData(){ return m_strDatamember }; está sobrecargado aquí Símbolo:
CMyDataamp; operador =(CMyDataamp;SrcData);
bool operador lt (CMyDataamp; datos);
bool operador gt; (CMyDataamp; ; datos );
privado:
char* m_strDatamember
int m_iDataSize
};
///////////////////////////////////////////////// ////// //////
Archivo MyData.cpp
//////////////////// //////// ////////////////////////////////
CMyData:: CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
eliminar[ ] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index, char* strData):
m_iIndex (Índice),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = nuevo carácter [m_iDataSize 1];
strcpy(m_strDatamember, strData);
}
CMyDataamp; = (CMyData y SrcData)
{
m_iIndex = SrcData.m_iIndex
m_iDataSize = SrcData.GetDataSize(); = nuevo carácter[m_i
DataSize 1];
strcpy(m_strDatamember, SrcData.GetData());
return *this;
}
bool CMyData ::operador lt; (CMyDataamp; datos)
{
return m_iIndexlt; data.m_iIndex;
}
bool CMyData: ：operador gt; (CMyDataamp; datos)
{
return m_iIndexgt; data.m_iIndex;
}
//// /////////////////////////////////////////////////// /// /////
//////////////////////////////////// ////// /////////////////////
//Parte principal del programa
#include lt; iostream.hgt;
#include MyData.h
template lt; class Tgt;
void run(T* pData, int left, int right)
{
int i, j;
T medio, iTemp
i = izquierda
j; = right;
//Todas las siguientes comparaciones llaman a nuestra función de operador sobrecargada
middle = pData[(left right)/2] //Encontrar el valor medio
;do{
while((pDatalt; middle) amp; amp; (ilt; right))//Escanee desde la izquierda en busca de números mayores que el valor mediano
i ;
while((pData[j]gt; middle) amp; amp; (jgt; left))//Escanea el número mayor que el valor del medio desde la derecha
j --;
if (ilt;=j)//Se encontró un par de valores
{
//Intercambio
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i;
j--;
}
} while(ilt;=j);// Si los subíndices escaneados en ambos lados están entrelazados, deténgase (completar una vez)
//Cuando la parte izquierda tiene un valor (leftlt;j), mitad izquierda recursiva
if(leftlt;j)
run(pData, left, j);
//Cuando la parte derecha tiene un valor (rightgt; i ), la mitad derecha recursiva
if(rightgt;i)
run(pData, i, derecha);
}
plantilla lt; clase Tgt;
void QuickSort(T* pData, int Count)
{
run(pData, 0, Count-1);
p>}
void main()
{
Datos CMyData[]
= {
CMyData (8, xulion),
CMyData (7, sanzoo),
CMyData (6, wangjun),
CMyData (5, VCKBASE),
CMyData (4, jacky2000),
CMyData (3, cwally),
CMyData (2, VCUSER),
CMyData(1, isdong)
};
QuickSort(datos, 8);
for (int i=0; ilt; 8; i )
coutlt;lt;data.m_iIndexlt;lt; lt;lt;data.GetData()lt;lt;\n;
coutlt; \n；