排序——选择类排序

清疚 2021-11-05 14:58 248阅读 0赞

## 简单选择排序 ##

> **算法思想：从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，直至序列有序。**
> 
> **时间复杂度分析：**
> 
> **空间复杂度：O(1)**
> 
>  *  **两层循环的执行次数和初始序列无关，外层循环执行n次，内层循环执行n-1次，总执行次数：（n-1+1)(n-1)/2 = n(n-1)/2，即时间复杂度为O(n^2)**

**代码：**

void Select_sort(int arr[],int n)       //选择排序
    {
        int i,j,k,temp;
        for(i=0;i<n;i++)
        {
            k = i;                          //k保存当前无序序列中最小的值，初始为arr[i]
            for(j=i+1;j<n;j++)              //从无序序列中选择出一个最小的值
            {
                if(arr[k]>arr[j])
                {
                    k = j;
                }
            }
            //将当前无序序列最小值与第i个数交换
            temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }

## 堆排序 ##

> **算法介绍：堆是一种数据结构，将堆看成一棵完全二叉树，这棵完全二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值。若父亲大孩子小，则称为大顶堆，反之为小顶堆。**
> 
> **算法思想：以升序为例，将无序序列调整，使之符合堆的完全二叉树定义，则此时根节点的值是整个序列中的最大值，将根节点交换到有序序列的最后，并将完全二叉树中底层最右边的节点赋给根节点后删除该叶子节点；继续进行上述操作，序列有序。**
> 
> **时间复杂度分析：O(nlog2n)**
> 
> **空间复杂度：O(1)**
> 
> **适用场景：适用于关键字数很多的情况，例如从10000个数中选出最小的前10个**
> 
> **优点：最坏也是O(nlog2n)，堆排序的空间复杂度为O(1)是所有时间复杂度为O(nlog2n)的排序中最小的。**

**代码：**

void Sift(int arr[],int low,int high)
    {
        int i = low,j = 2*i;        //下标从1开始,arr[j]是arr[i]的左孩子节点
        int temp = arr[i];
        while(j <= high)
        {
            if(j<high&&arr[j]<arr[j+1])     //防止越界，比较左右孩子的值，若右孩子大，则使j+1，即当前arr[j]为i节点的右孩子
                ++j;
            if(temp<arr[j])         //如果arr[i]<arr[j]，则说明此时不满足堆的完全二叉树定义，交换这两个数
            {
                arr[i] = arr[j];    //①
                i = j;              //修改i,j的值，让i（为j的值）成为双亲节点，j为i（赋值前j）的的左孩子
                j = 2*i;
            }
            else
                break;
        }
        arr[i] = temp;              //②将调整后的值放入最终位置
    }
    void heap_sort(int arr[],int n)
    {
        int i,temp;
        for(i=n/2;i>0;i--)         //建立初始堆
        {
            Sift(arr,i,n);
        }
        for(i=n;i>1;--i)           //进行n-1次循环，完成堆排序
        {
            temp = arr[1];          //将当前序列中最大的（即arr[1]位置上的）与第i个位置上的数交换
            arr[1] = arr[i];        //从后往前将依次有序
            arr[i] = temp;
            Sift(arr,1,i-1);        //将去掉一个关键字的剩余序列进行调整，使之符合堆的定义
        }
    }

## 完整代码： ##

#include <stdio.h>
    #include <stdlib.h>
    void Select_sort(int arr[],int n)       //选择排序
    {
        int i,j,k,temp;
        for(i=0;i<n;i++)
        {
            k = i;                          //k保存当前无序序列中最小的值，初始为arr[i]
            for(j=i+1;j<n;j++)              //从无序序列中选择出一个最小的值
            {
                if(arr[k]>arr[j])
                {
                    k = j;
                }
            }
            //将当前无序序列最小值与第i个数交换
            temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    void Sift(int arr[],int low,int high)
    {
        int i = low,j = 2*i;        //下标从1开始,arr[j]是arr[i]的左孩子节点
        int temp = arr[i];
        while(j <= high)
        {
            if(j<high&&arr[j]<arr[j+1])     //防止越界，比较左右孩子的值，若右孩子大，则使j+1，即当前arr[j]为i节点的右孩子
                ++j;
            if(temp<arr[j])         //如果arr[i]<arr[j]，则说明此时不满足堆的完全二叉树定义，交换这两个数
            {
                arr[i] = arr[j];    //①
                i = j;              //修改i,j的值，让i（为j的值）成为双亲节点，j为i（赋值前j）的的左孩子
                j = 2*i;
            }
            else
                break;
        }
        arr[i] = temp;              //②将调整后的值放入最终位置
    }
    void heap_sort(int arr[],int n)
    {
        int i,temp;
        for(i=n/2;i>0;i--)         //建立初始堆
        {
            Sift(arr,i,n);
        }
        for(i=n;i>1;--i)           //进行n-1次循环，完成堆排序
        {
            temp = arr[1];          //将当前序列中最大的（即arr[1]位置上的）与第i个位置上的数交换
            arr[1] = arr[i];        //从后往前将依次有序
            arr[i] = temp;
            Sift(arr,1,i-1);        //将去掉一个关键字的剩余序列进行调整，使之符合堆的定义
        }
    }
    int main()
    {
        int i;
        int arr[] = {0,56,12,78,34,10,90,23,67,56,43};   //下标从1开始
    //    Select_sort(arr,10);
        heap_sort(arr,10);
        for(i=1;i<=10;i++)
        {
            printf("%d\t",arr[i]);
        }
    }

#include <stdio.h>
    #include <stdlib.h>
    void Select_sort(int arr[],int n)       //选择排序
    {
        int i,j,k,temp;
        for(i=0;i<n;i++)
        {
            k = i;                          //k保存当前无序序列中最小的值，初始为arr[i]
            for(j=i+1;j<n;j++)              //从无序序列中选择出一个最小的值
            {
                if(arr[k]>arr[j])
                {
                    k = j;
                }
            }
            //将当前无序序列最小值与第i个数交换
            temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    void Sift(int arr[],int low,int high)
    {
        int i = low,j = 2*i+1;        //下标从1开始,arr[j]是arr[i]的左孩子节点
        int temp = arr[i];
        while(j <= high)
        {
            if(j<high&&arr[j]<arr[j+1])     //防止越界，比较左右孩子的值，若右孩子大，则使j+1，即当前arr[j]为i节点的右孩子
                ++j;
            if(temp<arr[j])         //如果arr[i]<arr[j]，则说明此时不满足堆的完全二叉树定义，交换这两个数
            {
                arr[i] = arr[j];    //①
                i = j;              //修改i,j的值，让i（为j的值）成为双亲节点，j为i（赋值前j）的的左孩子
                j = 2*i+1;
            }
            else
                break;
        }
        arr[i] = temp;              //②将调整后的值放入最终位置
    }
    void heap_sort(int arr[],int n)
    {
        int i,temp;
        for(i=n/2-1;i>=0;i--)         //建立初始堆
        {
            Sift(arr,i,n);
        }
        for(i=n-1;i>=1;--i)           //进行n-1次循环，完成堆排序
        {
            temp = arr[0];          //将当前序列中最大的（即arr[1]位置上的）与第i个位置上的数交换
            arr[0] = arr[i];        //从后往前将依次有序
            arr[i] = temp;
            Sift(arr,0,i-1);        //将去掉一个关键字的剩余序列进行调整，使之符合堆的定义
        }
    }
    int main()
    {
        int i;
        int arr[] = {56,12,78,34,10,90,23,67,56,43};    //下标从0开始
    //    Select_sort(arr,10);
        heap_sort(arr,10);
        for(i=0;i<10;i++)
        {
            printf("%d\t",arr[i]);
        }
    }