Login
Accedi

Galleria mappe mentale Algoritmo di ordinamento della struttura dei dati

Algoritmo di ordinamento della struttura dei dati

Gli algoritmi di ordinamento sono spesso considerati nelle strutture di dati, inclusi l'ordinamento per inserzione, l'ordinamento in collina, l'ordinamento a bolle e quasi tutti gli algoritmi di ordinamento. L'ordinamento è il processo di riorganizzazione degli elementi nella tabella in modo che gli elementi nella tabella soddisfino l'ordine crescente o decrescente delle parole chiave. .

Modificato alle 2023-09-18 01:41:47

WSZUS4lF

Lavori recenti Visualizza più lavori>>

Algoritmo di ordinamento della struttura dei dati

WSZUS4lF

Lavori recenti Visualizza più lavori>>

Consigliato per te
Profilo

Nozioni di base comuni sul computer
- 9
WSCoUtCI
Dati e strutture dati
- 13
WSZUS4lF
Capitolo Uno Introduzione
- 4
WSCoUtCI
01Struttura dei dati
- 7
VisioneCreativa
Mappa mentale dell'algoritmo e della struttura dei dati
- 7
WSZUS4lF
Algoritmo di ricerca della struttura dati
- 9
WSZUS4lF
Strutture dati e algoritmi
- 13
WSZUS4lF
Implementazione della struttura dei dati e analisi degli algoritmi
- 9
WSZUS4lF
struttura dati
- 9
WSZUS4lF
Strutture dati stack e code
- 10
WSZUS4lF

ordinare

Concetti base di ordinamento

ordinare

Riorganizzare gli elementi nella tabella in modo che gli elementi nella tabella soddisfino il processo di aumento o diminuzione per parola chiave

stabilità dell'algoritmo

Se ci sono due elementi Ri e Rj nell'algoritmo di ordinamento, le loro parole chiave corrispondenti keyi = keyj e Ri è davanti a Rj prima dell'ordinamento. Se dopo l'ordinamento Ri è ancora davanti a Rj, questo algoritmo è stabile. Altrimenti è instabile.

La stabilità non può misurare la qualità di un algoritmo

ordinamento di inserimento

ordinamento per inserzione diretta

Dividere la sequenza in due parti, ordinate e non ordinate, e inserire ogni volta i bit appropriati nella parte ordinata.

principio

Lo stato della lista da ordinare L [1···n] in un determinato momento durante un determinato processo di ordinamento

1. Trova la posizione di inserimento k di L(i) in L[1···i-1]

2. Sposta tutti gli elementi in L[k···i-1] indietro di una posizione

3) Copia L(i) in L(k)

prestazione

Complessità spaziale O(1)

La migliore complessità temporale è O(n)

Complessità temporale peggiore O(n^2)

Complessità temporale media O(n^2)

Stabilizzare

Sii applicabile

elenco di sequenze, elenco concatenato

ordinamento a metà inserimento

Ordinamento per inserimento diretto utilizzando la ricerca binaria

Numero di confronti di elementi

prestazione

Complessità spaziale O(1)

miglior complessità temporale

Complessità temporale peggiore O(n^2)

Complessità temporale media O(n^2)

Stabilizzare

Sii applicabile

Tabella di sequenza

Ordinamento collinare

La tabella di ordinamento è divisa in diverse sottotabelle, ciascuna sottotabella viene inserita direttamente nell'ordinamento e infine viene eseguito l'intero ordinamento per inserimento.

prestazione

Complessità spaziale O(1)

Complessità temporale O(n^1.3)

Stima

Complessità temporale peggiore O(n^2)

instabile

Sii applicabile

Tabella di sequenza

Ordinamento dello scambio

Ordinamento a bolle

Partendo dall'inizio, confronta ogni coppia di elementi adiacenti e spostali dietro se sono più grandi. Dopo il confronto, l'elemento più grande sarà alla fine. Ripeti il processo sopra, non migliore di quello più grande, e continua a ripetere per ottenere la sequenza.

prestazione

Complessità spaziale O(1)

miglior complessità temporale

Quando la sequenza è ordinata, il numero di confronti è n-1, il numero di mosse è 0 e la complessità temporale è O(n).

Complessità temporale peggiore O(n^2)

Quando la sequenza è invertita

Complessità temporale media O(n^2)

Stabilizzare

Sii applicabile

elenco di sequenze, elenco concatenato

Ordinamento rapido

1. Innanzitutto, prendi un numero dalla sequenza come numero base. 2. Processo di partizionamento: metti tutti i numeri più grandi di questo numero alla sua destra e metti tutti i numeri più piccoli o uguali alla sua sinistra. 3. Ripeti il secondo passaggio per gli intervalli sinistro e destro finché non rimane un solo numero in ciascun intervallo.

Il caso peggiore è che ogni volta il numero centrale selezionato sia l'elemento più grande o più piccolo nella sequenza corrente. L'ordinamento rapido di una tabella di dati di lunghezza n richiede n divisioni, rendendo la complessità temporale dell'intero algoritmo di ordinamento O(n^2)

prestazione

spazio

Peggiore complessità spaziale O(n)

complessità spaziale media

tempo

miglior complessità temporale

La peggiore complessità del momento

O(n^2)

complessità temporale media

instabile

Sii applicabile

Tabella di sequenza

ordinamento della selezione

Ordinamento di selezione semplice

Ogni volta viene selezionato quello più piccolo e scambiato con la posizione specificata.

Numero di confronti n(n-1)/2 Complessità temporale O(n^2)

prestazione

Complessità spaziale O(1)

La migliore complessità temporale è O(n^2)

Complessità temporale peggiore O(n^2)

Complessità temporale media O(n^2)

instabile

Sii applicabile

elenco di sequenze, elenco concatenato

Ordinamento dell'heap

mucchio

Una sequenza di n parole chiave L[1 ... n] è detta heap se e solo se la sequenza soddisfa:

piccolo mucchio di radici

dagendui

ordinare

Per prima cosa costruisci la colonna da ordinare come heap e seleziona l'elemento più grande (o più piccolo) nell'heap, che è l'elemento superiore dell'heap e generalo. Dopo che l'elemento superiore dell'heap è stato emesso, l'elemento inferiore dell'heap viene inviato in cima all'heap e le proprietà dell'heap vengono distrutte. L'elemento superiore dell'heap viene regolato verso il basso per formare nuovamente un heap e l'elemento superiore dell'heap viene visualizzato ripetutamente.

Costruisci una pila

1. Costruisci un albero binario in ordine sequenziale

{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}

2. Trova ⌊n/2⌋ e regola l'albero utilizzandolo come nodo radice.

3. Trova il nodo prima del nodo precedente, continua a regolare e ripeti Durante il processo di aggiustamento, assicurati che l'heap modificato sia ancora conforme alle regole.

inserire

Aggiungi il nodo all'ultimo nodo e regolalo dal basso verso l'alto

eliminare

È possibile eliminare solo il nodo radice

Sostituisci l'ultimo nodo con il nodo radice e regolalo dall'alto verso il basso.

unisci ordinamento

Ordinamento di unione bidirezionale

La tabella da ordinare contiene n record, che possono essere considerati come n sottotabelle ordinate. Ciascuna sottotabella ha una lunghezza pari a 1, quindi vengono ordinate a coppie. Ottieni ⌈n/2⌉ elenchi ordinati con una lunghezza di 2 o 1, quindi uniscili in due pozzetti. Ripeti l'operazione finché non vengono uniti in un elenco ordinato di lunghezza n. Nota la differenza tra unione ricorsiva e unione non ricorsiva

prestazione

Complessità spaziale O(n)

miglior complessità temporale

La peggiore complessità del momento

complessità temporale media

Stabilizzare

Sii applicabile

Tabella di sequenza

Ordinamento radicale

L'ordinamento radicale consiste nell'ordinare prima in base all'ordine più basso, quindi a raccogliere; quindi a ordinare in base all'ordine più alto, quindi a raccogliere e così via, fino all'ordine più alto;