美文网首页
数据结构与算法-选择排序&堆排序

数据结构与算法-选择排序&堆排序

作者: 星空下奔跑 | 来源:发表于2018-03-30 23:05 被阅读0次

简单选择排序

排序思想:每次选出最小值与对应位置记录交换,直至序列有序。

void SelectSort(Sqlist &L){
    for(int i=1;i<L.length;i++){
        min=selmin(L,i);
        L.r[i]<->L.r[min];
    }//for
}

Java实现:

private void selectSort(int[] array) {
        int len=array.length;
        for (int i = 0; i < len; i++) {
            int target=array[i];
            int index=i;
            for (int j = i + 1; j < len; j++) {
                if (target > array[j]) {
                    target=array[j];
                    index=j;
                }
            }
            array[index]=array[i];
            array[i]=target;
        }
        println(array);
    }

堆排序

排序思想:将待排序列看成一个完全二叉树,完全二叉树所有非终端结点均不大于其左右孩子结点的值,反复进行便得到有序的序列。

//小顶堆
void HeapAdjust(Sqlist &L,int n){
    for(int i=2*n;i<L.length;i*=2){
        if(i<L.length&&LT(L.r[i],L.r[i/2]){
            L.r[i]<->L.r[i/2];
        }//if
    }//for
}

void HeapSort(Sqlist &L){
    for(int i=L.length/2;i<L.length;--i){
        HeapAdust(L,i);
}

Java实现:

private void adjust(int[] a,int end) {
        for (int i = end; i > 0; i--) {
            if (a[i] > a[i / 2]) {
                int tmp=a[i];
                a[i] = a[i / 2];
                a[i/2]=tmp;
            }
        }
    }
    private void heapSort(int[] array){

        if (array != null && array.length > 0) {
            adjust(array,array.length-1);
        }

        for (int i = array.length - 1; i > 0; i--) {
            int tmp=array[i];
            array[i] = array[0];
            array[0]=tmp;

            adjust(array,i-1);
        }

        println(testArray);
    }

相关文章

  • 排序算法-堆排序

    参考: Java排序算法(五):堆排序 【算法与数据结构】图说堆排序 【数据结构】排序算法:希尔、归并、快速、堆排...

  • 算法与数据结构(六):堆排序

    title: 算法与数据结构(六):堆排序tags: [算法与数据结构, C语言, 堆排序]date: 2019-...

  • 算法与数据结构路线图

    学习算法与数据结构,深刻理解计算机科学 排序算法:插入、冒泡、选择、希尔、快速、归并、堆排序、计数排序、桶排序、基...

  • 2018-06-30

    排序算法之堆排序 堆排序是利用堆的数据结构而设计的一种排序算法,堆排序是一种选择排序。可以利用数组的特点快速定位制...

  • 排序

    一、选择排序 1.堆排序 定义:堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序可参考http...

  • 堆排序

    预备知识 堆排序 堆排序(heap sort)是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的...

  • 堆排序(swift、oc双语实现)

    预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复...

  • 高效排序算法-堆排序

    预备知识: 堆排序堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复...

  • 【数据结构与算法】堆排序算法回顾

    一.堆排序介绍 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂...

  • 堆排序

    转载:图解排序算法(三)之堆排序 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选...

网友评论

      本文标题:数据结构与算法-选择排序&堆排序

      本文链接:https://www.haomeiwen.com/subject/dlzvcftx.html