这一篇要总计的是挑选排序,冒泡排序和高效排序

1-1、示意图

图片 1

 

壹 、直接选取排序及算法实现

一 、直接采取排序及算法达成

1-1、示意图

图片 2

 

上一篇计算了置换排序的冒泡排序和高速排序。这一篇要总计的是选取排序,选取排序分为直接接纳排序和堆排序,主要从以下几点实行总括。

② 、堆排序及算法达成

堆排序(Heap Sort)
利用堆(一般为大根堆)实行排序的措施。它的主旨境维是:将待排序的因素构造成贰个大根堆。此时,整个系列的最大值正是堆顶的根节点。将它移走(其实正是将它与数组的末尾元素实行置换,此时末尾成分正是最大值),然后将余下的length-三个成分重新协会成2个大根堆,那样就会博得length个因素中的次大值。如此频仍实践,便能赢得3个稳步的队列。

堆是具有下列性质的一心二叉树:各样节点的值都大于或等于其左右亲骨肉节点的值,称为大根堆;种种节点的值都自愧不如或等于其左右儿女节点的值,称为小根堆。

堆排序的最坏时间复杂度为O(n*log2n),平均时间复杂度为O(n*log2n) 
 

 

二 、堆排序及算法实现

堆排序(Heap Sort)
利用堆(一般为大根堆)进行排序的措施。它的为主考虑是:将待排序的因素构造成一个大根堆。此时,整个种类的最大值便是堆顶的根节点。将它移走(其实正是将它与数组的末梢成分举办置换,此时末尾成分正是最大值),然后将多余的length-三个要素重新布局成一个大根堆,那样就会博得length个因素中的次大值。如此频仍实践,便能获取一个静止的队列。

堆是享有下列性质的一心二叉树:每一种节点的值都大于或等于其左右儿女节点的值,称为大根堆;每一个节点的值都低于或等于其左右男女节点的值,称为小根堆。

堆排序的最坏时间复杂度为O(n*log2n),平均时间复杂度为O(n*log2n) 
 

 

2-2、代码

HeapSort.java

public class HeapSort {
    public static void main(String[] args) {
        int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
        System.out.println("************堆排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        heapSort(list);
        display(list);
    }

    /**
     * 堆排序算法
     */
    public static void heapSort(int[] list) {
        // 将无序堆构造成一个大根堆,大根堆有length/2个父节点
        for (int i = list.length / 2 - 1; i >= 0; i--) {
            headAdjust(list, i, list.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换,并且再调整其为大根堆
        for (int i = list.length - 1; i > 0; i--) {
            // 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
            swap(list, 0, i);
            headAdjust(list, 0, i);
        }
    }

    /**
     * 构造大根堆
     */
    public static void headAdjust(int[] list, int parent, int length) {
        // 保存当前父节点
        int temp = list[parent];

        // 得到左孩子节点
        int leftChild = 2 * parent + 1;

        while (leftChild < length) {
            // 如果parent有右孩子,则要判断左孩子是否小于右孩子
            if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
                leftChild++;
            }
            // 父亲节点大于子节点,就不用做交换
            if (temp >= list[leftChild]) {
                break;
            }
            // 将较大子节点的值赋给父亲节点
            list[parent] = list[leftChild];
            // 然后将子节点做为父亲节点
            parent = leftChild;
            // 找到该父亲节点较小的左孩子节点
            leftChild = 2 * parent + 1;
        }
        // 最后将temp值赋给较大的子节点,以形成两值交换
        list[parent] = temp;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int top, int last) {
        int temp = list[top];
        list[top] = list[last];
        list[last] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

图片 3

 

 

迎接转载,但请保留小说原来出处

本文地址:http://www.cnblogs.com/nnngu/p/8282291.html 

壹 、直接选用排序及算法达成

直白选择排序(Straight Select Sort)
是一种简单的排序方法,它的大旨理维是:通过length-1
趟元素之间的可比,从length-i+3个元素中选出最小的因素,并和第i个因素沟通地点。直接选拔排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2
 

下图展现了直接选择排序的历程。

② 、堆排序及算法完结

② 、堆排序及算法达成

上一篇计算了置换排序的冒泡排序和高效排序。这一篇要计算的是选项排序,采纳排序分为直接选用排序和堆排序,重要从以下几点实行总括。

 

壹 、间接采用排序及算法达成

直白选取排序(Straight Select Sort)
是一种不难的排序方法,它的中坚思想是:通过length-1
趟成分之间的比较,从length-i+3个因素中选出最小的因素,并和第i个因素交流位置。直接选拔排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2
 

下图突显了直白选取排序的长河。

2-1、示意图

图一:

图片 4

图二:

图片 5

图三:

图片 6

图四:

图片 7

图五:

图片 8

 

图六:

图片 9

 

1-2、代码

SelectionSort.java

public class SelectionSort {
    public static void main(String[] args) {
        int[] list = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        System.out.println("************直接选择排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        selectionSort(list);
        display(list);
    }

    /**
     * 直接选择排序算法
     */
    public static void selectionSort(int[] list) {
        // 要遍历的次数(length-1次)
        for (int i = 0; i < list.length - 1; i++) {
            // 将当前下标定义为最小值下标
            int min = i;

            // 遍历min后面的数据
            for (int j = i + 1; j <= list.length - 1; j++) {
                // 如果有小于当前最小值的元素,将它的下标赋值给min
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            // 如果min不等于i,说明找到真正的最小值
            if (min != i) {
                swap(list, min, i);
            }
        }
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int min, int i) {
        int temp = list[min];
        list[min] = list[i];
        list[i] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

图片 10

 

1-2、代码

SelectionSort.java

public class SelectionSort {
    public static void main(String[] args) {
        int[] list = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        System.out.println("************直接选择排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        selectionSort(list);
        display(list);
    }

    /**
     * 直接选择排序算法
     */
    public static void selectionSort(int[] list) {
        // 要遍历的次数(length-1次)
        for (int i = 0; i < list.length - 1; i++) {
            // 将当前下标定义为最小值下标
            int min = i;

            // 遍历min后面的数据
            for (int j = i + 1; j <= list.length - 1; j++) {
                // 如果有小于当前最小值的元素,将它的下标赋值给min
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            // 如果min不等于i,说明找到真正的最小值
            if (min != i) {
                swap(list, min, i);
            }
        }
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int min, int i) {
        int temp = list[min];
        list[min] = list[i];
        list[i] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

图片 11

 

2-1、示意图

图一:

图片 12

图二:

图片 13

图三:

图片 14

图四:

图片 15

图五:

图片 16

 

图六:

图片 17

 

2-2、代码

HeapSort.java

public class HeapSort {
    public static void main(String[] args) {
        int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
        System.out.println("************堆排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        heapSort(list);
        display(list);
    }

    /**
     * 堆排序算法
     */
    public static void heapSort(int[] list) {
        // 将无序堆构造成一个大根堆,大根堆有length/2个父节点
        for (int i = list.length / 2 - 1; i >= 0; i--) {
            headAdjust(list, i, list.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换,并且再调整其为大根堆
        for (int i = list.length - 1; i > 0; i--) {
            // 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
            swap(list, 0, i);
            headAdjust(list, 0, i);
        }
    }

    /**
     * 构造大根堆
     */
    public static void headAdjust(int[] list, int parent, int length) {
        // 保存当前父节点
        int temp = list[parent];

        // 得到左孩子节点
        int leftChild = 2 * parent + 1;

        while (leftChild < length) {
            // 如果parent有右孩子,则要判断左孩子是否小于右孩子
            if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
                leftChild++;
            }
            // 父亲节点大于子节点,就不用做交换
            if (temp >= list[leftChild]) {
                break;
            }
            // 将较大子节点的值赋给父亲节点
            list[parent] = list[leftChild];
            // 然后将子节点做为父亲节点
            parent = leftChild;
            // 找到该父亲节点较小的左孩子节点
            leftChild = 2 * parent + 1;
        }
        // 最后将temp值赋给较大的子节点,以形成两值交换
        list[parent] = temp;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int top, int last) {
        int temp = list[top];
        list[top] = list[last];
        list[last] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

图片 18

 

 

欢迎转发,但请保留小说原来出处

本文地址:http://www.cnblogs.com/nnngu/p/8282291.html