Java实现:排序算法--时间复杂度为O(n² )

时间:2021-02-22 17:18:51

为什么要学习时间复杂度为O(n² )?


1.基础
2.编码简单,易于实现,是一些简单情景的首选

3.在一些特殊情况下,简单的排序算法更有效

4.简单的排序算法思想衍生出复杂的排序算法


1.选择排序

选择排序,就是每一次都筛选出最小(或最大)的数字,然后放在每一次排序的第几个位置。

比如第一次排序,找出最小(或最大)的元素,放在第一个位置,第二次排序,找出最小(或最大)的元素,放在第二个位置.....

顺序从小到大排序:

首先选出最小元素:“1”

Java实现:排序算法--时间复杂度为O(n² )

然后将这个“1”和第一个位置进行交换:

Java实现:排序算法--时间复杂度为O(n² )

此时的“1”是在最终位置了,可以不去理会了。

接着找出剩余还没排序的最小元素:“2”

Java实现:排序算法--时间复杂度为O(n² )

跟第二个位置进行交换:

Java实现:排序算法--时间复杂度为O(n² )

以此类推进行排序,这种排序就是选择排序了。

public class SelectionSort {	public static void swap(Object[]arr , int i , int j){
Object obj = arr[i];
arr[i] = arr[j];
arr[j] = obj;
}

public static void sort_asc(Comparable[] arr){
int n = arr.length -1;
for( int i = 0 ; i <= n ; i++ ){
for( int j = i+1 ; j <= n ; j++ ){
if( arr[j].compareTo(arr[i]) < 0 ){
swap(arr,i,j);
}
}
}
}

public static void main(String[] args) {
Integer [] arr = {10,3,5,2,4,1,8,6,7,9};
sort_asc(arr);
for( int i : arr ){
System.out.print(i + " ");
}
}
}

Java实现:排序算法--时间复杂度为O(n² )

2.插入排序

插入排序,从前(或往后),第n次排序,则对n个元素进行排序。

例如第一次排序,对于“8”来说,已经排序完毕了。

Java实现:排序算法--时间复杂度为O(n² )

第二次排序,对于“6”来说,要放到前面合适的位置。

Java实现:排序算法--时间复杂度为O(n² )



比“8”还要小,放在前面的位置。

第三次排序,对于“2”来说,要放在前面3个元素合适的位置。

Java实现:排序算法--时间复杂度为O(n² )

“2”比“8”小。

Java实现:排序算法--时间复杂度为O(n² )

“2”比“6”小,继续交换一次位置。

Java实现:排序算法--时间复杂度为O(n² )

进行多次的数据交换

这样前面3个元素就排序完成了。以此类推排序完成......


public class InsertionSort {	public static void swap(Object[]arr , int i , int j){		Object obj = arr[i];		arr[i] = arr[j];		arr[j] = obj;	}		public static void sort_asc(Comparable[]arr){		int n = arr.length - 1;		for( int i = 1 ; i <= n ; i++ ) {						//寻找元素arr[i]适合插入的位置			for( int j = i ; j > 0 ; j--) {				if( arr[j].compareTo(arr[j-1]) < 0 ) {					swap(arr,j,j-1);				} else {					//如果不小于,则已排序完成,可以跳出当前循环,进行下一个循环					break;				}			}		}	}		public static void main(String[] args) {		Integer [] arr = {10,3,5,2,4,1,8,6,7,9};		sort_asc(arr);		for( int  i : arr ){			System.out.print(i + " ");		}	}}

Java实现:排序算法--时间复杂度为O(n² )

对于比较插入排序和选择排序。

在插入排序中:

public static void InsertSort(Comparable[]arr){		int n = arr.length - 1;		for( int i = 1 ; i <= n ; i++ ) {						//寻找元素arr[i]适合插入的位置			for( int j = i ; j > 0 ; j--) {				if( arr[j].compareTo(arr[j-1]) < 0 ) {					swap(arr,j,j-1);				} else {					//如果不小于,则已排序完成,可以跳出当前循环,进行下一个循环					break;				}			}		}	}

有一个break操作,能够节省一些时间。

所以理应来说比较于“选择排序”来说,要快的很多

但是其实不然,选择排序只是每一次进行一次数据的交换操作(swap)

插入排序在每一次的排序中要进行多次的数据交换操作(swap里面有3次赋值的操作),所以对于一个break语句来说,其实并没有快的多少。

所以能不能改变一下算法,让插入排序也能只进行一次数据交换呢?答案是完全可以的

改进的插入排序:

第一次排序“8”还是在那里:

Java实现:排序算法--时间复杂度为O(n² )

在第二次排序,“6”的位置的时候,不像之前那样冒然交换了。

而是先把“6”复制一份,保存起来。

Java实现:排序算法--时间复杂度为O(n² )

然后看“6”是否合适放在当前位置。

那么判断是否合适放在当前位置,比较这两位数的大小,“6”比“8”小,所以不能放在当前位置。

Java实现:排序算法--时间复杂度为O(n² )

所以把“8”向后移动一个位置,直接在当前位置进行赋值,而不是交换

Java实现:排序算法--时间复杂度为O(n² )

然后再来考察“6”,是否能放在前一个位置:

Java实现:排序算法--时间复杂度为O(n² )

此时的位置是第一个,所以不用比较了:

Java实现:排序算法--时间复杂度为O(n² )


接下来看”2“,直接复制一个副本:

Java实现:排序算法--时间复杂度为O(n² )

因为 “2” 比前面 “8”小,所以“2”不能放在这个位置,此时“8”赋值到“2”这个位置:

Java实现:排序算法--时间复杂度为O(n² )

然后再次判断 “2”是不是应该放在之前“8”这个位置,跟前面的“6”比较,不是:

所以把“6”赋值到这个位置:

Java实现:排序算法--时间复杂度为O(n² )

然后再来看 “2”是不是应该放在原来 “6”放的位置:

Java实现:排序算法--时间复杂度为O(n² )

因为是第0个位置:所以直接赋值就好了:

Java实现:排序算法--时间复杂度为O(n² )

依次类推,不用一次排序进行多次数据的交换,而是变成数据的赋值操作。

代码如下:

public static void changeSort(Integer [] arr){		for( int i = 1 ; i < arr.length ; i++ ){			//寻找元素arr[i]适合的插入位置			int temp = arr[i];			//j保存元素temp应该插入的位置			int j;			for( j = i ; j > 0 && arr[j-1] > temp ; j-- ){				arr[j] = arr[j-1];			}			arr[j] = temp;		}	}

4.冒泡排序

顾名思义:像冒泡泡一样上升。

对于一个数组,有n个元素。

第一轮排序下来,把最大(或最小)的数据给筛选出来,放在数组的最右(或最左),

然后进行第二轮排序,找出第二大(或次小)的数据,放在数组的[n-2](或[1]),

....

依次类推,进行第n轮排序,数据便以排序完成。

所以冒泡排序需要两个循环:

public class BubbleSort {	public static void swap(Object[]arr , int i , int j){		Object obj = arr[i];		arr[i] = arr[j];		arr[j] = obj;	}		public static void sort_asc(Comparable[]arr){		for(int i = arr.length-1 ; i >= 0 ; i-- ){			for( int j = i-1 ; j >= 0 ; j-- ){				if(arr[i].compareTo(arr[j]) < 0){					swap(arr,i,j);				}			}		}	}		public static void main(String[] args) {		Integer [] arr = {10,3,5,2,4,1,8,6,7,9};		sort_asc(arr);		for( int  i : arr ){			System.out.print(i + " ");		}	}}
Java实现:排序算法--时间复杂度为O(n² )