数据结构（堆排序和归并排序）

超、凢脫俗 2022-06-05 12:49 188阅读 0赞

**堆排序**  
在直接选择排序中，顺序表是一个线性结构，要从有n个记录的顺序表中选择出一个最小的记录需要比较n-1 次。如能把待排序的n个记录构成一个完全二叉树结构，则每次选择出一个最大（或最小）的记录比较的次数就是完全二叉树的高度，即log2n次，则排序算法的时间复杂度就是O（nlog2n）。这就是堆排序(Heap Sort)的基本思想。  
堆排序中的堆分为最大堆和最小堆，最大堆的定义如下：  
设顺序表 sqList 中存放了 n 个记录，对于任意的 i(0≤i≤n-1)，如果 2i+1

public void CreateHeap(List<int> list,int low,int high)
            {
                int j = 0;
                int temp = 0;
                int k = 0;
                for (int i = high/2; i >=low; i--)
                {
                    k = i;
                    j = 2*k + 1;//左孩子节点
                    temp = list[i];//比较的关键码
                    while (j<=high)
                    {
                        if (j<high&&j+1<=high&&list[j]<list[j+1])//找出左右孩子节点中关键码最大的孩子节点
                        {
                            j++;
                        }
                        if (temp < list[j])//如果需要交换位置
                        {
                            list[k] = list[j];
                            k = j;
                            j = 2*k + 1;//交换后重新比较以j为根节点的树
                        }
                        else
                        {
                            j = high + 1;
                        }
                    }
                    list[k]=temp;//避免重复赋值
                }
            }
    
            public void HeapSort(List<int> list)
            {
                int temp = 0;
                CreateHeap(list,0,list.Count);//所有的建成一个最大堆
                for (int i =list.Count; i>0;i--)
                {
                    temp = list[0];//堆顶记录
                    list[0] = list[i];
                    list[i] = temp;
                    CreateHeap(list,0,i-1);
                }
            }

堆排序算法是基于完全二叉树的排序方法。把一棵完全二叉树调整为堆，以及每次堆顶记录交换后进行调整的时间复杂度均为O（nlog2n），所以，堆排序算法的时间复杂度为O（nlog2n）。  
**归并排序**  
归并排序(merge Sort)主要是二路归并排序。二路归并排序的基本思想是：将两个有序表合并为一个有序表。  
假设顺序表 sqList 中的 n 个记录为 n 个长度为 1 的有序表，从第 1 个有序表开始，把相邻的两个有序表两两进行合并成一个有序表，得到 n/2 个长度为 2的有序表。如此重复，最后得到一个长度为 n 的有序表。

public void Merge(List<int> list,int len)
            {
                int m = 0;
                int l1 = 0;
                int h1 = 0;
                int l2 = 0;
                int h2 = 0;
                int j = 0;
                int i = 0;
                List<int> temp=new List<int>(list.Count);
                while (l1+len<list.Count)
                {
                    l2 = l1 + len;
                    h1 = l2 - 1;
                    h2 = (l2 + len - 1) < list.Count ? l2 + len - 1 : list.Count - 1;
                    j = l2;
                    i=l1;
                    while (i<=h1&&j<=h2)
                    {
                        if (list[i] <= list[j])
                        {
                            temp[m++] = list[i++];
                        }
                        else
                        {
                            temp[m++] = list[j++];
                        }
                    }
                    while (i<=h1)
                    {
                        temp[m++] = list[i]++;
                    }
                    while (j<=h2)
                    {
                        temp[m++] = list[j++];
                    }
                    l1 = h2 + 1;
                }
                i = l1;
                while (i<list.Count)
                {
                    temp[m++] = list[i++];
                }
                for (int k = 0; k < list.Count; k++)
                {
                    list[k] = temp[k];
                }
            }
    
            public void MergeSort(List<int> list)
            {
                int k = 1;
                while (k<list.Count)
                {
                    Merge(list,k);
                    k *= 2;
                }
            }

二路归并排序的时间复杂度为O（nlog2n）。