文章目录
- 空间复杂度为O(1)的三种排序法
- 一、冒泡排序法
- 1.代码实现思想
- 2.复杂度分析
- 3.代码实现
- 4.代码测试
- 二、选择排序法
- 1.代码实现思想
- 2.复杂度分析
- 3.代码实现
- 4.代码测试
- 三、插入排序法
- 1.代码实现思想
- 2.复杂度分析
- 3.代码实现
- 4.代码测试
空间复杂度为O(1)的三种排序法
一、冒泡排序法
1.代码实现思想
参考文章
慕课网数据结构与算法课程
-
冒泡,即大的数据下层,小的数据上浮。
-
代码实现:每一轮,指定数组中的一个位置,放置该位置前所有元素中的最大值,即通过数据两两比较获取
-
要将N-1个位置放置好数据,需要N-1轮
-
每轮,指针j从0位置依次遍历,遍历到指定位置的前一个位置,比较当前位置j与下个位置j+1位置数值大小,是否交换
-
代码优化,对于大量有序的数列,可能要指定的位置已经排好序,无需再循环判断,即,为了减少循环,用变量lastSwap记录已经排号序的位置,下次循环指定的位置是标志位前一个无序位置
2.复杂度分析
-
时间复杂度:
O
(
N
2
)
O(N^2)
O(N2),即需要
O
(
N
)
O(N)
O(N)轮,每轮
O
(
N
)
O(N)
O(N)的操作
-
空间复杂度:
O
(
1
)
O(1)
O(1),即需要常数级的变量空间,无需开辟新的空间
-
稳定性:指的是相同元素保存相对位置不变的特性,可以设计成稳定排序,即相等元素比较时不交换
3.代码实现
public class BubbleSort {
private BubbleSort() {}
public static <E extends Comparable<E>> void sort(E[] arr) {
if(arr == null || arr.length <= 2) return;
for(int i = arr.length -1; i > 0;) {
int lastSwap = 0;
for(int j = 0; j < i; j ++) {
if(arr[j].compareTo(arr[j + 1]) > 0) {
swap(arr, j, j + 1);
lastSwap = j + 1;
}
}
i = lastSwap - 1;
}
}
private static <E> void swap(E[] arr, int j, int i) {
E t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
public static void main(String[] args) {
int n = 10000;
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
SortingHelper.sortTime("BubbleSort", arr);
}
}
4.代码测试
设计两个辅助测试类:
import java.util.Random;
public class ArrayGenerator {
private ArrayGenerator() {}
public static Integer[] generateOrderedArray(int n) {
Integer[] arr = new Integer[n];
for(int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}
public static Integer[] generateRandomArray(int n, int border) {
Integer[] arr = new Integer[n];
Random rdm = new Random();
for(int i = 0; i < n ; i++) {
arr[i] = rdm.nextInt(border);
}
return arr;
}
}
public class SortingHelper {
private SortingHelper() {}
public static <E extends Comparable<E>> boolean isSorted(E[] arr) {
for(int i = 1; i < arr.length; i++) {
if(arr[i-1].compareTo(arr[i]) > 0) {
return false;
}
}
return true;
}
public static <E extends Comparable<E>> void sortTime(String sortName, E[] arr) {
long startTime = System.nanoTime();
if(sortName.equals("BubbleSort")) {
BubbleSort.sort(arr);
} else if(sortName.equals("InsertionSort")) {
InsertionSort.sort(arr);
} else if(sortName.equals("SelectionSort")) {
SelectionSort.sort(arr);
} else if(sortName.equals("MergeSort")) {
MergeSort.sort(arr);
}
long lastTime = System.nanoTime();
double time = (lastTime - startTime) / 1000000000.0;
if(!SortingHelper.isSorted(arr)) {
throw new RuntimeException("Sort false!");
}
System.out.println(String.format(
"%s, n = %d : %f s", sortName, arr.length, time));
}
}
输出结果:
BubbleSort, n = 10000 : 0.417135 s
二、选择排序法
1.代码实现思想
- 与冒泡思想类似,每轮选择最小元素(最大元素)放在指定位置,一般从左往右依次放置
- 选择过程也是比较交换过程,为了减少交换操作,设计一个变量minIndex储存当前轮最小值索引,遍历比较
- 最后将minIndex指向的数值与指定位置的数值进行交换,得到指定位置应该放的最小元素
2.复杂度分析
-
时间复杂度:
O
(
N
2
)
O(N^2)
O(N2),即需要
O
(
N
)
O(N)
O(N)轮,每轮
O
(
N
)
O(N)
O(N)的操作
-
空间复杂度:
O
(
1
)
O(1)
O(1),即需要常数级的变量空间,无需开辟新的空间
-
稳定性:指的是相同元素保存相对位置不变的特性,正常算法无法保持稳定性,因为交换后会打乱顺序
3.代码实现
public class SelectionSort {
private SelectionSort() {}
public static <E extends Comparable<E>> void sort2(E[] arr) {
if(arr == null || arr.length < 2) return;
for(int i = 0; i < arr.length - 1; i ++) {
int minIndex = i;
for(int j = i + 1; j < arr.length; j ++) {
minIndex = arr[j].compareTo(arr[minIndex]) < 0 ? j : minIndex;
}
swap(arr, minIndex, i);
}
}
private static <E>void swap(E[] arr, int j, int i) {
E t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
4.代码测试
public static void main(String[] args) {
int n = 10000;
System.out.println("Random Array:");
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr1 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("BubbleSort", arr);
SortingHelper.sortTime("SelectionSort", arr1);
}
Random Array:
BubbleSort, n = 10000 : 0.410318 s
SelectionSort, n = 10000 : 0.058414 s
- 通过测试知,选择排序法实现正确,且时间性能方面,由于减少了交换次数,会相对比冒泡排序法更好。
三、插入排序法
1.代码实现思想
-
每一轮,对指定元素,找到它要插入的位置,保证插入位置之前的元素已经排好序
-
通过两两比较的方式判断插入位置,保证插入的位置前所有元素比指定元素小,后所有元素比指定元素大
-
为减少比较次数,先找位置,不急着交换,只是将非插入位置元素往后挪,复杂度会低些,找到位置后,再将指定元素放到插入位置上
2.复杂度分析
- 时间复杂度:
O
(
N
2
)
O(N^2)
O(N2),即需要
O
(
N
)
O(N)
O(N)轮,每轮
O
(
N
)
O(N)
O(N)的操作
- 有序数组的排序,
O
(
1
)
O(1)
O(1),需要比较n-1次,无需交换元素
- 空间复杂度:
O
(
1
)
O(1)
O(1),即需要常数级的变量空间,无需开辟新的空间
- 稳定性:指的是相同元素保存相对位置不变的特性,因为位置是相对挪动,保证相同元素不挪动,可以保证稳定性
3.代码实现
import java.util.Arrays;
import bubbleSort.ArrayGenerator;
import bubbleSort.SortingHelper;
public class InsertionSort {
private InsertionSort() {};
public static <E extends Comparable<E>> void sort(E[] arr) {
for(int i = 1; i < arr.length; i ++) {
E target = arr[i];
int j;
for(j = i; j > 0 && arr[j - 1].compareTo(target) > 0; j --) {
arr[j] = arr[j - 1];
}
arr[j] = target;
}
}
}
4.代码测试
public static void main(String[] args) {
int n = 10000;
System.out.println("Random Array:");
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr1 = Arrays.copyOf(arr, arr.length);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("BubbleSort", arr);
SortingHelper.sortTime("SelectionSort", arr1);
SortingHelper.sortTime("InsertionSort", arr2);
System.out.println();
System.out.println("Order Array:");
arr = ArrayGenerator.generateOrderedArray(n);
arr1 = Arrays.copyOf(arr, arr.length);
arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("BubbleSort", arr);
SortingHelper.sortTime("SelectionSort", arr1);
SortingHelper.sortTime("InsertionSort", arr2);
}
Random Array:
BubbleSort, n = 10000 : 0.430529 s
SelectionSort, n = 10000 : 0.057633 s
InsertionSort, n = 10000 : 0.153631 s
Order Array:
BubbleSort, n = 10000 : 0.106295 s
SelectionSort, n = 10000 : 0.046629 s
InsertionSort, n = 10000 : 0.000241 s
- 测试结果显示:排序算法正确,无序数组,性能方面,选择排序法由于交换次数较少,较其他两种较优
- 有序数组,插入排序法,对已经排好序的数组操作较简单,性能较其他两种较优
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)