Skip to content

Commit e53d182

Browse files
shinezejianshinezejian
committed
O(n²)的排序算法实现
1 parent 2f13768 commit e53d182

6 files changed

Lines changed: 557 additions & 0 deletions

File tree

‎src/com/zejian/structures/Sort/SortTestHelper.java‎

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
package com.zejian.structures.Sort;
2+
3+
import java.lang.reflect.Method;
4+
5+
/**
6+
* Created by zejian on 2018/2/12.
7+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
8+
* 排序算法性辅助类
9+
*/
10+
public class SortTestHelper {
11+
12+
private SortTestHelper(){}
13+
14+
/**
15+
* 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
16+
* @param n
17+
* @param rangeL
18+
* @param rangeR
19+
* @return
20+
*/
21+
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
22+
23+
assert rangeL <= rangeR;
24+
25+
Integer[] arr = new Integer[n];
26+
27+
for (int i = 0; i < n; i++)
28+
arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL));
29+
return arr;
30+
}
31+
32+
// 生成一个近乎有序的数组
33+
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
34+
// swapTimes定义了数组的无序程度:
35+
// swapTimes == 0 时, 数组完全有序
36+
// swapTimes 越大, 数组越趋向于无序
37+
public static Integer[] generateNearlyOrderedArray(int n, int swapTimes){
38+
39+
Integer[] arr = new Integer[n];
40+
for( int i = 0 ; i < n ; i ++ )
41+
arr[i] = new Integer(i);
42+
43+
for( int i = 0 ; i < swapTimes ; i ++ ){
44+
int a = (int)(Math.random() * n);
45+
int b = (int)(Math.random() * n);
46+
int t = arr[a];
47+
arr[a] = arr[b];
48+
arr[b] = t;
49+
}
50+
51+
return arr;
52+
}
53+
54+
/**
55+
* 打印arr数组的所有内容
56+
* @param arr
57+
*/
58+
public static void printArray(Object arr[]) {
59+
60+
for (int i = 0; i < arr.length; i++){
61+
System.out.print( arr[i] );
62+
System.out.print( ' ' );
63+
}
64+
System.out.println();
65+
66+
return;
67+
}
68+
69+
70+
/**
71+
* 判断arr数组是否有序
72+
* @param arr
73+
* @return
74+
*/
75+
public static boolean isSorted(Comparable[] arr){
76+
77+
for( int i = 0 ; i < arr.length - 1 ; i ++ )
78+
if( arr[i].compareTo(arr[i+1]) > 0 )
79+
return false;
80+
return true;
81+
}
82+
83+
/**
84+
* 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
85+
* @param sortClassName
86+
* @param arr
87+
*/
88+
public static <T extends Comparable<T>> void testSort(String sortClassName, T[] arr){
89+
90+
// 通过Java的反射机制，通过排序的类名，运行排序函数
91+
try{
92+
// 通过sortClassName获得排序函数的Class对象
93+
Class sortClass = Class.forName(sortClassName);
94+
// 通过排序函数的Class对象获得排序方法
95+
Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class});
96+
// 排序参数只有一个，是可比较数组arr
97+
Object[] params = new Object[]{arr};
98+
99+
long startTime = System.currentTimeMillis();
100+
// 调用排序函数
101+
sortMethod.invoke(null,params);
102+
long endTime = System.currentTimeMillis();
103+
//判断是否有序
104+
assert isSorted( arr );
105+
106+
System.out.println( sortClass.getSimpleName()+ "消耗时间: " + (endTime-startTime) + "ms" );
107+
}
108+
catch(Exception e){
109+
e.printStackTrace();
110+
}
111+
}
112+
}

‎src/com/zejian/structures/Sort/Sort_N_2/BubbleSort.java‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
package com.zejian.structures.Sort.Sort_N_2;
2+
3+
/**
4+
* Created by zejian on 2018/2/12.
5+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
6+
* 冒泡排序算法原理:比较两个相邻的元素，将值大的元素交换至右端。
7+
* 核心思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，
8+
* 将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，
9+
* 将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
10+
*
11+
*
12+
* 时间复杂度分析:
13+
* 最好的情况是只需扫描一趟,比较 N 次,没有数据移动,时间复杂度为O(N)
14+
* 最坏的情况是数据序列随机排列或者反序排列,需要 N-1 趟扫描 ,那么对于移动数据和比较次数都如下
15+
* 第一趟:比较 N - 1 次
16+
* 第二趟:比较 N - 2 次
17+
* 第三趟:比较 N - 3 次
18+
* .....
19+
* 第N-1趟:比较 1 次
20+
*
21+
* N-1趟的总次数: (N-1) + (N-2) + (N-3) + ... + 1 = (N-1)*(N-2)/2
22+
* 注意对于移动数据和比较次数都是(N-1)*(N-2)/2 ≈ N²
23+
* 所以最坏的情况下时间杂度为 O(N²)
24+
* 即冒泡排序的时间复杂度在O(N) ~ O(N²) 之间.
25+
* 同时冒泡排序算法是稳定的.
26+
*/
27+
public class BubbleSort {
28+
29+
/**
30+
* 未优化版本
31+
* @param array
32+
* @param <T>
33+
*/
34+
public static <T extends Comparable<T>> void sort1(T[] array){
35+
36+
assert array != null;
37+
38+
for (int i = 0; i <array.length ; i++) {
39+
//这里限制边界需要注意,长度要-1,防止数组越界
40+
for (int j = 0; j < array.length - 1 - i ; j++) {
41+
if(array[j].compareTo(array[j+1]) > 0){
42+
swap(array,j,j+1);
43+
}
44+
}
45+
}
46+
}
47+
48+
/**
49+
* 冒泡排序优化版,思路,如果在某轮比较中,再没有发生过交换,那么说明该数组元素已是
50+
* 有序,没有必要再进行循环操作.这里我们通过一个flag标志符记录.
51+
* @param array
52+
* @param <T>
53+
*/
54+
public static <T extends Comparable<T>> void sort(T[] array){
55+
56+
assert array != null;
57+
boolean exchange = true;//标记是否发生元素交换
58+
for (int i = 0; i <array.length && exchange ; i++) {
59+
exchange = false;
60+
//这里限制边界需要注意,长度要-1,防止数组越界
61+
for (int j = 0; j < array.length - 1 - i ; j++) {
62+
if(array[j].compareTo(array[j+1]) > 0){
63+
swap(array,j,j+1);
64+
exchange = true;
65+
}
66+
}
67+
}
68+
}
69+
70+
private static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
71+
T t = arr[i];
72+
arr[i] = arr[j];
73+
arr[j] = t;
74+
}
75+
76+
77+
public static void main(String[] args) {
78+
79+
Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
80+
BubbleSort.sort(arr);
81+
for( int i = 0 ; i < arr.length ; i ++ ){
82+
System.out.print(arr[i]);
83+
System.out.print(' ');
84+
}
85+
System.out.println();
86+
87+
//
88+
// // 测试排序算法辅助函数
89+
// int N = 20000;
90+
// Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
91+
// SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.SelectionSort", arr);
92+
93+
}
94+
}

‎src/com/zejian/structures/Sort/Sort_N_2/InsertionSort.java‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
package com.zejian.structures.Sort.Sort_N_2;
2+
3+
import com.zejian.structures.Sort.SortTestHelper;
4+
5+
/**
6+
* Created by zejian on 2018/2/12.
7+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
8+
* 插入排序算法核心思想:
9+
* 检查第i个元素，如果在它的左边的元素比它大，进行交换，然后继续下去与前一个元素比较，
10+
* 直到这个元素的左边元素比它还要小，就停止。插入排序法主要的回圈有两个变数：i和j，
11+
* 每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。
12+
*
13+
* 分成两组
14+
* 一组A已排序,一组B未排序,不断从B组中取出元素与A组元素比较,并交互位置.
15+
* 初始化时,第一组A只有一个元素,即第一个元素
16+
* 未排序组B,则为从第二个元素到最后一个元素. N-1个元素
17+
* 每轮循环比较后,A组元素总会增加已排序的元素,而B组总会减少1个未排序的元素
18+
*
19+
* 时间复杂度分析:
20+
* 在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，
21+
* 要考虑前2个元素，……，插入第N个元素，要考虑前 N - 1 个元素。因此，最坏情况下的比较次数是
22+
* 1 + 2 + 3 + ... + (N - 1) = N * (N-1) / 2 ≈ N²
23+
* 所以最坏情况下的复杂度为 O(N²)
24+
* 最好情况下，数组已经是有序的，只需要N-1次比较和0次交换
25+
* 因此最好情况下，插入排序的时间复杂度为O(N)。
26+
*
27+
* 注意插入排序与选择排序的不同是,插入排序每次发现数组有序会提前结束,
28+
* 而选择排序每次总会从头到尾找出最小的元素,因此一般情况下,插入排序的效率
29+
* 总是高于选择排序.
30+
*
31+
* 尤其在数组有序的情况下,插入排序算法的效率十分高,达到O(N)级别.
32+
*
33+
*/
34+
public class InsertionSort {
35+
36+
/**
37+
* 插入排序算法,未优化版,每次比较都进行swap
38+
* @param array
39+
*/
40+
public static <T extends Comparable<T>> void sort1(T[] array){
41+
assert array != null;
42+
//从第2个元素开始
43+
for (int i = 1; i < array.length ; i++) {
44+
//元素进行比较排序
45+
for (int j = i; j > 0 && array[j].compareTo(array[j-1]) < 0 ; j--) {
46+
swap(array,j,j-1);
47+
}
48+
}
49+
}
50+
51+
/**
52+
* 插入排序算法,优化版,在确定交换的元素后再进行交换位置
53+
* 每次比较时先不交换,在最后确定最终交换位置时再执行交换.
54+
* @param array
55+
*/
56+
public static <T extends Comparable<T>> void sort(T[] array){
57+
assert array != null;
58+
//从第2个元素开始
59+
for (int i = 1; i < array.length ; i++) {
60+
T e = array[i];//先记录要比较的元素,确定其交换的位置后再移动到对应位置
61+
int j;//记录j,最后交换时使用
62+
//普通写法
63+
// for (j = i; j > 0 ; j--) {
64+
// if(array[j-1].compareTo(e) > 0){
65+
// array[j] = array[j-1];
66+
// }
67+
// }
68+
//更优雅的写法,(array[j-1].compareTo(e) > 0)这个比较确保了发现前面没有更大元素就停止,这点与选择排序不同.
69+
for (j = i; j > 0 && array[j-1].compareTo(e) > 0; j--) {
70+
array[j] = array[j-1];
71+
}
72+
array[j] = e;
73+
}
74+
}
75+
76+
77+
private static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
78+
T t = arr[i];
79+
arr[i] = arr[j];
80+
arr[j] = t;
81+
}
82+
83+
public static void main(String[] args) {
84+
85+
// Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
86+
// InsertionSort.sort2(arr);
87+
// for( int i = 0 ; i < arr.length ; i ++ ){
88+
// System.out.print(arr[i]);
89+
// System.out.print(' ');
90+
// }
91+
// System.out.println();
92+
93+
int N = 20000;
94+
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
95+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.InsertionSort", arr);
96+
97+
98+
}
99+
}

‎src/com/zejian/structures/Sort/Sort_N_2/MainTest.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package com.zejian.structures.Sort.Sort_N_2;
2+
3+
import com.zejian.structures.Sort.SortTestHelper;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* Created by zejian on 2018/2/12.
9+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
10+
* 测试插入排序和选择排序的性能
11+
* 优化后，插入排序比选择排序性能略好
12+
* 对于有序性强的数组，插入排序远远优于选择排序
13+
*
14+
*/
15+
public class MainTest {
16+
17+
public static void main(String[] args) {
18+
19+
int N = 20000;
20+
21+
// 测试1 一般测试
22+
System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");
23+
24+
Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
25+
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
26+
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
27+
28+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.SelectionSort", arr1);
29+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.InsertionSort", arr2);
30+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.ShellSort", arr3);
31+
32+
System.out.println();
33+
34+
35+
// 测试2 有序性更强的测试
36+
System.out.println("Test for more ordered random array, size = " + N + " , random range [0,3]");
37+
38+
arr1 = SortTestHelper.generateRandomArray(N, 0, 3);
39+
arr2 = Arrays.copyOf(arr1, arr1.length);
40+
arr3 = Arrays.copyOf(arr1, arr1.length);
41+
42+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.SelectionSort", arr1);
43+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.InsertionSort", arr2);
44+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.ShellSort", arr3);
45+
46+
System.out.println();
47+
48+
49+
// 测试3 测试近乎有序的数组
50+
int swapTimes = 100;
51+
System.out.println("测试近乎有序的数组, size = " + N + " , swap time = " + swapTimes);
52+
53+
arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes);
54+
arr2 = Arrays.copyOf(arr1, arr1.length);
55+
arr3 = Arrays.copyOf(arr1, arr1.length);
56+
57+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.SelectionSort", arr1);
58+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.InsertionSort", arr2);
59+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_N_2.ShellSort", arr3);
60+
61+
return;
62+
}
63+
}

0 commit comments

Comments
 (0)