-) { // 当前最大堆个数每次递减1 // 把堆顶a[0]元素和当前最大堆的最后一个元素交换 temp = a[0]; a[0] = a[i];
a[i] = temp; createHeap(a, i, 0); // 调整根结点满足最大堆 } } public static void main(String[] args) { int[] test = { 10, 50, 32, 5, 76, 9, 40, 88 }; int n = test.length; heapSort(test); for (int i = 0; i < n; i++) System.out.print(test[i] + " } } ");
三、交换排序 交换排序 冒泡排序:BubbleSort 排序方法 最好时间 冒泡排序 O(n)
平均时间 O(n2)
最坏时间 O(n2)
辅助空间 O(1)
稳定性 稳定
冒泡排序的基本思想是: 设数组 a 中存放了 n 个数据元素, 循环进行 n-1 趟如下的排序 过程:第
1 趟时,依次比较相临两个数据元素 a[i]和 a[i+1](i = 0,1,2,…,n-2),若为逆 序,即 a[i]>a[i+1],则交换两个数据元素,否则不交换,这样数值最大的数据元素将被放 置在 a[n-1]中。第 2 趟时,循环次数减 1,即数据元素个数为 n-1,操作方法和第 1 趟的类 似,这样整个 n 个数据元素集合中数值次大的数据元素将被放置在 a[n-2]中。当第 n-1 趟 结束时,整个 n 个数据元素集合中次小的数据元素将被放置在 a[1]中,a[0]中放置了最小 的数据元素。 public class BubbleSort{ public static void bubbleSort(int[] a){ int i, j, flag=1; int temp; int n = a.length; for(i = 1; i < n &;&; flag == 1; i++){ flag = 0; for(j = 0; j < n-i; j++){ if(a[j] > a[j+1]){ flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } }
} public static void main(String[] args){ int[] test = {64,5,7,89,6,24}; int n = test.lengt