0


堆/选择/插入/希尔排序

堆排序

堆排序是利用树的结构进行的,常常用于选出最大/最小的N个数,效率很高

树可以用链表表示,也可以用数组表示,这里我们先用数组来实现堆排序

** 首先我们要先把一个数组构造成一个堆,只有成为了一个堆之后才能进行向上/向下调整**

将问题一个一个细分,因为一个乱的数如果直接从根开始进行向上/向下进行排序的话肯定是不行的,所以我们可以从最后一个非叶子节点开始往前进行向上调整,而这里为什么要从最后一个非叶子节点开始呢?因为单个叶子节点不需要调整,也无法进行调整,如图,第一个非叶子节点就是3,从而对3和6进行调整,一直到1位置为止,这时候就已经把数组排成了一个堆了。

而如何进行向上/向下调整呢?

对于向下调整而言,调成一个小堆我,就是父亲节点一定小于孩子节点。

而第一个问题就是如何找到左右孩子中较小的那一个呢?为了代码的简洁,可以直接找到左孩子,而右孩子就是左孩子+1,child=parent2+1,*以下为代码实现:

//向下调整(小堆)
void AdjustDown(int *a, int n, int parent) {
    int child = parent * 2 + 1;//左孩子,右孩子为左孩子+1
    while (child < n) {
        //child+1不能大于n,然后再选出左右孩子中小的那一个
        if (child + 1 < n && a[child + 1] < a[child]) {
            child++;//拿到右孩子
        }
        if (a[child] < a[parent]) {
            //如果孩子节点小于父亲节点,则进行交换
            Swap(&a[child], &a[parent]);
            //父亲和孩子继续交换,继续向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

交换函数Swap:

void Swap(int *child, int *parent) {
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

现在就可以将数组构造成堆了,代码实现:

void CreateHeap(int *a, int n) {
    //找到最后一个非叶子节点的节点
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
}

总代码:

#include <stdio.h>

void Swap(int *child, int *parent) {
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

//堆排序

//向下调整(小堆)
void AdjustDown(int *a, int n, int parent) {
    int child = parent * 2 + 1;//左孩子,右孩子为左孩子+1
    while (child < n) {
        //child+1不能大于n,然后再选出左右孩子中小的那一个
        if (child + 1 < n && a[child + 1] < a[child]) {
            child++;//拿到右孩子
        }
        if (a[child] < a[parent]) {
            //如果孩子节点小于父亲节点,则进行交换
            Swap(&a[child], &a[parent]);
            //父亲和孩子继续交换,继续向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

//建堆
void CreateHeap(int *a, int n) {
    //找到最后一个非叶子节点的节点
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
}

int main(void) {
    int arr[] = { 3, 8, 9, 18, 7, 5, 10, 87, 21, 99, 76, 100 };
    CreateHeap(arr, 12);
    for (int i = 0; i < 12; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果

画出树的结构为:

可以看出,这个数组已经变成一个小堆了。

接下来就可以进行堆排序了,那么如何进行堆排序呢?

如果要排升序,就建立一个大堆,选出来最大的数,然后最后一个数和第一个数交换,再把最后一个数不看作堆里的数1,进行向下调整即可

代码实现:

void HeapSort(int *a, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    int end = n - 1;
    while (end >= 0) {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

运行结果:

这样就排序成功了。

总代码:

#include <stdio.h>

void Swap(int *child, int *parent) {
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

//堆排序

//向下调整(小堆)
void AdjustDown(int *a, int n, int parent) {
    int child = parent * 2 + 1;//左孩子,右孩子为左孩子+1
    while (child < n) {
        //child+1不能大于n,然后再选出左右孩子中小的那一个
        if (child + 1 < n && a[child + 1] > a[child]) {
            child++;//拿到右孩子
        }
        if (a[child] > a[parent]) {
            //如果孩子节点小于父亲节点,则进行交换
            Swap(&a[child], &a[parent]);
            //父亲和孩子继续交换,继续向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

//建堆
void CreateHeap(int *a, int n) {
    //找到最后一个非叶子节点的节点
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
}

//堆排序(大堆的条件下),进行升序
void HeapSort(int *a, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    int end = n - 1;
    while (end >= 0) {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

int main(void) {
    int arr[] = { 3, 8, 9, 18, 7, 5, 10, 87, 21, 99, 76, 100 };
    HeapSort(arr, 12);
    for (int i = 0; i < 12; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

选择排序

选择排序,顾名思义就是选择某个数进行排序,这里我们可以遍历一次数据,找到最小值和最大值,将最小值放在第一个位置,最大值放在最后一个位置,然后再将区间缩小,一次类推,但这里会有一个bug,那就是当第一个数就是最大值的时候是无法正确进行排序的。

这时候就需要进行修正

解决方法就是加一个判断,如果begin==maxi,那么maxi=mini

代码实现

#include <stdio.h>

void Swap(int* child, int* parent) {
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (end > begin) {
        int mini = begin, maxi = begin;
        for (int i = begin; i <= end; i++) {
            if (a[i] < a[mini]) {
                mini = i;
            }
            if (a[i] > a[maxi]) {
                maxi = i;
            }
        }
        Swap(&a[begin], &a[mini]);
        if (begin == maxi) {
            maxi = mini;
        }
        Swap(&a[end], &a[maxi]);
        end--;
        begin++;
    }
}

int main(void) {
    int arr[] = { 100, 8, 6, 89, 26, 83, 52, 12, 90, 0 };
    SelectSort(&arr, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

直接插入排序

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一

个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

实际中我们玩扑克牌时,就用了插入排序的思想

从要插入的位置开始,设这个位置为end,用该位置的数值从后往前比较,如果能找到比它小的数,则a[end+1]=x;

代码实现:

#include <stdio.h>

void InsertSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int x = a[end + 1];
        while (end >= 0) {
            if (a[end] > x) {
                a[end + 1] = a[end];
                end--;
            } else {
                break;
            }
        }
        a[end + 1] = x;
    }
}

int main(void) {
    int arr[] = {100, 520, 123, 98, 56, 23, 87, 12, 66, 99};
    InsertSort(arr, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果:

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个

组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工

作。当到达=1时,所有记录在统一组内排好序。

希尔排序其实就是在直接插入排序的基础上进行了改良,直接插入排序的快慢取决于数组是否接近有序,是的话则很快,反之较慢,而希尔排序就是先将数组接近有序,再进行直接插入排序

如图所示,当gap等于2的时候,4 2 5 8 5为一组,1 3 9 6 7为一组,对这两组数据进行排序,可以使得数组的数据接近有序,当gap越大,越接近无序,反之则接近有序,当gap=1的时候,就是直接插入排序了,又因为gap也是数据的组数,所以可以操作gap来进行排序

代码实现:

#include <stdio.h>

void ShellSort(int *a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int x = a[end + gap];
            while (end >= 0) {
                if (a[end] > x) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = x;
        }
    }
}

int main(void) {
    int arr[] = {100, 520, 0, 78, 66, 99, 123, 97, 12, 2};
    ShellSort(arr, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

本文转载自: https://blog.csdn.net/AkieMo/article/details/127586074
版权归原作者 AkieMo 所有, 如有侵权,请联系我们删除。

“堆/选择/插入/希尔排序”的评论:

还没有评论