数据结构与算法：选择排序

选择排序

每次从乱序区中选择一个最小的排序
分为简单选择排序和堆排序

简单选择排序

每次遍历都找到一个最小的元素，放在乱序区的第一个位置。

void SelectSort(int arr[], int n)
{
    for(int i=0;i<n;i++){
        int Min=i;
        for(int j=i+1;j<n;j++){
            if(arr[j]<arr[Min]){
                Min=j;
            }
        }
        swap(arr[i],arr[Min]);
    }
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，时间复杂度均为O(nlogn)，是不稳定排序。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
一个节点下标为x，左孩子为2x+1，有孩子为2x+2（这是对于数组下标为0的数组，若下标为1，则左孩子为2x，有孩子为2x+1，选用不同的起始下标实现略有不同）。

堆排序的过程：每次都弹出堆顶的元素，然后将剩余的元素调整成堆，再弹出堆顶元素，再调整，直到没有元素为止，就完成了排序.
堆排序的初始化：可以把初始数组看作一棵完全二叉树，对这棵二叉树进行调整使其变成大顶堆或小顶堆。
调整方法：将叶子节点顶替根节点，自上而下进行调整，然后再自上而下调整。

以下代码将一个数组调整为一个大顶堆，其中arr表示待排数组，n表示数组长度，i为要调整的节点。

void Heapify(int* arr,int n,int i)
{
   int largest = i;
   int left = 2 * i + 1;
   int right = 2 * i + 2;

   while (true) {
       if (left < n && arr[left] > arr[largest]) {
           largest = left;
       }

       if (right < n && arr[right] > arr[largest]) {
           largest = right;
       }

       if (largest == i) {
           break;
       }

       swap(arr[i], arr[largest]);
       i = largest;
       left = 2 * i + 1;
       right = 2 * i + 2;
   }
}

若要把数组调整为小顶堆，只需要改变比较策略就可以实现,把下面代码替换判断逻辑就可以得到一个小顶堆：

if(left < n && arr[left] < arr[largest]){
    largest = left;
}
if(right < n && arr[right] < arr[largest]){
    largest = right;
}

利用大顶堆对数组进行排序：

void HeapSort(int* arr, int n)
{
    //将数组初始化为一个大顶堆
    for(int i=n/2-1;i>=0;i--){
        Heapify(arr,n,i);
    }

    //使用一个临时变量堆数组长度进行标记，也可以将for循环改为从后向前遍历，就可以直接使用i代替数组长度
    int m=n-1;
    for(int i=0;i<n;i++){
        cout << arr[0] << " ";
        swap(arr[0],arr[m]);
        Heapify(arr,m,0);
        m--;
    }
}

使用逆序遍历代码

for(int i=n-1;i>=0;i--){
    ocut << arr[0] << " ";
    swap(arr[0],arr[i]);
    Heapify(arr,i,0);
}

• 本文作者： KongXinQing
• 本文链接： https://13114987559.github.io/2023/09/20/note/数据结构与算法-选择排序/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！