直接选择排序
选择排序的原理:将数组分为有序区,无序区。初始有序区元素为0,整个数组为无序区。每次遍历从无序区中选出一个最小(或最大)的元素,放在有序区的最后,每一次遍历排序过程都是有序区元素个数增加,无序区元素个数减少的过程,直到无序区元素个数位0。
直接选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的数组进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
/** * 直接选择排序 * * @param ts */ public static <T extends Comparable<? super T>> void selectSort(T[] ts) { int length = ts.length; int min; // 无序区最小元素位置 T tem; // 辅助空间 for (int i = 0; i < length - 1; i++) { min = i;// 默认取无序区第一个元素为最小值 // 循环遍历无序区,查找到无序区最小元素 for (int y = i + 1; y < length; y++) if (ts[min].compareTo(ts[y]) > 0) min = y; if (i == min) continue; // 把无序区最小元素,插入到有序区末尾 tem = ts[i]; ts[i] = ts[min]; ts[min] = tem; } }
1. 时间复杂度:O(n^2)
直接选择排序耗时的操作有:比较 + 交换赋值。时间复杂度如下:
1) 最好情况:序列是升序排列,在这种情况下,需要进行的比较操作需n(n-1)/2次。交换赋
值操作为0次。即O(n^2)
2) 最坏情况:序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。交换赋值n-1
次(交换次数比冒泡排序少多了),选择排序的效率比较稳定,最好情况和最坏情况差
不多。即O(n^2)
3) 渐进时间复杂度(平均时间复杂度):O(n^2)
2. 空间复杂度:O(1)
3. 稳定性
直接选择排序是不稳定的。
因为每次遍历比较完后会使用本次遍历选择的最小元素和无序区的第一个元素交换位置,所以如果无序区第一个元素后面有相同元素的,则可能会改变相同元素的相对顺序。
堆排序
堆是一颗被完全填满的二叉树,有可能的例外是在底层,底层上的元素从左到右填入。这样的树称为完全二叉树。
堆的性质:
比如我们想找出最大元,因为最大元在根上,而且任意子树也是一个堆,那么任意节点就应该大于它的所有后裔。
一个重要的观察发现,因为完全二叉树这么有规律,所以可以用一个数组表表示而不需要使用链, 对于数组中任意位置的i上元素,其左儿子在位置[2i+1]上,右儿子在左儿子后的[(2i+1)+1]位置,它的父亲则在[i-1/2] 上,注意[0]位置是根。如下图
当新增一个元素24时,我们在下一个可用位置插入元素24。因为24>10,所以破坏了堆的性质,解决:把24朝着根的方向上移,直到24放入正确的位置。 如下图,这里称之为上虑。(堆排序,不会用到)
当删除最大元时。由于现在堆少了一个元素,因此堆中最后一个元素必须移动到堆中某个地方。我们的做法是将最后一个元素放在删除的最大元位置。然后向下插入到最大儿子路径的一个正确的位置。这里称之为下虑。堆排中会递归删除最大元。
根据上面堆的性质,每次删除最大元后,堆缩小1,因此,堆中最后的单元可以用来存放刚刚删去的元素。
下图中先进行,先把数组初始化成最大堆,然后递归删除最大元(最左面那根),每次删除的最大元放在数组的length-1,length-2,length-3......
在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作:
- 最大堆调整:将堆的末端子节点作调整,使得子节点永远小于父节点
- 创建最大堆:将堆所有数据重新排序
- 堆排序:移除位在第一个数据的根节点,并做最大堆调整的递归运算
/** * 堆排序 * * @param ts */ public static <T extends Comparable<? super T>> void heapSort(T[] ts) { // 通过下虑,将数组初始化成一个堆。 for (int length = ts.length, i = length / 2 - 1; i >= 0; i--) percDown(ts, i, length); // 对具有堆性质的数组排序 for (int len = ts.length - 1; len >= 0; len--) { // 将最大元[0]删除,即放到堆尾,堆尾元素放到最大元位置 swap(ts, len); // 对最大元位置元素 下虑 percDown(ts, 0, len); } } /** * 下虑 找出最大元 * * @param ts * @param index * @param length */ private static <T extends Comparable<? super T>> void percDown(T[] ts, int i, int length) { T temp = ts[i];// 待调整最大元位置元素 for (int child = leftChild(i); child < length; i = child, child = leftChild(i)) { // 判断有右儿子&&右儿子>左儿子 if (child + 1 != length && ts[child + 1].compareTo(ts[child]) > 0) child++; // 最大儿子跟父比较 if (temp.compareTo(ts[child]) < 0) ts[i] = ts[child]; else break; } ts[i] = temp;// 放到正确位置 } /** * 堆尾、堆首互换 * * @param ts * @param index */ private static <T extends Comparable<? super T>> void swap(T[] ts, int index) { T temp = ts[index]; ts[index] = ts[0]; ts[0] = temp; } /** * 左儿子位置 * * @param i * @return */ private static int leftChild(int i) { return i * 2 + 1; }
1. 时间复杂度:O(nlog2n)
首先把数组,初始化成一个堆。这个阶段花费O(N)的时间,可以忽略。
然后执行N次的删除最大元,每次最大元删除重排花费的时间为O(logn),因此
最差时间复杂:O(nlogn)
最优时间复杂:O(nlogn)
平均时间复杂:O(nlogn)
2. 空间复杂度:O(1)
3. 稳定性
堆排序是不稳定的
因为在初始化堆时,相同元素可能被分配到不同的父节点下,所以在反复调整堆过程中,可能会改变相同元素的相对顺序
简单性能测试
/** * 简单的性能测试 * * @param args */ public static void main(String[] args) { int num = 100000; Integer[] inters = new Integer[num]; Random inter = new Random(); for (int i = 0; i < num; i++) { inters[i] = inter.nextInt(num); } long tims = System.currentTimeMillis(); // heapSort(inters); selectSort(inters); tims -= System.currentTimeMillis(); System.err.println(tims * -1); }
排序方法\数组大小 | 1000 | 5000 | 10000 | 50000 | 10w | 100w | 1000w |
选择排序 | 29 | 45 | 104 | 2.3s | 10s | 太长 | 太长 |
堆排序 | 3 | 15 | 20 | 28 | 40 | 600 | 10s |
相关推荐
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
堆排序 java实现
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
Java实现堆排序.rar
堆排序算法Java实现
用Java实现的堆排序算法,二叉树转换为堆,然后排序
java 实现二叉排序树
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
八大排序java实现版本,直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔插入排序、快速排序 、堆排序、2-路归并排序 、基数排序,并有时间比较,博文...
Java 写得最大堆排序代码,给大家参考下,自己刚写的。
heapSort 方法实现了堆排序算法。它使用以下步骤进行排序: 构建最大堆:从非叶子节点开始向上调整,使得父节点的值大于等于子节点的值。 排序阶段:依次从堆顶(最大值)开始,将堆顶元素与末尾元素交换,然后...
代码实现了二元选择排序与堆排序
堆排序算法 java
用java语言实现冒泡排序、插入排序、堆排序、快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。