选择排序
复制 public static void selectionSort( int [] arr) {
if (arr == null || arr . length < 2 ) {
return ;
}
// 找出 0 ~ n-1 中的最小值的索引
// 找出 1 ~ n-1 中的最小值的索引
// 找出 2 ~ n-1 中的最小值的索引
// 找出 i ~ n-1 中的最小值的索引
for ( int i = 0 ; i < arr . length ; i ++ ) {
int minValueIndex = i;
for ( int j = i + 1 ; j < arr . length ; j ++ ) {
minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
}
// 交换值,将每次最小都放入前面
swap(arr , i , minValueIndex) ;
}
}
private static void swap( int [] arr , int i , int j) {
int iV = arr[i];
arr[i] = arr[j];
arr[j] = iV;
}
@ Test
public void testSelectionSort() {
int [] arr = new int []{ 1 , 3 , 5 , 3 , 2 , 9 , 2 , 5 };
selectionSort(arr) ;
System . out . println ( Arrays . toString (arr));
}
时间复杂度:
冒泡排序
依次比较相邻的数,并交换,最后将最大的数冒泡到最后,这样循环 n-1 次后,即可排序所有数。
复制 public static void bubbleSort( int [] arr) {
if (arr == null || arr . length < 2 ) {
return ;
}
// 0 ~ n-1
// 0 ~ n-2
// 0 ~ n-3
// 0 ~ n-4
// 也就是 0 ~ end
for ( int end = arr . length - 1 ; end >= 0 ; end -- ) {
// 在 0 ~ end 上对数进行两两比较,将最大的数冒泡到最后
// 需要循环 end-1 次,倒数第二次循环已经将最大值选出了
for ( int i = 0 ; i <= end - 1 ; i ++ ) { // 从1开始是为了不溢出
if (arr[i] > arr[i + 1 ]) {
swap(arr , i , i + 1 ) ;
}
}
}
}
@ Test
public void testBubbleSort() {
int [] arr = new int []{ 1 , 3 , 5 , 3 , 2 , 9 , 2 , 5 };
bubbleSort(arr) ;
System . out . println ( Arrays . toString (arr));
}
时间复杂度:
假设数组长度为 n,交换方式是最坏的情况,每次都要交换
那么交换次数为: n, n-1, n-2, ... 3, 2, 1
根据等差数列公式,Sn=n*a1+n(n-1)d/2
或者 Sn=n(a1+an)/2
,可以得到数据量级n与交换次数之间的关系为 (1/2)*(n^2) -(1/2 -a1)n
保留最高次项,故冒泡排序的时间复杂度为O(n^2)
插入排序
插入排序之所以叫插入排序,是因为他的排序过程类似扑克游戏斗地主的摸牌的排序过程。
复制 public static void insertSort( int [] arr) {
if (arr == null || arr . length < 2 ) {
return ;
}
// 0 ~ 0
// 0 ~ 1 范围有序
// 0 ~ 2 范围有序
// ...
// 0 ~ n 范围有序
for ( int end = 0 ; end < arr . length ; end ++ ) {
// 排序新数
int newNumIndex = end;
while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1 ] > arr[newNumIndex]) {
swap(arr , newNumIndex - 1 , newNumIndex) ;
newNumIndex -- ;
}
}
}
时间复杂度:
归并排序
归并排序是时间复杂度为O(n*logn)
。
递归实现
将数组拆分为两半,确认中间位置 (L+R)/2 = M
左右部分排序成功后,准备一个R-L长度的数组空间,同时遍历左右空间,每次取出一个元素,比较两个两个数字的大小。谁小将谁放额外数组空间中,这样就完成了结果的归并
就这样这样依次对半拆分排序,直到不能再拆分,再依次归并,即可完成归并排序
复制 /**
* 递归实现归并排序
*/
public void mergeSort1( int [] arr , int L , int R) {
if (arr == null || arr . length < 2
|| L < 0 || L >= arr . length
|| R < 0 || R >= arr . length || L >= R) {
return ;
}
process(arr , L , R) ;
}
public void process( int [] arr , int L , int R) {
if (L == R) {
return ;
}
int M = (L + R) / 2 ;
process(arr , L , M) ;
process(arr , M + 1 , R) ;
merge(arr , L , M , R) ;
}
public void merge( int [] arr , int L , int M , int R) {
int [] help = new int [R - L + 1 ]; // 创建一个用于盛放合并后数组的数组
int i = 0 ; // help的指针,每次填充后+1
int p1 = L; // 遍历左部分的指针
int p2 = M + 1 ; // 遍历有部分的指针
// p1 p2 都在正确的范围内
while (p1 <= M && p2 <= R) {
help[i ++ ] = arr[p1] <= arr[p2] ? arr[p1 ++ ] : arr[p2 ++ ];
}
// 如果p1在正确的范围内,说明p2循环完毕了
while (p1 <= M) {
help[i ++ ] = arr[p1 ++ ];
}
// 如果p2在正确的范围内,说明p1循环完毕了
while (p2 <= R) {
help[i ++ ] = arr[p2 ++ ];
}
// 将help排序后的内容填充到arr中
for (i = 0 ; i < help . length ; i ++ ) {
arr[L + i] = help[i];
}
}
@ Test
public void testMergeSort1() {
int [] arr = new int []{ 7 , 9 , 3 , 1 , 0 , 1 , 4 , 5 , 9 , 8 , 0 , 2 };
mergeSort1(arr , 0 , 5 ) ;
System . out . println ( Arrays . toString (arr));
}
复杂度:
复制 T(n) = aT(n/b) + O(N^d)
T(n) = 2T(n/2) + O(N^1)
a = 2, b = 2, d = 1
logbA = 1 == d,那么时间复杂度为 O(N^d * logN) ,即 O(N*logN)
也可以使用for循环替代while:
复制 package com . rhdk . contractservice ;
import java . util . Arrays ;
public class Test {
public static void main ( String [] args) {
// 递归实现归并排序
int [] arr = new int []{ 2 , 1 , 3 , 4 };
mergeSort1(arr) ;
System . out . println ( Arrays . toString (arr));
}
public static void mergeSort1 ( int [] arr) {
if (arr == null || arr . length <= 1 ) {
return ;
}
sort(arr , 0 , arr . length - 1 ) ;
}
public static void sort ( int [] arr , int L , int R) {
if (L >= R) {
return ;
}
int M = (L + R) / 2 ;
sort(arr , L , M) ;
sort(arr , M + 1 , R) ;
merge(arr , L , M , R) ;
}
public static void merge ( int [] arr , int L , int M , int R) {
int [] help = new int [R - L + 1 ];
int lIndex = L;
int rIndex = M + 1 ;
for ( int i = 0 ; i < help . length ; i ++ ) {
if (lIndex > M && rIndex > R) {
break ;
}
if (lIndex > M) {
help[i] = arr[rIndex ++ ];
continue ;
}
if (rIndex > R) {
help[i] = arr[lIndex ++ ];
continue ;
}
if (arr[lIndex] <= arr[rIndex]) {
help[i] = arr[lIndex ++ ];
} else {
help[i] = arr[rIndex ++ ];
}
}
// 填充到原数组
if (R + 1 - L >= 0 ) {
System . arraycopy (help , 0 , arr , L , R - L + 1 );
}
}
}
非递归实现
递归是将数组拆分为两半,而这种方式则是将元素分为固定的k组,整体思想是相同的
k=1:循环数组,因为数组在[0,0]、[1,1]、[2,2]、[3,3]...范围内有序,合并有序数组,让数组在[0,1]、[2,3]、[4,5]...范围内有序
k=2:循环数组,因为数组在[0,1]、[2,3]、[4,5]、[6,7]...范围内有序,合并有序数组,让数组在[0,3]、[4,7]、[8,11]...范围内有序
k=4:循环数组,因为数组在[0,3]、[4,7]、[8,11]...范围内有序,合并有序数组,让数组在[0,7]、[8,15]、[16,23]...范围内有序
k=?:循环数组,因为数组在[i, i+k-1]范围上有序,合并有序数组,让数组在 [i + 2k-1]范围内有序
如此循环数组,直到k>=arr.length
时,即完成了数组的排序
此时让 k=4,按照上述流程继续循环,将4个7有序的小组合并为8个有序的小组
代码如下:
复制 public void mergeSort2( int [] arr) {
int k = 1 ;
int i = 0 ;
while (k <= arr . length ) {
if (i >= arr . length ) {
i = 0 ;
k <<= 1 ;
}
// 左索引为i,右索引为 i + 2 * k - 1,且不能超过数组长度-1,中间为i + k - 1,且不能超过数组长度
int L = i;
int R = Math . min (i + 2 * k - 1 , arr . length - 1 );
int M = Math . min (i + k - 1 , arr . length - 1 );
// 将小组合并为大组
merge(arr , L , M , R) ;
// 重置i索引
i += 2 * k;
}
}
@ Test
public void testMergeSort2() {
int [] arr = new int []{ 9 , 7 , 3 , 1 , 0 , 1 , 4 , 5 , 9 , 8 , 0 , 2 };
mergeSort2(arr) ;
System . out . println ( Arrays . toString (arr));
}
时间复杂度:
复制 while (k <= arr.length)
i += 2 * k;
每次使用x2的方式追赶问题规模N,故外层复杂度为 logN
每当if (i >= arr.length) 重新开始循环,这是内层循环
内层循环只走了merge方法,时间复杂度为N
所以时间复杂度也为 O(N * logN)
为什么选择、冒泡、插入排序O(n^2)的时间复杂度劣于归并排序O(N * logN)?
因为前者在比较时,将所有的数依次比较,很多比较行为并没有交换,造成了很多无效的操作。
小和问题
假设有个数组, [6, 3, 4, 6, 7]
,
第4个元素左侧比该元素小的值的总和为6+3+4+6=19
要求复杂度为 O(N*logN)
快速排序
快排的步骤:
以数组中最后一个数字P为边界,将数组内的小于等于P的数放在左侧,大于P的数放右侧
当前数 <= P,当前数在 <= 区,当前数与下一个数交换,<= 区扩容1,当前数指针向后移动一次