一、插入排序 插入排序 直接插入排序:InsertSort 排序方法 最好时间 平均时间 直接插入排序 O(n) O(n2)
最坏时间 O(n2)
辅助空间 O(1)
稳定性 稳定
直接插入排序的基本思想是: 顺序地把待排序的数据元素按其值的大小插入到已排序数 据元素子集合的适当位置。 子集合的数据元素个数从只有一个数据元素开始逐次增大。 当子 集合大小最终和集合大小相同时排序完毕。
public class InsertSort { public static void insertSort(int[] a) { int i, j, temp; int n = a.length; for (i = 0; i < n - 1; i++) { temp = a[i + 1]; j = i; while (j > -1 &;&; temp <= a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; } } public static void main(String[] args) { int[] test = { 64, 5, 7, 89, 6, 24 }; int n = test.length; insertSort(test); for (int i = 0; i < n; i++) System.out.print(test[i] + " } } ");
折半插入排序:BinSort 这般查找必须是有序的数组 public class BinSort {
/** * @param args */ public static void main(String[] args) { int arr[] = new int[] {1,12, 24, 32, 41, 65, 76, 478, 483, }; //用户输入查找的内容
System.out.println("请输入要查找的数值:"); Scanner input = new Scanner(System.in); int target = input.nextInt(); //搜索开始时,查找范围的上下边界、中间元素的索引 int high = arr.length - 1; int low = 0; int mid = (high + low) / 2; //开始查找 while (low <= high &;&; arr[mid] != target) { if (target > arr[mid]) { //目标比中值大,向上收缩
搜索范围 low = mid + 1; } else { //目标比中值小,向下收缩搜索范围 high = mid - 1; } //重新设定中间元素的索引 mid = (low + high) / 2; } if (low > high) { System.out.println("目标不在数组中!"); } else { System.out.println("目标在数组中第" + (mid + 1) + "个位置!"); } } }
希尔排序:ShellSort 排序方法 最好时间 希尔排序
平均时间 O(n1.3)
最坏时间
辅助空间 O(1)
稳定性 不稳定
希尔排序的基本思想是: 把待排序的数据元素分成若干个小组, 对同一小组内的数据元 素用直接插入法排序; 小组的个数逐次缩小; 当完成了所有数据元素都在一个组内的排序后 排序过程结束。希尔排序又称作缩小增量排序。
public class ShellSort { public static void shellSort(int[] a, int[] d, int numOfD) { int i, j, k, m, span; int temp; int n = a.length; for (m = 0; m < numOfD; m++) { // 共numOfD次循环 span = d[m]; // 取本次的增量值 for (k = 0; k < span; k++) { // 共span个小组
for (i = k; i < n - span; i = i + span) { temp = a[i + span]; j = i; while (j > -1 &;&; temp <= a[j]) { a[j + span] = a[j]; j = j - span; } a[j + span] = temp; } } } } public static void main(String[] args) { int[] test = { 65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23 }; int n = test.length; int numOfD = 3; int[] d = { 6, 3, 1 }; shellSort(test, d, numOfD); for (int i = 0; i < n; i++) System.out.print(test[i] + " } } ")
;
二、选择排序 选择排序 选择排序的基本思想是:每次从待排序的数据元素集合中选取最小(或最大)的数据元 素放到数据元素集合的最前(或最后) ,数据元素集合不断缩小,当数据元素集合为空时排 序过程结束。
常用的选择排序有直接选择排序和堆排序两种。 堆排序是一种基于完全二叉树 的排序。 直接选择排序: 直接选择排序的基本思想是: 从待排序的数据元素集合中选取最小的数据元素并将它与 原始数据元素集合中的第一个数据元素交换位置; 然后从不包括第一个位置上数据元素的集 合中选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置; 如此重 复,直到数据元素集合中只剩一个数据元素为止。 (1) public class SelectSort {
public static void selectSort(int[] a) { int i, j, small; int temp; int n = a.length; for (i = 0; i < n - 1; i++) { small = i; // 设第i个数据元素最小
for (j = i + 1; j < n; j++) // 寻找最小的数据元素 if (a[j] < a