排序算法(二)：选择排序(直接选择排序、堆排序)

野性酷女 2022-06-01 06:54 282阅读 0赞

### **一、直接选择排序** ###

#### **1.算法思想：** ####

每一趟(第i趟，i=0,1，…，n-2)在后面n-i个待排序的数据元素集合中选出关键码最 小的数据元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素集合中只剩下1 个元素，排序结束。

#### **2.具体算法描述** ####

*  在元素集合array\[i\]–array\[n-1\]中选择关键码最小的数据元素；
 *  若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素交换
 *  在剩余的array\[i+1\]–array\[n-1\]集合中，重复12步骤，直到集合剩余1个元素

// 最差时间复杂度 ---- O(n^2)
    // 最优时间复杂度 ---- O(n^2)
    // 平均时间复杂度 ---- O(n^2)
    // 空间复杂度 ------ O(1)
    // 稳定性 ------------ 不稳定
    
    void SeleteSort(int* arr, int size)
    {
        int i = 0;
        for (i = 0; i < size - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < size; j++)
            {
                if (arr[index]>arr[j])
                {
                    index = j;
                }
            }
            if (index != i)
            {
                swap(arr[index], arr[i]);
            }
        }
    }

### **二、堆排序** ###

#### **1.算法思想** ####

堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆为例，其中父结点的值总是大于它的孩子节点。

#### **2.具体算法描述** ####

升序排列需要创建大堆，否则创建小堆。

*  由输入的无序数组构造一个最大堆，作为初始的无序区
 *  把堆顶元素（最大值）和堆尾元素互换
 *  把堆（无序区）的大小减小1，并用向下调整算法从新的堆顶元素开始进行堆调整
 *  重复步骤2，直到堆的大小为1

// 最差时间复杂度 ---- O(nlogn)
    // 最优时间复杂度 ---- O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 空间复杂度 ------ O(1)
    // 稳定性 ------------ 不稳定
    
    void AdjustDown(int *arr, int n, int size)
    {
        size_t parent = n;
        size_t child = 2 * n + 1;
        while (child < size)
        {
            if ((child + 1 < size) && (arr[child + 1] > arr[child]))
            {
                ++child;
            }
            if (arr[child]>arr[parent])
            {
                swap(arr[parent], arr[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    void HeapSort(int *arr, size_t n)
    {
        //建堆
        int i = 0;
        for (i = (n - 2) / 2; i >= 0; --i)
        {
            AdjustDown(arr, i, n);
        }
        //选数据
        for (i = n - 1; i > 0; --i)
        {
            swap(arr[0], arr[i]);
            AdjustDown(arr, 0, i);
        }
    }

#### 测试代码： ####

void Test()
    {
        int arr1[10] = { 2, 0, 4, 5, 7, 1, 9, 3, 8, 6 };
        SeleteSort(arr1, 10);
        cout << "直接选择排序结果：";
        for (int i = 0; i < 10; i++)
        {
            cout << arr1[i] << " ";
        }
        cout << endl;
    
        int arr2[10] = { 2, 0, 4, 5, 7, 1, 9, 3, 8, 6 };
        HeapSort(arr2, 10);
        cout << "堆排序结果：";
        for (int i = 0; i < 10; i++)
        {
            cout << arr2[i] << " ";
        }
        cout << endl;
    
    }
    
    int main()
    {
        Test();
        system("pause");
        return 0;
    }

#### 运行结果： ####

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

[SouthEast]: /images/20220601/b17cab91c2324da2bb8900b577ed46c1.png