package com.wy.mycode.algorithm.sort.common;
public class SortExample {
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void show(String msg, Comparable[] a) {
System.out.print(msg + ": ");
show(a);
}
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;
}
}
测试数据
package com.wy.mycode.algorithm.sort.common; import java.util.Random; public class TestExampleData implements Comparable选择排序{ private int value; public int getValue() { return value; } public void setValue(int value) { this.value = value; } @Override public String toString() { return value + ""; } @Override public int compareTo(TestExampleData a) { if (this.getValue() - a.getValue() >= 0) { return 1; } return -1; } public static TestExampleData[] getTestData(int n) { TestExampleData[] array = new TestExampleData[n]; for (int i = 0; i < n; i++) { TestExampleData testExampleData = new TestExampleData(); Random random = new Random(); testExampleData.value = random.nextInt(1001); array[i] = testExampleData; } return array; } }
第一次:选择数组中的最小的元素,与数组中的第一个元素交换位置(如果第一个元素就是最小的,也交换)
第二次:从剩下元素中选择最小的元素,与数组中第二个元素交换位置
如此往复,直到遍历完整个数组对于长度为n的数组,选择排序需要 n 2 2 dfrac{n^2}{2} 2n2 次比较和 n 次交换
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Selection extends SortExample {
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
// 找到当前最小的元素
for (int j = i; j < a.length; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
// 交换位置
exch(a, i, min);
}
System.out.println();
}
public static void main(String[] args) {
TestExampleData[] array = TestExampleData.getTestData(10);
show("排序前", array);
sort(array);
if (isSorted(array)) {
show("排序后", array);
return;
}
show("排序失败", array);
}
}
插入排序
遍历数组,将数据插入到合适到位置
第一次:只有一个数,那么它一定在它最合适的位置
第二次:比较第二个数与第一个数的大小,如果第二个数小于第一个数,交换他们位置
第三次:比较第三个数与前两个数的大小,并按照比较结果交换它们位置
直到数组遍历完
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Insertion extends SortExample {
public static void sort(Comparable[] array) {
for (int i = 1; i < array.length; i++) {
for (int j = i; j > 0 && less(array[j], array[j-1]); j--) {
exch(array, j, j-1);
}
}
}
public static void main(String[] args) {
TestExampleData[] testData = TestExampleData.getTestData(10);
show("排序前", testData);
sort(testData);
if (isSorted(testData)) {
show("排序后", testData);
return;
}
show("排序失败", testData);
}
}
希尔排序
希尔排序轨迹:间隔为 5,3, 1希尔排序的思想是使数组中任意间隔为h的元素都是有序的
排序前
| 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49 | 55 | 4 |
|---|
第一次间隔为5,得到的子序列为:
(49, 13) (38, 27) (65, 49) (97, 55) (76, 4)
对子序列进行插入排序,得到:
| 13 | 27 | 49 | 55 | 4 | 49 | 38 | 65 | 97 | 76 |
|---|
第二次间隔为3,得到的子序列为:
(13, 55, 38, 76) (27, 4, 65) (49, 49, 97)
对子序列进程插入排序,得到:
| 13 | 4 | 49 | 38 | 27 | 49 | 55 | 65 | 97 | 76 |
|---|
最后一次间隔为1,得到的子序列就是第二次排序后的序列,对该序列进行插入排序
| 4 | 13 | 27 | 38 | 49 | 49 | 55 | 65 | 76 | 97 |
|---|
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Shell extends SortExample {
public static void sort(Comparable[] array) {
int length = array.length;
int h = 1;
// h初始化
while (h < length / 3) {
// h的可能为:1, 4, 13, 40, 121, 364, 1093...
h = 3 * h + 1;
}
while (h >= 1) {
// 对间隔为h的子序列进行插入排序
// 由于希尔排序的 h 一定存在一个值 1, 即对整个array进行插入排序,故,只需要将原插入逻辑改写
for (int i = h; i < length; i++) {
for (int j = i; j >= h && less(array[j], array[j-h]); j = j - h) {
exch(array, j, j-h);
}
}
h /= 3;
}
}
public static void main(String[] args) {
TestExampleData[] array = TestExampleData.getTestData(21);
show("排序前", array);
sort(array);
if (isSorted(array)) {
show("排序后", array);
return;
}
show("排序失败", array);
}
}
归并排序
将两个有序数组归并成一个更大的有序数组
| 534 | 629 | 817 | 108 | 788 | 375 |
|---|
第一次:待合并的有序数组为 534 与 629, 817与108, 788与375,合并后的结果为:
| 534 | 629 | 108 | 817 | 375 | 788 |
|---|
第二次:待合并的有序数组为 (534, 629) 与 (108,817), (375, 788), 合并后的结果为
| 108 | 534 | 629 | 817 | 375 | 788 |
|---|
第三次:待合并的有序数组为 (108, 534. 629, 817) 与 (375, 788), 合并后的结果为
| 108 | 375 | 534 | 629 | 788 | 817 |
|---|
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Merge extends SortExample {
private static Comparable[] aux;
public static void merge(Comparable[] array, int low, int mid, int high) {
// 第一个有序数组的第一个坐标
int i = low;
// 第二个有序数组的第一个坐标
int j = mid + 1;
// 初始化辅助数组
for (int k = low; k <= high ; k++) {
aux[k] = array[k];
}
for (int k = low; k <= high; k++) {
if (i > mid) {
// 此时说明,第一个数组,已经被合并完了,只需要将第二个数组剩余部分全部加进去
array[k] = aux[j++];
}else if (j > high) {
// 第二个数组合并完成了
array[k] = aux[i++];
}else if (less(aux[j], aux[i])) {
array[k] = aux[j++];
}else {
array[k] = aux[i++];
}
}
}
public static void sort(Comparable[] array) {
// 辅助数组初始化容量
aux = new Comparable[array.length];
sort(array, 0, array.length - 1);
}
private static void sort(Comparable[] array, int low, int high) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
sort(array, low, mid);
sort(array, mid+1, high);
merge(array, low, mid, high);
}
public static void main(String[] args) {
TestExampleData[] testData = TestExampleData.getTestData(100);
show("排序前", testData);
sort(testData);
if (isSorted(testData)) {
show("排序后", testData);
return;
}
show("排序失败", testData);
}
}
快速排序
选定一个基数 a,是 <= a的数都位于a的左边,> a 的数都位于a的右边
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Quick extends SortExample {
public static void sort(Comparable[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(Comparable[] array, int low, int high) {
if (low >= high) {
return;
}
int v = partition(array, low, high);
sort(array, low, v-1);
sort(array, v+1, high);
}
private static int partition(Comparable[] array, int low, int high) {
int i = low;
int j = high + 1;
Comparable v = array[low];
while (true) {
// 找到左边第一个大于 v 的数
while (less(array[++i], v)) {
if (i == high) {
break;
}
}
// 找到右边第一个小于v的数
while (less(v, array[--j])) {
if (j == low) {
break;
}
}
if (i >= j) {
break;
}
// 交换它们的位置
exch(array, i, j);
}
// 将 v 放入正确的位置
exch(array, low, j);
// 返回 v 的下标
return j;
}
public static void main(String[] args) {
TestExampleData[] testData = TestExampleData.getTestData(10);
show("排序前", testData);
sort(testData);
if (isSorted(testData)) {
show("排序后", testData);
return;
}
show("排序失败", testData);
}
}
冒泡排序
两两比较,交换位置;每次都能确定一个数的最终位置
package com.wy.mycode.algorithm.sort;
import com.wy.mycode.algorithm.sort.common.SortExample;
import com.wy.mycode.algorithm.sort.common.TestExampleData;
public class Bubble extends SortExample {
public static void sort(Comparable[] array) {
// 对n个数进行,冒泡排序,最多要进行 n - 1 轮,因为每次都能确定一个数都位置
for (int i = 1; i < array.length; i++) {
// 结束循环的标志 是否发生交换
boolean eachFlag = false;
// 第二层循环表示 每个数要比较的次数
for (int j = 0; j < array.length - i; j++) {
if (less(array[j+1], array[j])) {
exch(array, j+1, j);
eachFlag = true;
}
}
if (!eachFlag) {
break;
}
}
}
public static void main(String[] args) {
TestExampleData[] testData = TestExampleData.getTestData(6000);
show("排序前", testData);
sort(testData);
if (isSorted(testData)) {
show("排序后", testData);
return;
}
show("排序失败", testData);
}
}



