Zusammenfassung der Sortieralgorithmen für Datenstrukturen

Zusammenfassung des Datenstruktur-Sortieralgorithmus

Übersicht

Die Sortierung verfügt über interne und externe Sortierung Bei der internen Sortierung werden Datensätze im Speicher sortiert, während bei der externen Sortierung die sortierten Daten sehr groß sind und nicht alle sortierten Datensätze gleichzeitig aufnehmen können. Während des Sortiervorgangs muss auf den externen Speicher zugegriffen werden.

1. Einfügungssortierung - Gerade Einfügungssortierung

Grundidee:

Fügen Sie einen Datensatz in ein sortiertes Array ein. In der Sequenztabelle wird eine neue Reihenfolge eingefügt Die Liste wird mit der um 1 erhöhten Anzahl von Datensätzen erhalten. Das heißt: Behandeln Sie zuerst den ersten Datensatz der Sequenz als geordnete Teilsequenz und fügen Sie dann nacheinander den zweiten Datensatz ein, bis die gesamte Sequenz geordnet ist.

Wichtige Punkte: Richten Sie Wächter für die temporäre Speicherung und Beurteilung von Array-Grenzen ein.

Wenn ein Element gefunden wird, das dem eingefügten Element entspricht, platziert das eingefügte Element das einzufügende Element nach dem gleichen Element. Daher hat sich die Reihenfolge gleicher Elemente nicht geändert. Die Reihenfolge der ursprünglichen ungeordneten Reihenfolge ist die Reihenfolge nach der Sortierung, sodass die Einfügungssortierung stabil ist.

Implementierung des Algorithmus:

void print(int a[], int n ,int i){  
    cout<<i <<":";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<" ";  
    }  
    cout<<endl;  
}  
  
  
void InsertSort(int a[], int n)  
{  
    for(int i= 1; i<n; i++){  
        if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  
            int j= i-1;   
            int x = a[i];        //复制为哨兵，即存储待排序元素  
            a[i] = a[i-1];           //先后移一个元素  
            while(x < a[j]){  //查找在有序表的插入位置  
                a[j+1] = a[j];  
                j--;         //元素后移  
            }  
            a[j+1] = x;      //插入到正确位置  
        }  
        print(a,n,i);           //打印每趟排序的结果  
    }  
      
}  
  
int main(){  
    int a[8] = {3,1,5,7,2,4,9,6};  
    InsertSort(a,8);  
    print(a,8,8);  
}

Zeitliche Komplexität: O(n^2).

Andere Einfügungssortierung umfasst binäre Einfügungssortierung und 2-Wege-Einfügungssortierung.

2. Einfügungssortierung – Hill Sort (Shell`s Sort)

Hill Sort wurde 1959 von D.L. Shell vorgeschlagen. Es ist fortgeschrittener als die direkte Sortierung Big Verbesserung. Hill-Sortierung wird auch als reduzierte inkrementelle Sortierung bezeichnet

Grundidee:

Teilen Sie zunächst die gesamte Sequenz der zu sortierenden Datensätze in mehrere Untersequenzen für die Direkteinfügungssortierung auf und warten Sie dann auf die Datensätze Die gesamte Reihenfolge muss „Grundsätzlich in Ordnung“ sein, dann werden alle Datensätze direkt eingefügt und der Reihe nach sortiert.

Operationsmethode:

Wählen Sie eine inkrementelle Sequenz t1, t2, ..., tk aus, wobei ti>tj, tk=1; entsprechend der Anzahl der inkrementellen Sequenzen k, k-mal ausführen Bei der Sequenzsortierung wird die zu sortierende Spalte entsprechend dem entsprechenden Inkrement ti in mehrere Teilsequenzen der Länge m unterteilt, und für jede Untertabelle wird eine direkte Einfügungssortierung durchgeführt. Nur wenn der Inkrementfaktor 1 ist, wird die gesamte Sequenz als Tabelle verarbeitet und die Länge der Tabelle entspricht der Länge der gesamten Sequenz.

Algorithmusimplementierung:

Wir verarbeiten einfach die inkrementelle Sequenz: inkrementelle Sequenz d = {n/2,n/4, n/8 .....1} n ist die Anzahl der zu sortierenden Zahlen

Das heißt: Zuerst wird die Menge der zu sortierenden Datensätze entsprechend einem bestimmten Inkrement d (n/2, n ist die Anzahl der Zahlen) in mehrere Gruppen von Teilsequenzen unterteilt Die in jeder Gruppe aufgezeichneten Indizes unterscheiden sich um d. Führen Sie eine direkte Einfügungssortierung für alle Elemente in jeder Gruppe durch, gruppieren Sie sie dann mit einem kleineren Inkrement (d/2) und führen Sie eine direkte Einfügungssortierung für jede Gruppe durch. Reduzieren Sie das Inkrement weiter, bis es 1 beträgt, und verwenden Sie schließlich die direkte Einfügungssortierung, um die Sortierung abzuschließen.

void print(int a[], int n ,int i){ 
    cout<<i <<":"; 
    for(int j= 0; j<8; j++){ 
        cout<<a[j] <<" "; 
    } 
    cout<<endl; 
} 
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 缩小增量，如果是直接插入排序，dk=1
 *
 */ 
   
void ShellInsertSort(int a[], int n, int dk) 
{ 
    for(int i= dk; i<n; ++i){ 
        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 
            int j = i-dk;    
            int x = a[i];           //复制为哨兵，即存储待排序元素 
            a[i] = a[i-dk];         //首先后移一个元素 
            while(x < a[j]){     //查找在有序表的插入位置 
                a[j+dk] = a[j]; 
                j -= dk;             //元素后移 
            } 
            a[j+dk] = x;            //插入到正确位置 
        } 
        print(a, n,i ); 
    } 
       
} 
   
/**
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序
 *
 */ 
void shellSort(int a[], int n){ 
   
    int dk = n/2; 
    while( dk >= 1  ){ 
        ShellInsertSort(a, n, dk); 
        dk = dk/2; 
    } 
} 
int main(){ 
    int a[8] = {3,1,5,7,2,4,9,6}; 
    //ShellInsertSort(a,8,1); //直接插入排序 
    shellSort(a,8);           //希尔插入排序 
    print(a,8,8); 
}

Hill-Sorting-Aktualitätsanalyse ist schwierig. Die Anzahl der Schlüsselcodevergleiche und die Anzahl der Datensatzbewegungen hängen von der Auswahl der Inkrementfaktorsequenz d ab Häufigkeit genau abgeschätzt werden kann. Bisher hat noch niemand eine Methode zur Auswahl der besten inkrementellen Faktorfolge angegeben. Die Reihenfolge der inkrementellen Faktoren kann auf verschiedene Arten verwendet werden, einschließlich ungerader Zahlen und Primzahlen. Es ist jedoch zu beachten, dass es außer 1 keine gemeinsamen Faktoren zwischen den inkrementellen Faktoren gibt und der letzte inkrementelle Faktor 1 sein muss. Die Hill-Sortiermethode ist eine instabile Sortiermethode.

3. Auswahlsortierung – Einfache Auswahlsortierung

Grundidee:

Wählen Sie in einer zu sortierenden Zahlenmenge die Option „Kleinste suchen“ (bzw größte) Zahl und tauschen Sie sie mit der Zahl an der ersten Position aus; finden Sie dann die kleinste (oder größte) Zahl unter den verbleibenden Zahlen und tauschen Sie sie mit der Zahl an der zweiten Position aus, und so weiter, bis die n-1-ten Elemente (die (vorletzte Zahl) und das n-te Element (die letzte Zahl) werden verglichen.

Betriebsmethode:

Im ersten Durchgang den Datensatz mit dem kleinsten Schlüsselcode unter n Datensätzen finden und ihn mit dem ersten Datensatz austauschen;

Der zweite Durchgang , wählen Sie den Datensatz mit dem kleinsten Schlüsselcode aus den n-1 Datensätzen aus, beginnend mit dem zweiten Datensatz, und tauschen Sie ihn mit dem zweiten Datensatz aus

und so weiter...

i-mal; Wählen Sie dann den Datensatz mit dem kleinsten Schlüsselcode aus den n-i+1 Datensätzen beginnend mit dem i-ten Datensatz aus und tauschen Sie ihn mit dem i-ten Datensatz aus,

bis die gesamte Sequenz nach dem Schlüsselcode geordnet ist .

Algorithmusimplementierung:

void print(int a[], int n ,int i){  
    cout<<"第"<<i+1 <<"趟 : ";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
/** 
 * 数组的最小值 
 * 
 * @return int 数组的键值 
 */  
int SelectMinKey(int a[], int n, int i)  
{  
    int k = i;  
    for(int j=i+1 ;j< n; ++j) {  
        if(a[k] > a[j]) k = j;  
    }  
    return k;  
}  
  
/** 
 * 选择排序 
 * 
 */  
void selectSort(int a[], int n){  
    int key, tmp;  
    for(int i = 0; i< n; ++i) {  
        key = SelectMinKey(a, n,i);           //选择最小的元素  
        if(key != i){  
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
        }  
        print(a,  n , i);  
    }  
}  
int main(){  
    int a[8] = {3,1,5,7,2,4,9,6};  
    cout<<"初始值：";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl<<endl;  
    selectSort(a, 8);  
    print(a,8,8);  
}

Verbesserung der einfachen Auswahlsortierung - binäre Auswahlsortierung

Einfache Auswahlsortierung, jede Schleife kann nach der Sortierpositionierung nur ein Element bestimmen. Wir können erwägen, die Positionierung von zwei Elementen (der aktuellen maximalen und minimalen Datensätze) für jeden Zyklus zu verbessern und so die Anzahl der für die Sortierung erforderlichen Zyklen zu reduzieren. Nach der Verbesserung sind zum Sortieren von n Daten höchstens [n/2] Schleifen erforderlich. Die spezifische Implementierung lautet wie folgt:

void SelectSort(int r[],int n) {  
    int i ,j , min ,max, tmp;  
    for (i=1 ;i <= n/2;i++) {    
        // 做不超过n/2趟选择排序   
        min = i; max = i ; //分别记录最大和最小关键字记录位置  
        for (j= i+1; j<= n-i; j++) {  
            if (r[j] > r[max]) {   
                max = j ; continue ;   
            }    
            if (r[j]< r[min]) {   
                min = j ;   
            }     
      }    
      //该交换操作还可分情况讨论以提高效率  
      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
  
    }   
}

4. Auswahlsortierung - Heap-Sortierung (Heap-Sortierung)

Heap-Sortierung ist eine Baumauswahlsortierung, bei der es sich um eine direkte Auswahl handelt sortieren. Effektive Verbesserung.

Grundidee:

Die Definition von Heap lautet wie folgt: eine Folge von n Elementen (k1, k2,...,kn), genau dann, wenn

erfüllt ist

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

(b) 小顶堆序列：（12，36，24，85，47，30，53，91）

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

1. 如何将n 个待排序的数建成堆；

2. 2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。

再讨论对n 个元素初始建堆的过程。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
  
  
/** 
 * 已知H[s…m]除了H[s] 外均满足堆的定义 
 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
 * 
 * @param H是待调整的堆数组 
 * @param s是待调整的数组元素的位置 
 * @param length是数组的长度 
 * 
 */  
void HeapAdjust(int H[],int s, int length)  
{  
    int tmp  = H[s];  
    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
    while (child < length) {  
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
            ++child ;  
        }  
        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
            child = 2*s+1;  
        }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
             break;  
        }  
        H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
    }  
    print(H,length);  
}  
  
  
/** 
 * 初始堆进行调整 
 * 将H[0..length-1]建成堆 
 * 调整完之后第一个元素是序列的最小的元素 
 */  
void BuildingHeap(int H[], int length)  
{   
    //最后一个有孩子的节点的位置 i=  (length -1) / 2  
    for (int i = (length -1) / 2 ; i >= 0; --i)  
        HeapAdjust(H,i,length);  
}  
/** 
 * 堆排序算法 
 */  
void HeapSort(int H[],int length)  
{  
    //初始堆  
    BuildingHeap(H, length);  
    //从最后一个元素开始对序列进行调整  
    for (int i = length - 1; i > 0; --i)  
    {  
        //交换堆顶元素H[0]和堆中最后一个元素  
        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
        HeapAdjust(H,0,i);  
  }  
}   
  
int main(){  
    int H[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(H,10);  
    HeapSort(H,10);  
    //selectSort(a, 8);  
    cout<<"结果：";  
    print(H,10);  
  
}

分析:

设树深度为k，从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

5. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法的实现：

void bubbleSort(int a[], int n){  
    for(int i =0 ; i< n-1; ++i) {  
        for(int j = 0; j < n-i-1; ++j) {  
            if(a[j] > a[j+1])  
            {  
                int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
            }  
        }  
    }  
}

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。

6. 交换排序—快速排序（Quick Sort）

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

算法的实现：

递归实现：

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  
  
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基准元素  
    while(low < high){                                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
  
  
void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //将表一分为二  
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    }  
}  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"结果：";  
    print(a,10);  
  
}

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

7. 归并排序（Merge Sort）

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]否则，rf[k]=r[j]； j++； k++； 转⑵//将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空合并结束。

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
}

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  
  
void MergeSort(ElemType *r, ElemType *rf, int lenght)  
{   
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
    }  
}  
  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"结果：";  
    print(a,10);  
  
}

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t) r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          /*平分*p 表*/  
        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   /*对顺序表*p 作归并排序*/  
    MSort(r, rf,0, n-1);  
}

更多PHP相关知识，请访问PHP中文网！

Das obige ist der detaillierte Inhalt vonZusammenfassung der Sortieralgorithmen für Datenstrukturen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!