文章目录
1.冒泡排序2.选择排序3.插入排序4.归并排序5.快速排序
1.冒泡排序
import java
.util
.Arrays
;
public class BubbleSort {
public static void bubbleSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= arr
.length
- 1; i
>= 0; i
--) {
for (int j
= 0; j
< i
; j
++) {
if (arr
[j
] > arr
[j
+ 1]) {
swap(arr
, j
, j
+ 1);
}
}
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static boolean isEqual(int[] arr1
, int[] arr2
) {
if (arr1
== null
&& arr2
== null
) {
return true;
}
if (arr1
== null
|| arr2
== null
) {
return false;
}
if (arr1
.length
!= arr2
.length
) return false;
for (int i
= 0; i
< arr1
.length
; i
++) {
if (arr1
[i
] != arr2
[i
]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr
) {
if (arr
== null
) {
return null
;
}
int[] res
= new int[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
res
[i
] = arr
[i
];
}
return res
;
}
public static void comparator(int[] arr
) {
Arrays
.sort(arr
);
}
public static int[] generateRandomArray(int maxSize
, int maxValue
) {
int[] arr
= new int[(int) (Math
.random() * (maxSize
+ 1))];
for (int i
= 0; i
< arr
.length
; i
++) {
arr
[i
] = (int) (Math
.random() * (maxValue
+ 1)) - (int) (Math
.random() * (maxValue
+ 1));
}
return arr
;
}
public static void printArray(int[] arr
) {
if (arr
== null
) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.print(arr
[i
]);
}
System
.out
.println();
}
public static void main(String
[] arg
) {
int testTime
= 500000;
int maxSize
= 100;
int maxValue
= 100;
boolean succeed
= true;
for (int i
= 0; i
< testTime
; i
++) {
int[] arr1
= generateRandomArray(maxSize
, maxValue
);
int[] arr2
= copyArray(arr1
);
bubbleSort(arr1
);
comparator(arr2
);
if (!isEqual(arr1
, arr2
)) {
succeed
= false;
printArray(arr1
);
printArray(arr2
);
break;
}
}
System
.out
.println(succeed
? "Nice!" : "Fucking fucked!");
}
}
时间复杂度O(N^2)，额外空间复杂度O(1)
2.选择排序
import java
.util
.Arrays
;
public class SelectSort {
public static void selectSort(int[] 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
] < arr
[minIndex
] ? j
: minIndex
;
}
swap(arr
, i
, minIndex
);
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static boolean isEqual(int[] arr1
, int[] arr2
) {
if (arr1
== null
&& arr2
== null
) {
return true;
}
if (arr1
== null
|| arr2
== null
) {
return false;
}
if (arr1
.length
!= arr2
.length
) return false;
for (int i
= 0; i
< arr1
.length
; i
++) {
if (arr1
[i
] != arr2
[i
]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr
) {
if (arr
== null
) {
return null
;
}
int[] res
= new int[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
res
[i
] = arr
[i
];
}
return res
;
}
public static void comparator(int[] arr
) {
Arrays
.sort(arr
);
}
public static int[] generateRandomArray(int maxSize
, int maxValue
) {
int[] arr
= new int[(int) (Math
.random() * (maxSize
+ 1))];
for (int i
= 0; i
< arr
.length
; i
++) {
arr
[i
] = (int) (Math
.random() * (maxValue
+ 1)) - (int) (Math
.random() * (maxValue
+ 1));
}
return arr
;
}
public static void printArray(int[] arr
) {
if (arr
== null
) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.print(arr
[i
]+" ");
}
System
.out
.println();
}
public static void main(String
[] arg
) {
int testTime
= 500000;
int maxSize
= 100;
int maxValue
= 100;
boolean succeed
= true;
for (int i
= 0; i
< testTime
; i
++) {
int[] arr1
= generateRandomArray(maxSize
, maxValue
);
int[] arr2
= copyArray(arr1
);
selectSort(arr1
);
comparator(arr2
);
if (!isEqual(arr1
, arr2
)) {
succeed
= false;
printArray(arr1
);
printArray(arr2
);
break;
}
}
System
.out
.println(succeed
? "Nice!" : "Fucking fucked!");
}
}
时间复杂度O(N^2)，额外空间复杂度O(1)
3.插入排序
import java
.util
.Arrays
;
public class InsertSort {
public static void insertSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= 1; i
< arr
.length
; i
++) {
for (int j
= i
- 1; j
>= 0 && arr
[j
] > arr
[j
+ 1]; j
--) {
swap(arr
, j
, j
+ 1);
}
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static boolean isEqual(int[] arr1
, int[] arr2
) {
if (arr1
== null
&& arr2
== null
) {
return true;
}
if (arr1
== null
|| arr2
== null
) {
return false;
}
if (arr1
.length
!= arr2
.length
) return false;
for (int i
= 0; i
< arr1
.length
; i
++) {
if (arr1
[i
] != arr2
[i
]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr
) {
if (arr
== null
) {
return null
;
}
int[] res
= new int[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
res
[i
] = arr
[i
];
}
return res
;
}
public static void comparator(int[] arr
) {
Arrays
.sort(arr
);
}
public static int[] generateRandomArray(int maxSize
, int maxValue
) {
int[] arr
= new int[(int) (Math
.random() * (maxSize
+ 1))];
for (int i
= 0; i
< arr
.length
; i
++) {
arr
[i
] = (int) (Math
.random() * (maxValue
+ 1)) - (int) (Math
.random() * (maxValue
+ 1));
}
return arr
;
}
public static void printArray(int[] arr
) {
if (arr
== null
) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.print(arr
[i
]);
}
System
.out
.println();
}
public static void main(String
[] arg
) {
int testTime
= 500000;
int maxSize
= 100;
int maxValue
= 100;
boolean succeed
= true;
for (int i
= 0; i
< testTime
; i
++) {
int[] arr1
= generateRandomArray(maxSize
, maxValue
);
int[] arr2
= copyArray(arr1
);
insertSort(arr1
);
comparator(arr2
);
if (!isEqual(arr1
, arr2
)) {
succeed
= false;
printArray(arr1
);
printArray(arr2
);
break;
}
}
System
.out
.println(succeed
? "Nice!" : "Fucking fucked!");
}
}
时间复杂度O(N^2)，额外空间复杂度O(1)
4.归并排序
import java
.util
.Arrays
;
public class MergeSort {
public static void mergeSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
mergeSort(arr
, 0, arr
.length
- 1);
}
public static void mergeSort(int[] arr
, int l
, int r
) {
if (l
< r
) {
int mid
= l
+ ((r
- l
) >> 1);
mergeSort(arr
, l
, mid
);
mergeSort(arr
, mid
+ 1, r
);
merge(arr
, l
, mid
, r
);
}
}
public static void merge(int[] arr
, int l
, int mid
, int r
) {
int[] help
= new int[r
- l
+ 1];
int p1
= l
;
int p2
= mid
+ 1;
int p
;
for (p
= 0; p1
<= mid
&& p2
<= r
; p
++) {
help
[p
] = arr
[p1
] < arr
[p2
] ? arr
[p1
++] : arr
[p2
++];
}
while (p1
<= mid
) {
help
[p
++] = arr
[p1
++];
}
while (p2
<= r
) {
help
[p
++] = arr
[p2
++];
}
for (int i
= 0; i
< help
.length
; i
++) {
arr
[l
+ i
] = help
[i
];
}
}
public static boolean isEqual(int[] arr1
, int[] arr2
) {
if (arr1
== null
&& arr2
== null
) return true;
if (arr1
== null
|| arr2
== null
) {
return false;
}
if (arr1
.length
!= arr2
.length
) {
return false;
}
for (int i
= 0; i
< arr1
.length
; i
++) {
if (arr1
[i
] != arr2
[i
]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr
) {
if (arr
== null
) {
return null
;
}
int[] res
= new int[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
res
[i
] = arr
[i
];
}
return res
;
}
public static void comparator(int[] arr
) {
Arrays
.sort(arr
);
}
public static int[] generateRandomArray(int maxSize
, int maxValue
) {
int[] arr
= new int[(int) (Math
.random() * (maxSize
+ 1))];
for (int i
= 0; i
< arr
.length
; i
++) {
arr
[i
] = (int) (Math
.random() * (maxValue
+ 1)) - (int) (Math
.random() * (maxValue
+ 1));
}
return arr
;
}
public static void printArray(int[] arr
) {
if (arr
== null
) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.print(arr
[i
]);
}
System
.out
.println();
}
public static void main(String
[] arg
) {
int testTime
= 500000;
int maxSize
= 100;
int maxValue
= 100;
boolean succeed
= true;
for (int i
= 0; i
< testTime
; i
++) {
int[] arr1
;
arr1
= generateRandomArray(maxSize
, maxValue
);
int[] arr2
= copyArray(arr1
);
mergeSort(arr1
);
comparator(arr2
);
if (!isEqual(arr1
, arr2
)) {
succeed
= false;
printArray(arr1
);
printArray(arr2
);
break;
}
}
System
.out
.println(succeed
? "Nice!" : "Fucking fucked!");
}
}
时间复杂度O(N*logN)，额外空间复杂度O(N)
5.快速排序
import java
.util
.Arrays
;
public class QuickSort {
public static void quickSort(int[] arr
) {
if (arr
.length
< 2 || arr
== null
) {
return;
}
quickSort(arr
,0,arr
.length
-1);
}
public static void quickSort(int[] arr
, int l
, int r
) {
if (l
< r
) {
int[] p
= partition(arr
, l
, r
);
quickSort(arr
, l
, p
[0] - 1);
quickSort(arr
, p
[1] + 1, r
);
}
}
private static int[] partition(int[] arr
, int l
, int r
) {
int less
= l
- 1;
int more
= r
+ 1;
int num
= arr
[l
+ (int) (Math
.random() * (r
- l
+ 1))];
int cur
= l
;
while (cur
< more
) {
if (arr
[cur
] < num
) {
swap(arr
, cur
++, ++less
);
} else if (arr
[cur
] > num
) swap(arr
, cur
, --more
);
else {
cur
++;
}
}
return new int[]{less
+ 1, more
- 1};
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static boolean isEqual(int[] arr1
, int[] arr2
) {
if (arr1
== null
&& arr2
== null
) {
return true;
}
if (arr1
== null
|| arr2
== null
) {
return false;
}
if (arr1
.length
!= arr2
.length
) {
return false;
}
for (int i
= 0; i
< arr1
.length
; i
++) {
if (arr1
[i
] != arr2
[i
]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr
) {
if (arr
== null
) {
return null
;
}
int[] res
= new int[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
res
[i
] = arr
[i
];
}
return res
;
}
public static void comparator(int[] arr
) {
Arrays
.sort(arr
);
}
public static int[] generateRandomArray(int maxSize
, int maxValue
) {
int[] arr
= new int[(int) (Math
.random() * (maxSize
+ 1))];
for (int i
= 0; i
< arr
.length
; i
++) {
arr
[i
] = (int) (Math
.random() * (maxValue
+ 1)) - (int) (Math
.random() * (maxValue
+ 1));
}
return arr
;
}
public static void printArray(int[] arr
) {
if (arr
== null
) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.print(arr
[i
]);
}
System
.out
.println();
}
public static void main(String
[] arg
) {
int testTime
= 500000;
int maxSize
= 100;
int maxValue
= 100;
boolean succeed
= true;
for (int i
= 0; i
< testTime
; i
++) {
int[] arr1
;
arr1
= generateRandomArray(maxSize
, maxValue
);
int[] arr2
= copyArray(arr1
);
quickSort(arr1
);
comparator(arr2
);
if (!isEqual(arr1
, arr2
)) {
succeed
= false;
printArray(arr1
);
printArray(arr2
);
break;
}
}
System
.out
.println(succeed
? "Nice!" : "Fucking fucked!");
}
}
随机快速排序复杂度：时间复杂度O(N*logN)，额外空间复杂度O(logN)
