2022年考研数据结构_8 排序

太过爱你忘了你带给我的痛 2022-12-31 05:23 197阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  8. 排序
 *   *  8.0 算法复杂度
     *  8.1 冒泡排序（Bubble Sort）
     *   *  1.1 算法描述
         *  1.2 动图演示
         *  1.3 代码实现
     *  8.2 选择排序（Selection Sort）
     *   *  2.1 算法描述
         *  \*\*2.2 动图演示\*\*
         *  2.3 代码实现
         *  2.4 算法分析
     *  8.3 插入排序（Insertion Sort）
     *   *  3.1 算法描述
         *  3.2 动图演示
         *  3.2 代码实现
         *  3.4 算法分析
     *  8.4 希尔排序（Shell Sort）
     *   *  4.1 算法描述
         *  4.2 动图演示
         *  4.3 代码实现
         *  4.4 算法分析
     *  8.5 归并排序（Merge Sort）
     *   *  5.1 算法描述
         *  5.2 动图演示
         *  5.3 代码实现
         *  5.4 算法分析
     *  8.6 快速排序（Quick Sort）
     *   *  6.1 算法描述
         *  6.2 动图演示
         *  6.3 代码实现
     *  8.7 堆排序（Heap Sort）
     *   *  7.1 算法描述
         *  7.2 动图演示
         *  7.3 代码实现
     *  8.8 计数排序（Counting Sort）
     *   *  8.1 算法描述
         *  8.2 动图演示
         *  8.3 代码实现
         *  8.4 算法分析
     *  8.9 桶排序（Bucket Sort）
     *   *  9.1 算法描述
         *  9.2 图片演示
         *  9.3 代码实现
         *  9.4 算法分析
     *  8.10 基数排序（Radix Sort）
     *   *  10.1 算法描述
         *  10.2 动图演示
         *  10.3 代码实现
         *  10.4 算法分析
     *  8.11 多路归并排序
     *   *  基本思想
         *  两两归并排序
         *  \*\*多路归并排序\*\*
         *   *  胜者树
             *  败者树
             *  败者树的建立与调整
             *  败者树的java代码
             *  败者树的效率

# 8. 排序 #

十种常见排序算法可以分为两大类：

*  **比较类排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
 *  **非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

![img][]

## 8.0 算法复杂度 ##

![img][img 1]

*相关概念*

*  **稳定**：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
 *  **不稳定**：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
 *  **时间复杂度**：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 *  \*\*空间复杂度：\*\*是指算法在计算机

内执行时所需存储空间的度量，它也是数据规模n的函数。

***每一趟排序，都会有一个元素在最终的位置上，堆排序，冒泡排序，快速排序，选择排序***

***和序列初始化状态没有关系的有 简单选择排序和二路归并排序***

## 8.1 冒泡排序（Bubble Sort） ##

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

### 1.1 算法描述 ###

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *  针对所有的元素重复以上的步骤，除了最后一个；
 *  重复步骤1~3，直到排序完成。

### 1.2 动图演示 ###

![img][img 2]

### 1.3 代码实现 ###

## 8.2 选择排序（Selection Sort） ##

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

### 2.1 算法描述 ###

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

*  初始状态：无序区为R\[1…n\]，有序区为空；
 *  第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R\[1…i-1\]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R\[k\]，将它与无序区的第1个记录R交换，使R\[1…i\]和R\[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
 *  n-1趟结束，数组有序化了。

### **2.2 动图演示** ###

![img][img 3]

### 2.3 代码实现 ###

### 2.4 算法分析 ###

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

## 8.3 插入排序（Insertion Sort） ##

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

### 3.1 算法描述 ###

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

*  从第一个元素开始，该元素可以认为已经被排序；
 *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
 *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
 *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 *  将新元素插入到该位置后；
 *  重复步骤2~5。

### 3.2 动图演示 ###

![img][img 4]

### 3.2 代码实现 ###

### 3.4 算法分析 ###

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

## 8.4 希尔排序（Shell Sort） ##

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫**缩小增量排序**。

### 4.1 算法描述 ###

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

*  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 *  按增量序列个数k，对序列进行k 趟排序；
 *  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

*希尔排序的组内排序为直接插入排序*

### 4.2 动图演示 ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fLYG0TBb-1609144969403)(https://gitee.com/fakerlove/picture/raw/master/22.gif)\]

### 4.3 代码实现 ###

// 修改于 2019-03-06
    function shellSort(arr)
    { 
        var len = arr.length;
        for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2))
        {  // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
            for (var i = gap; i < len; i++)
            { 
                var j = i;
                var current = arr[i];
                while (j - gap >= 0 && current < arr[j - gap])
                { 
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }
                arr[j] = current;
            }
        }
        return arr;
    }

### 4.4 算法分析 ###

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

## 8.5 归并排序（Merge Sort） ##

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

### 5.1 算法描述 ###

*  把长度为n的输入序列分成两个长度为n/2的子序列；
 *  对这两个子序列分别采用归并排序；
 *  将两个排序好的子序列合并成一个最终的排序序列。

### 5.2 动图演示 ###

![img][img 5]

### 5.3 代码实现 ###

### 5.4 算法分析 ###

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

## 8.6 快速排序（Quick Sort） ##

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

### 6.1 算法描述 ###

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

*  从数列中挑出一个元素，称为 “基准”（pivot）；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

*就性能而言，快速排序最快*

### 6.2 动图演示 ###

![img][img 6]

![c33402a34dcb6815f05cecbd22945674.gif][]

### 6.3 代码实现 ###

#include <stdio.h>
    #include <stdlib.h>
    
    void display(int array[], int size) {
        for (int i = 0; i < size; i++) {
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    int getStandard(int array[], int i, int j) {
        // 基准数据
        int key = array[i];
        while (i < j) {
            // 因为默认基准是从左边开始，所以从右边开始比较
            // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
            while (i < j && array[j] >= key) {
                j--;
            }
            // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
            if (i < j) {
                array[i] = array[j];
            }
            // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
            while (i < j && array[i] <= key) {
                i++;
            }
            // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
            if (i < j) {
                array[j] = array[i];
            }
        }
        // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
        // 把基准数据赋给正确位置
        array[i] = key;
        return  i;
    }
    
    void QuickSort(int array[], int low, int high) {
        //开始默认基准为 low
        if (low < high) {
            //分段位置下标
            int standard = getStandard(array, low, high);
            //递归调用排序
            //左边排序
            QuickSort(array, low, standard - 1);
            //右边排序
            QuickSort(array, standard + 1, high);
        }
    }
    
    // 合并到一起快速排序
    // void QuickSort(int array[], int low, int high) {
    //     int i   = low;
    //     int j   = high;
    //     int key = array[i];
    //     if (low < high) {
    //         while (i < j) {
    //             while (i < j && array[j] >= key) {
    //                 j--;
    //             }
    //             if (i < j) {
    //                 array[i] = array[j];
    //             }
    //             while (i < j && array[i] <= key) {
    //                 i++;
    //             }
    //             if (i < j) {
    //                 array[j] = array[i];
    //             }
    //         }
    //         array[i]     = key;
    //         int standard = i;
    //         QuickSort(array, low, standard - 1);
    //         QuickSort(array, standard + 1, high);
    //     }
    // }
    
    int main() {
        int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
        printf("%d \n", size);
        QuickSort(array, 0, size - 1);
        display(array, size);
    
        // int size      = 20;
        // int array[20] = {0};                 // 数组初始化
        // for (int i = 0; i < 10; i++) {       // 数组个数
        //     for (int j = 0; j < size; j++) { // 数组大小
        //         array[j] = rand() % 1000;    // 随机生成数大小 0~99
        //     }
        //     printf("原来的数组：");
        //     display(array, size);
        //     QuickSort(array, 0, size - 1);
        //     printf("排序后数组：");
        //     display(array, size);
        //     printf("\n");
        // }
    
        return  0;
    }

## 8.7 堆排序（Heap Sort） ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

### 7.1 算法描述 ###

*  将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
 *  将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R\[1,2…n-1\]<=R\[n\]；
 *  由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

### 7.2 动图演示 ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eApbEzTw-1609144969407)(https://gitee.com/fakerlove/picture/raw/master/20.gif)\]

### 7.3 代码实现 ###

var  len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
     
    function buildMaxHeap(arr) {    // 建立大顶堆
        len = arr.length;
        for(var i = Math.floor(len/2); i >= 0; i--) { 
            heapify(arr, i);
        }
    }
     
    function heapify(arr, i) {      // 堆调整
        var  left = 2 * i + 1,
            right = 2 * i + 2,
            largest = i;
     
        if(left < len && arr[left] > arr[largest]) { 
            largest = left;
        }
     
        if(right < len && arr[right] > arr[largest]) { 
            largest = right;
        }
     
        if(largest != i) { 
            swap(arr, i, largest);
            heapify(arr, largest);
        }
    }
     
    function swap(arr, i, j) { 
        var  temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
     
    function heapSort(arr) { 
        buildMaxHeap(arr);
     
        for(var  i = arr.length - 1; i > 0; i--) { 
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return  arr;
    }

\*建堆，是从  n \\sqrt\{n\} n 开始的，然后不停的往上 heapify，所以i-- \*

## 8.8 计数排序（Counting Sort） ##

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

### 8.1 算法描述 ###

*  找出待排序的数组中最大和最小的元素；
 *  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 *  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
 *  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

### 8.2 动图演示 ###

![img][img 7]

### 8.3 代码实现 ###

### 8.4 算法分析 ###

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

## 8.9 桶排序（Bucket Sort） ##

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

### 9.1 算法描述 ###

*  设置一个定量的数组当作空桶；
 *  遍历输入数据，并且把数据一个一个放到对应的桶里去；
 *  对每个不是空的桶进行排序；
 *  从不是空的桶里把排好序的数据拼接起来。

### 9.2 图片演示 ###

![img][img 8]

### 9.3 代码实现 ###

### 9.4 算法分析 ###

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

## 8.10 基数排序（Radix Sort） ##

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

### 10.1 算法描述 ###

*  取得数组中的最大数，并取得位数；
 *  arr为原始数组，从最低位开始取每个位组成radix数组；
 *  对radix进行计数排序（利用计数排序适用于小范围数的特点）；

### 10.2 动图演示 ###

![img][img 9]

### 10.3 代码实现 ###

### 10.4 算法分析 ###

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d\*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

我们一般提到排序都是指内排序，比如快速排序，堆排序，归并排序等，所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍，我们当然希望如果可以的话都是内排来完成。但对于大数据集来说，内存是远远不够的，这时候就涉及到外排序的知识了。

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

## 8.11 多路归并排序 ##

### 基本思想 ###

外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

一般来说外排序分为两个步骤：预处理和合并排序。即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的内存排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件就是初始顺串，然后采用合并的方法将这些初始顺串逐趟合并成一个有序文件。

### 两两归并排序 ###

假设有一个含10000 个记录的文件，首先通过10 次内部排序得到10 个初始归并段R1～R10 ，其中每一段都含1000 个记录。然后两两归并，直至得到一个有序文件为止

如R1与R2归并排序成R12，R3与R4排序成R34，再R12与R34排序从R1234

这种方法要归并排序多次，时间耗费多，不提倡

### **多路归并排序** ###

由于多路归并，有k路，就要比较k-1次，所以有了减少比较次数的胜者树与败者树，而多路归并常用败者树

多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次， 为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为 s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k- 1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整) (log2m)(n-1)，与k无关。

败者树是完全二叉树， 因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls\[0\]为冠军结点，ls\[1\]–ls\[k- 1\]为比较结点，ls\[k\]–ls\[2k-1\]为叶子结点（同时用另外一个指针索引b\[0\]–b\[k-1\]指向）。另外bk为一个附加的辅助空间，不 属于败者树，初始化时存着MINKEY的值。

多路归并排序算法的过程大致为：

1）：首先将k个归并段中的首元素关键字依次存入b\[0\]–b\[k-1\]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls\[0\]中。然后不断循环：

2）把ls\[0\]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所 在的叶子结点b\[q\]中，调用Adjust顺着b\[q\]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls\[0\]中。循环这个 操作过程直至所有元素被写到有序归并段里。

**伪代码如下：**

void Adjust(LoserTree &ls, int s)
    /*从叶子结点b[s]到根结点的父结点ls[0]调整败者树*/
    {   int t, temp;
       t=(s+K)/2;          /*t为b[s]的父结点在败者树中的下标，K是归并段的个数*/
       while(t>0)                         /*若没有到达树根，则继续*/
       {      if(b[s]>b[ls[t]])        /*与父结点指示的数据进行比较*/
                   {   /*ls[t]记录败者所在的段号，s指示新的胜者，胜者将去参加更上一层的比较*/
                      temp=s;
                      s=ls[t];
                      ls[t]=temp; 
                    }
               t=t/2;                     /*向树根退一层，找到父结点*/
       }
      ls[0]=s;                           /*ls[0]记录本趟最小关键字所在的段号*/
    }
     
     
    void K_merge( int ls[K])
    /*ls[0]~ls[k-1]是败者树的内部比较结点。b[0]~b[k-1]分别存储k个初始归并段的当前记录*/
    /*函数Get_next(i)用于从第i个归并段读取并返回当前记录*/
    {    int b[K+1),i,q;
         for(i=0; i<K;i++)                
         {    b[i]=Get_next(i);           /*分别读取K个归并段的第一个关键字*/  } 
         b[K]=MINKEY;                        /*创建败者树*/
         for(i=0; i<K ; i++)                    /*设置ls中的败者初值*/
               ls[i]=K;
         for(i=K-1 ; i>=0 ; i--)                /*依次从b[K-1]……b[0]出发调整败者*/
              Adjust(ls , i);             /*败者树创建完毕，最小关键字序号存入ls[0] while(b[ls[0]] !=MAXKEY ) { q=ls[0]; /*q为当前最小关键字所在的归并段*/
              prinftf("%d",b[q]);
              b[q]=Get_next(q);
              Adjust(ls,q);                /*q为调整败者树后，选择新的最小关键字*/
         }
    }

#### 胜者树 ####

胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。

**注意：方块，表示最底层要比较的东西，里面的值是要比较的数值，下面的是数值对应的index。**

**圆圈，表示节点与节点之间比较的结果，里面的值是比较后结果，对应的对象的index，这里是胜利的数的index，旁边的是这个圆圈对应的index。**

![img][img 10]

Fig.1是一个胜者树的示例。规定数值小者胜。

\\1. b3 PK b4，b3胜b4负，内部结点ls\[4\]的值为3；

\\2. b3 PK b0，b3胜b0负，内部结点ls\[2\]的值为3；

\\3. b1 PK b2，b1胜b2负，内部结点ls\[3\]的值为1；

\\4. b3 PK b1，b3胜b1负，内部结点ls\[1\]的值为3。.

当叶子结点b3的值变为11时，重构的胜者树所示。

![img][img 11]

\\1. b3 PK b4，b3胜b4负，内部结点ls\[4\]的值为3；

\\2. b3 PK b0，b0胜b3负，内部结点ls\[2\]的值为0

\\3. b1 PK b2，b1胜b2负，内部结点ls\[3\]的值为1；

\\4. b0 PK b1，b1胜b0负，内部结点ls\[1\]的值为1。.

#### 败者树 ####

败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

**注意：方块，表示最底层要比较的东西，里面的值是要比较的数值，下面的是数值对应的index。**

**圆圈，表示节点与节点之间比较的结果，里面的值是比较后结果，对应的对象的index，这里是失败的数的index，旁边的是这个圆圈对应的index。**

**线段上的数字，表示线段下面的圆圈，对应的比较，胜利的数的index。**

![img][img 12]

一棵败者树。规定数大者败。

\\1. b3 PK b4，b3胜b4负，内部结点ls\[4\]的值为4；

\\2. b3 PK b0，b3胜b0负，内部结点ls\[2\]的值为0；

\\3. b1 PK b2，b1胜b2负，内部结点ls\[3\]的值为2；

\\4. b3 PK b1，b3胜b1负，内部结点ls\[1\]的值为1；

\\5. 在根结点ls\[1\]上又加了一个结点ls\[0\]=3，记录的最后的胜者。

败者树重构过程如下：

将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。

比赛沿着到根结点的路径不断进行，直到ls\[1\]处。把败者存放在结点ls\[1\]中，胜者存放在ls\[0\]中。

![img][img 13]

图是当b3变为13时，败者树的重构图。

注意，\*\*败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。\*\*对照Fig. 3来看，b3与结点ls\[4\]的原值比较，ls\[4\]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls\[4\]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。

由上可知，**败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。**

算法的步骤是：每次从k个组中的首元素中选一个最小的数，加入到新组，这样每次都要比较k-1次，故

算法复杂度为O((n-1)\*(k-1))，而如果使用败者树，可以在O(logk)的复杂度下得到最小的数，算法复杂

度将为O((n-1)\*logk)， 对于外部排序这种数据量超大的排序来说，这是一个不小的提高。

#### 败者树的建立与调整 ####

![img][img 14]

![img][img 15]

#### 败者树的java代码 ####

package algorithm.sort.losertreeSort;
     
    import java.awt.Adjustable;
    import java.util.ArrayList;
    import java.util.Arrays;
    /* */
    import java.util.Iterator;
    /** * @author xusy * */
    import java.util.List;
    public class LoserTree { 
    	
    	//数据源，为叶子节点提供数据，iterator里的是有序的数据，从小到大
    	private Iterator<Integer>[] data;
    	
    	//总共有几个数据源
    	private int size;
    	
    	//叶子节点，数据源中具体的数据,一对一
    	private Integer[] leaves;
    	
    	//非叶子节点,记录叶子节点的下标, 根据节点的值可以定位到叶子节点所指向的数据（就是图里画的败者树）
    	//nodes[0]为最小值的索引
    	private int[] nodes;
    	
    	/**根据data，构建败者树 * @param data iterator里的是有序的数据，从小到大 */
    	public LoserTree(List<Iterator<Integer>> data){ 
    		//因为iterator不能变成迭代器数组，只能变成迭代器列表
    		this.data=data.toArray(new Iterator[0]);
    		size=data.size();
    		leaves=new Integer[size];
    		nodes=new int[size];
    		
    		//为叶子节点，leaves数组赋值
    		for(int i=0;i<size;i++){ 
    			setLeavesValueFromData(i);
    		}
    		
    		//找到叶子节点中最小值的下标
    		int winner=0;
    		for(int i=1;i<size;i++){ 
    			//如果i位元素比winner位元素小
    			if(compareLeavesByIndex(i, winner)){ 
    				winner=i;
    			}
    		}
    		
    		// 非叶子节点全部初始化为最小值对应的叶子节点下标
            Arrays.fill(nodes, winner);
    		
            //从后向前依次调整非叶子节点
            for(int i=size-1;i>=0;i--){ 
            	adjust(i);
            }
    		
    	}
    	
    	/**根据数据源data，设置leaves[i]的值，如果对应的data没有值了，就设置null * @param i 位置 */
    	public void setLeavesValueFromData(int i){ 
    		Iterator<Integer> iterator=data[i];
    		if(iterator.hasNext()){ 
    			leaves[i]=iterator.next();
    		}
    		else{ 
    			leaves[i]=null;
    		}		
    	}
    	
    	/**比较leaves数组中位置为index1的元素是否小于index2的元素（因为是要得到小的） * @param index1 * @param index2 * @return */
    	public boolean compareLeavesByIndex(int index1,int index2){ 
    		Integer value1=leaves[index1];
    		Integer value2=leaves[index2];
    		if(value1==null){ 
    			return false;
    		}
    		if(value2==null){ 
    			return true;
    		}
    		//当叶节点数据相等时比较分支索引是为了实现排序算法的稳定性
    		if(value1==value2){ 
    			return index1<index2;
    		}
    		if(value1<value2){ 
    			return true;
    		}
    		else{ 
    			return false;
    		}
    		
    	}
    	
    	
    	/**调整第index个叶子节点的值，在非叶子节点nodes（败者树）中的位置，最后nodes[0]为最小的节点 * 具体调整过程为: 叶子节点和父节点比较, 败者（较大值）留在父节点位置, 胜者（较小值）继续和祖父节点比较，直至最终 * @param index */
    	public void adjust(int index){ 
    		int parent=(index+size)/2;
    		//直到parent变成0
    		while (parent>0) { 
    			//如果父节点小于当前值，败者为当前值，败者留在父亲节点，index变成父亲节点的值，相当于父亲节点与祖父节点继续比较
    			//如果父节点大于当前值，败者为父节点，父节点不变，继续与祖父节点比较
    			if(compareLeavesByIndex(nodes[parent], index)){ 
    				int temp=nodes[parent];
    				nodes[parent]=index;
    				index=temp;				
    			}
    			//祖父节点的位置
    			parent=parent/2;
    			//一套流程下来，index成为胜者，小的
    			//parent放置着败者，大的
    			//parent最后成为下一个比较的节点（祖父节点）
    		}
    		//跳出循环后，index成为最小的节点
    		nodes[0]=index;		
    	}
    	
    	
    	/**返回败者树中data，经过败者树，多路归并排序后的list * @return */
    	public List<Integer> mergeSort(){ 
    		List<Integer> list=new ArrayList<>();
    		Integer smallest=null;
    		while (true) { 
    			//得到最小值
    			smallest=leaves[nodes[0]];
    			if(smallest==null){ 
    				break;
    			}			
    			list.add(smallest);
    			//由于leaves数组中的最小值，索引为nodes[0]的元素被拿走了，所以要重新读入一个
    			setLeavesValueFromData(nodes[0]);
    			// 根据新插入的叶子节点重新调整树
    			adjust(nodes[0]); 
    		}		
    		return list;
    	}
    	
    }

测试

package algorithm.sort.losertreeSort;
     
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Iterator;
    import java.util.List;
     
    public class Main { 
    	
    	public static void main(String[] args) { 
    		//int[][] testTable = { {1,2,3,0},{1,2,3,4},{1,2567678,3,4,6767,45,12,345,3435,34,66666},
    		//{1,1,1,3,3,4,3,2,4,2},{1,6,2,7,1}};
     
    		List<Iterator<Integer>> list=new ArrayList<>();
    		list.add(createRandomIntArray(-100,100,50));
    		list.add(createRandomIntArray(-100,100,40));
    		list.add(createRandomIntArray(-100,100,50));
    		list.add(createRandomIntArray(-100,100,50));	
    		test(list);
    	}
    		 
    	private static void test(List<Iterator<Integer>> ito) { 		
    		//开始时打印数组
    		long begin = System.currentTimeMillis();
    		LoserTree tree=new LoserTree(ito);
    		List<Integer> result=tree.mergeSort();
    		long end = System.currentTimeMillis();	
    		
    		//System.out.println(ito + ": rtn=" +rtn);
    		for (int i = 0; i < result.size(); i++) { 
    		    System.out.print(result.get(i)+" ");
    		}//打印结果几数组
    		
    		System.out.println();
    		System.out.println("耗时：" + (end - begin) + "ms");
    		System.out.println("-------------------");
    		System.out.println("-------------------");
    	}
    	public static Iterator<Integer> createRandomIntArray(int min,int max,int length){ 
    		List<Integer> result=new ArrayList<>(length);
    		for(int i=0;i<length;i++){ 
    			double rand=Math.random();
    			result.add((int)(min+(max-min)*rand));
    		}
    		Collections.sort(result);
    		return result.iterator();
    	}
     
    }

#### 败者树的效率 ####

败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够在log(n)的时间内找到最值。（n为多路归并的路数）

设，总共有k组，总共n个数据,每组n/k个

一开始对每组进行排序的时间是 k\*log(n/k)*n/k=n*log(n/k)

进行败者树归并排序的时间为n\*log(k)

**总共时间为n\*(log(n/k)+log(k))=n\*log(n) 也就是最好的速度,速度为O(n\*log(n))**

**所需的空间为O(k)**

[img]: /images/20221120/dfa43d06f8914b819af8e85db308d9a6.png
[img 1]: /images/20221120/ddecd885f8064060b865c1fb30897ad7.png
[img 2]: /images/20221120/fa7b24d58e9b4c538110755a9494eb77.png
[img 3]: /images/20221120/5c59ab0dfd7d4da691e7517aca6cc44b.png
[img 4]: /images/20221120/b21fa8ee3dff4abd89a1c57e7e2280bd.png
[img 5]: /images/20221120/d066d9bf2cbd41eea81056f2b92c7d1e.png
[img 6]: /images/20221120/ef9c14e21ea74610998a19c65933d2b9.png
[c33402a34dcb6815f05cecbd22945674.gif]: /images/20221120/4a6a5fd0b8ea40a5bf59069394ebacdd.png
[img 7]: /images/20221120/7359874a8e724e598360990197d0a0f0.png
[img 8]: /images/20221120/9cc8e0557bcc40818d6d6e021198621a.png
[img 9]: /images/20221120/7bf95f90695c4146ab0508eafb816fb8.png
[img 10]: /images/20221120/f48d2ab0c30746769bc78ff0193c3781.png
[img 11]: /images/20221120/da628652e81a464aaa1f6db61fa22228.png
[img 12]: /images/20221120/857bbcd3a8104d1a9c86b721ed0b56f0.png
[img 13]: /images/20221120/7b8bdf54ccba470b8f4dabd8dfc7489b.png
[img 14]: /images/20221120/6630a45e9bc9402489eda93b76c15a88.png
[img 15]: /images/20221120/dc5bcc3f94414a64a4fae538e005d3a8.png