[small]) small = j; // 记住最小元素的下标 if (small != i) { // 当最小元素的下标不为i时交换位置 temp = a[i]; a[i] = a[small]; a[small] = temp; } } } public static void main(String[] args) { int[] test = { 64, 5, 7, 89, 6, 24 }; int n = test.length; selectSort(test); for (int i = 0; i < n; i++) System.out.print(test[i] + " } } ");
(2)稳定的直接选择排序 (2)稳定的直接选择排序 排序方法 最好时间 直接选择排序 O(n2)
平均时间 O(n2)
最坏时间 O(n2)
辅助空间 O(1)
稳定性 稳定
直接选择排序的基本思想是: 从待排序的数据元素集合中选取最小的数据元素并将它与 原始数据元素集合中的第一个数据元素交换位置; 然后从不包括第一个位置上数据元素的集 合中选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置; 如此重 复,直到数据元素集合中只剩一个数据元素为止。
public class SelectSort2 { public static void selectSort2(int a[]) { int i, j, small; int temp; int n = a.length; for (i = 0; i < n - 1; i++) { small = i; for (j = i + 1; j < n; j++) { // 寻找最小的数据元素 if (a[j] < a[small]) small = j; // 记住最小元素的下标 }
if (small != i) { temp = a[small]; for (j = small; j > i; j--) // 把该区段尚未排序元素依次后移 a[j] = a[j - 1]; a[i] = temp; // 插入找出的最小元素 } } } public static void main(String[] args) { int[] test = { 64, 5, 7, 89, 6, 24, 5 }; int n = test.length; selectSort2(test); for (int i = 0; i < n; i++) System.out.print(test[i] + " } } ");
堆排序:HeapSort 排序方法 最好时间 堆排序 O(nlog2n)
平均时间 O(nlog2n)
最坏时间 O(nlog2n)
辅助空间 O(1)
稳定性 不稳定
在直接选择排序中,放在数组中的 n 个数据元素排成一个线性序列(即线性结
构) ,要 从有 n 个数据元素的数组中选择出一个最小的数据元素需要比较 n-1 次。 如果能把待排序的 数据元素集合构成一个完全二叉树结构,则每次选择出一个最大(或最小)的数据元素只需 比较完全二叉树的高度次,即 log2n 次,则排序算法的时间复杂度就是 O(nlog2n)。这就是 堆排序的基本思想。 堆排序的基本思想是:循环执行如下过程直到数组为空: (1)把堆顶 a[0]元素(最大 元素)和当前最大堆的最后一个元素交换; (2)最大堆元素个数减 1; (3)调整根结点使之 满足最大堆的定义。 最大堆的定义如下: 最大堆的定义如下 个数据元素, 开始, 设数组 a 中存放了 n 个数据元素,数组下标从 0 开始,如果当数组下标 2i+1
public class HeapSort { public static void createHeap(int[] a, int n, int h) { int i, j, flag; int temp; i = h; // i为要建堆的二叉树根结点下标 j = 2 * i + 1; // j为i结点的左孩子结点的下标 temp = a[i]; flag = 0; // 沿左右孩子中值较大者重复向下筛选 while (j < n &;&; flag != 1) { // 寻找左右孩子结点中的较大者,j为其下标 if (j < n - 1 &;&; a[j] < a[j + 1]) j++; if (temp > a[j]) // a[i]>a[j] flag = 1; // 标记结束筛选条件 else { // 否则把a[j]上移 a[i] = a[j]; i = j; j = 2 * i + 1; } } a[i] = temp; // 把最初的a[i]赋予最后的a[j] } public static void initCreateHeap(int[] a) { int n = a.length; for (int i = (n - 1) / 2; i >= 0; i--) createHeap(a, n, i); } public static void heapSort(int[] a) { int temp; int n = a.length; initCreateHeap(a); // 初始化创建最大堆 for (int i = n - 1; i > 0; i-