排序模板
public class Example {
public static void sort(Comparable[] a) {
// 各类排序算法
}
private static boolean less(Comparable v, Comparable w) {
// 对元素进行比较
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
// 将元素交换位置
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
// 在单行中打印数组
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}
public static boolean isSorted(Comparable[] a) {
// 测试数组元素是否有序
for(int i = 1; i < a.length; i++)
if(less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
// 从标准输入读取字符串，将它们排序并输出
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
- sort - 排序算法的具体实现
- less - 比较元素
- exch - 元素交换位置
- show - 打印数组
- isSorted - 判断数组元素是否有序
- main - 标准输入读取字符串，将它们排序并输出
选择排序
首先找到最小的那个元素，其次，将它和数组第一个元素交换位置,再次，
在剩下的元素中找到最小的元素，将它与数组的第二个元素交换，直到整个数组排序
public static void sort(Comparable[] a) {
// 将 a[] 按升序排列
int N = a.length;
for(int i = 0 ; i < N; i++) {
// 将 a[i] 和 a[i...N]中最小的元素交换
int min = i; // 最小元素的索引
for(int j = i+1; j < N; j++)
if(less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
特点
运行时间和输入无关：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长；
数据移动是最少的：每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。其他算法大多都是线性对数或是平方级别。
插入排序
直接插入
与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定。为了给更小的元素腾出空间，它们可能会向右移动。当索引到达数组的右端时，数组排序就完成了。
public static void sort(Comparable a[]) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j - 1, j);
}
}
}
二分法插入排序
二分法定位插入的位置
public void sort_2(int arr[]) {
int N = arr.length;
int low, high, mid, temp;
for (int i = 1; i < N; i++) {
temp = arr[i];
low = 0;
high = i;
while (low <= high) {
mid = (low + high) / 2;
if (temp > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}//循环结束,元素应该在low 位置
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp;
}
}
特点
查入排序堆部分有序的数组十分高效，也适合小规模数组
与选择排序不同的是，排序所需的时间取决于输入元素中的初始化顺序
比较
插入排序不会访问索引右侧元素，而选择排序不会访问索引左侧元素
希尔排序
出发点
直接插入排序在以下情况下高效
- 基本有序
- 待排序的记录个数较少
思想
-
将整个排序记录序列分割成若干个子序列,分别进行直接排序
-
待整个序列中的记录"基本有序"时,再对全体记录进行以次直接插入排序
使数组中任意间隔为 h(增量) 的元素都是有序的。这样的数组被称为 h(增量) 有序数组。
增量不断缩小直到为1时，数组有序，排序结束
//算法4例子
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;//增量
while (h < N / 3) {
h = 3 * h + 1; //1,4,13,40,121,364,1093..
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;//缩小增量
}
}
public static void sort02(Comparable[] a) {
int N = a.length;
int gap = N / 2;//增量每次减半
while (gap >= 1) {
for (int i = gap; i < N; i++) {
for (int j = i; j >= gap && less(a[j], a[j - gap]);j -= gap) {
exch(a, j, j - gap);
}
}
gap = gap / 2;
}
}
希尔排序是一种基于插入排序的快速的排序算法，为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
特点
简单的计算增量和复杂的计算增量的性能接近。
希尔排序不同于*选择* *插入* 可以作用于大型数组，对任意排序的数组表现也很好