算法4-第二章-排序
排序
2.1 初级排序
2.1.2 选择排序
基本思路:遍历数组依次找到最小的，放入队列的前面即可。
代码示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Selection {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[min])) min = j;
exch(a, i, min);
}
}
}
}
2.1.3 插入排序
基本思路:根据索引遍历数组，发现右边的比左边的小，则直接调换位置。发现右边>=左边的后，则停止对比（因为左边的已经是从小到大排列好的了）
代码示例：
1
2
3
4
5
6
7
8
9
10
11
public class Insertion {
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, j - 1);
}
}
}
}
2.1.6 希尔排序
基本思想：主要是在插入排序的基础上，减少对比替换的次数。
例如：插入排序如果最小数放在最末尾，则排序替换的时候需要执行 N 次，才能替换成功，希尔排序是将原数组拆分成多个数组，然后分别进行插入排序，并确保小数在前，大数在后，以此来减少对比替换次数。
例如：有数组[3,4,1,6,8,7,5,29,10],可以将其拆分为 4 列：
1
2
3 4 1 8
7 5 29 10
然后每列插入排序就，再次缩小列数
1
2
3
4
3 4
1 8
7 5
29 10
1
2
3
4
1 4
3 5
7 8
29 10
可以按此进行多次拆分,直到最后只剩下一列，然后进行正常的插入排序，即可完成整个排序
1
2
3
4
5
6
7
8
1
4
3
5
7
8
29
10
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Shell {
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) h = 3 * h + 1;
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;
}
}
}
公用的基础的比较替换方法
1
2
3
4
5
6
7
8
9
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;
}
2.2 归并排序
2.2.1 原地归并的抽象方法
主要思想：将一个数组拆分为多个数组，之后在进行合并排序 示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
Comparable[] aux = new Comparable[hi - 1]; //首先将数组统一复制到aux中
for (int k = lo; k < hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k < hi; k++) { //遍历所有数据
if (i > mid) a[k] = aux[j++]; //如果左边的数组用完了，则直接将右边的数组填入
else if (j > hi) a[k] = aux[i++]; //如果右边的数组用完了，则直接将左边的数组填入
else if (less(aux[j], aux[i])) a[k] = aux[j++]; //如果两边数组都还没用完，则对比当前左右两边第一个数据的大小，填入小的
else a[k] = aux[i++];
}
}
2.2.2 自顶向下的归并排序
递归将大数组拆分为小数组，并将小数组逐步递归合并排序为大数组
示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
public static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
2.2.3 自低向上的归并排序
两两数组归并排序，再四四数组合并，如此最终合并所有数组 示例：
1
2
3
4
5
6
7
8
9
public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz) {
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
2.3 快速排序
2.3.1 基本算法
基本思想：找到一个数，对数组进行切分，确保左边的都比它小，右边的都比它大，然后对左右再次如此递归，直到左右 index 相等不再需要排序为止 示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable v = a[lo];
while (true) {
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
2.3.3 算法改进
2.3.3.2 三取样切分
主要思想：从数组中取 3 个数，进行排序，然后将大的放到数组的最末尾，小的放到数组中间，中位数的放到数组的开头。然后用中位数当作切分元素。进行快排的逻辑。（这可以带来约 5%~10% 的性能提升）
主要是因为快排比较依靠切分值，切分值选的好的话，直接就可以将数组切分为平均的两半（在切分不平衡时这个程序可能会极为低效。例如，如果第一次从最小的元素切分，第二次从第二小的元素切分，如此这般，每次调用 只会移除一个元素。这会导致一个大子数组需要切分很多次。）
2.3.3.2 三向切分的快速排序
主要思想：将数组排序，将小的放左边，相等的放中间，大于的放右边。然后再将小/大的这两部份分别递归排序(更快速排序的区分数，快排是找个数，然后来排序，三分取样没有具体针对某个数，而是整体遍历替换，保证大/中/小三部份，然后再递归三分取样)
示例代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}
2.4 优先队列
2.4.1 优先队列
优先队列是一种抽象数据类型，优先队列最重要的操作就是删除最大元素和插入元素。
二叉堆
二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。 例如下图：
1
2
3
4
5
6
7
8
1 11
/ \ / \
2 3 9 10
/ \ / \ / \ / \
4 5 6 7 5 6 7 8
/ \ / \ / \ / \
8 9 10 11 1 2 3 4
2.4.2 初级实现
数组实现二叉堆，因为二叉堆是有序的，所以在插入的时候直接在尾部直接插入，然后用当前的 index/2 得到它的上面一级，作对比替换就可以了
2.4.5 堆排序
主要思想：先将数组进行排序，构造成最大二叉堆，然后，再将堆底部的数顺序跟最顶部的数进行交换(确保所有二叉堆右侧的也都经历了排序)并重新修复堆结构(确保二叉堆左侧的经历了排序)，如此递归到堆的堆顶部，即可完成排序。 堆排序类似于选择排序，但是不需要额外的空间
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static void sort(Comparable[] pq) {
int n = pq.length;
for (int k = n / 2; k >= 1; k--)
sink(pq, k, n);
while (n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}
private static void sink(Comparable[] pq, int k, int n) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(pq, j, j + 1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i - 1].compareTo(pq[j - 1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i - 1];
pq[i - 1] = pq[j - 1];
}
2.5 应用
--EOF--
若无特别说明，本站文章均为原创，转载请保留链接，谢谢