C语言排序算法之选择排序(直接选择排序,堆排序)

C语言排序算法之选择排序

选择排序概述

选择排序是一种简单直观的排序算法，其基本思想是：每一趟从数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列最后，直到全部数据元素排完为止。

选择排序算法的时间复杂度为O(n^2)，在数据规模较小时效率较高，但是在数据规模较大时效率较低。

选择排序示例

以下是一个使用选择排序算法对数组进行排序的示例：

#include <stdio.h>

void selection_sort(int arr[], int n)
{
    int i, j, min_idx, temp;

    for (i = 0; i < n - 1; i++)
    {
        min_idx = i;

        //找出剩余未排序元素中最小的一个
        for (j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }

        //将找到的最小元素放到已排序序列的末尾
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main(void)
{
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

输出结果为：

排序后的数组：
11 12 22 25 64 

堆排序概述

堆排序是利用堆这种数据结构设计的一种排序算法。其中堆是一个近似完全二叉树的结构，并同时满足堆特性：即父节点的键值总是大于或小于其子节点的键值。

堆排序算法的时间复杂度为O(nlogn)，是效率较高的一种排序算法。

堆排序示例

以下是一个使用堆排序算法对数组进行排序的示例：

#include <stdio.h>

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2 * i + 1; 
    int r = 2 * i + 2; 

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

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

    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

void heap_sort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i >= 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);
    }
}

int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    heap_sort(arr, n);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

输出结果为：

排序后的数组：
5 6 7 11 12 13 

以上就是选择排序和堆排序的完整攻略。