选择排序和堆排序

朴灿烈づ我的快乐病毒、 2022-06-13 08:07 251阅读 0赞

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法，选择排序是一种时间复杂度为O(N^2)的算法

![这里写图片描述][SouthEast]

void SelectSort(int*arr, int n)
    {
    
    
        int left = 0;
        int right = n;
        int i = left;
        while (left < right)
        {
            int min = left;
            int max = right - 1;
            for (i=left; i < right; ++i)
            {
                if (arr[i] < arr[min])
                {
                    min = i;
                }
               if (arr[i]>arr[max])
                {
                    max = i;
                }
            }
            swap(arr[left], arr[min]);
            if (max == left)
            {
                max = min;
            }
            swap(arr[--right], arr[max]);
            ++left;
        }
    }

堆排序  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
首先将堆建好之后，在让最后一个数和第一个数交换，交换之后，把之前最后一个数不在当作数组中的数，将第一个数到最后一个数的前一个数进行向下调整算法。直到调整到最后一个数变为第一个数的时候不再需要调整，堆排序的升序也已经排列好了。

void AdjustDown(int *arr, int root,int n)
    {
        int parent = root;
        int child = parent * 2 + 1;
        while (child<n)
        {
            if (child + 1 < n&&arr[child] < arr[child + 1])
            {
                ++child;
            }
            if (arr[child] > arr[parent])
            {
                swap(arr[child], arr[parent]);
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }
    void HeapSort(int *arr, int n)
    {
        int *p = arr;
        for (int i = (n - 2) / 2; i >= 0; --i)
        {
            AdjustDown(arr, i,n);
        }
        int end = n - 1;
        while (end > 0)
        {
            swap(arr[0], arr[end]);
            AdjustDown(arr, 0, end);
            --end;
        }
    }

[SouthEast]: /images/20220613/d40e919fe17a40108b812d772f40a1b0.png
[SouthEast 1]: /images/20220613/1209aaa222b04d52814cc39f705b5958.png
[SouthEast 2]: /images/20220613/2702eb8844e6420e8622a0f6714520b6.png