排序

选择排序

nkul · 7月9日 · 2020年 · 243次已读

简单选择排序

每次选择一个最小值放到前面即可!

int select_sort(int a[],int n){
    for(int i=0;i

1、每次比较要和最小值比较,即和a[min]比较!!!

2、外层只需要遍历n-1次即可

性质

  • 内部排序
  • 不稳定
  • 空间复杂度:o(1)
  • 时间复杂度:o(n^2)

堆排序

堆数据结构的表示

堆逻辑结构上是一棵树,分为小顶堆和大顶堆。小顶堆即父亲节点小于左右孩子节点!大顶堆即父亲节点大于左右孩子节点!

但是树是可以用顺序结构存储的!

1、为了方便,数组元素比树节点多一个,下标为0的位置不存储

2、对于一个节点放在a[i]位置,则其两个孩子位置为a[2*i]和a[2*i+1]位置

3、对于一个节点放在a[i]位置,则其父亲节点位置为a[i/2]

4、数组存储的树,非叶子节点的下标为(1,n/2),其中n为数组的长度

堆排序过程

1、给定数组[-1,49,38,65,97,76,13,27,49,55,04],此时-1是不参与排序的,是占位符
2、将其逻辑上看成一棵树,则非叶子节点从76往前
3、将76和其两个孩子中较大的交换(该操作成为下坠)
4、若交换了,则交换后的那个节点也要进行下坠操作!

最终数组变成了一个大顶堆,此时交换a[1]和最后一个元素,这样最大值会放到最后面,然后对a[1]进行下坠,又构成了一个大顶堆,进而数组完成排序!

下坠操作

//k为要下坠的元素下标,len是数组长度(因为0逻辑上不算,故a[len]是数组最后一个元素)
void adjust(int a[],int k,int len){
    //备份
    a[0] = a[k];
    //此时,i指向左子树
    for(int i=2*k;i<=len;i*=2){
        //i指向左右孩子中的较大值
        if(ia[i]) break;
        else{
            //交换父亲和孩子,然后将k指向孩子,继续对k进行下注。外层循环i每次乘2,此时i指向的是刚下坠的元素,乘2后继续指向待处理的元素左子树
            a[k] = a[i];
            a[i] = a[0];
            k = i;
        }
    }
}

数组排序

//建堆
void BuildHeap(int a[],int n){
    //对于顺序存储的树,非根节点为下标小于等于n/2;
    for(int i=n/2;i>0;i--){
        adjust(a,i,n);
    }
}
//排序
void heap_sort(int a[],int n){
    BuildHeap(a,n);
    for(int i=n;i>1;i--){
        swap(a[i],a[1]);
        adjust(a,1,i-1);
    }
}

堆排序性质

  • 内部排序
  • 不稳定
  • 空间复杂度:o(1)
  • 时间复杂度:
    • 建堆:o(n)
    • 排序:o(nlogn)

大顶堆的插入删除

1、插入:将数据插入到最后位置,逐渐和父节点比较,一步步上升

2、删除,将最后一个元素对其进行互换,然后对该元素进行下坠操作



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!