冒泡排序
流程
在arr[0...N-1]
范围上:
arr[0]
和arr[1]
,谁大谁来到1位置;
arr[1]
和arr[2]
,谁大谁来到2位置
以此类推...
arr[N-2]
和arr[N-1]
,谁大谁来到第N-1个位置上
在arr[0...N-2]
范围上,重复上面的过程,但最后一步是arr[N-3]
和arr[N-2]
,谁大谁来到第N-2个位置上
在arr[0...N-3]
范围上,重复上面的过程,但最后一步是arr[N-4]
和arr[N-3]
,谁大谁来到第N-3个位置上
以此类推...
最后在arr[0~1]
范围上,重复上面的过程,但最后一步是arr[0]
和arr[1]
,谁大谁来到第一个位置上
示例图

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Code_0003_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);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
|
复杂度分析
- 最优:\(O(n)\)
- 最差:\(O(n^2)\)
插入排序
流程
想让arr[0...0]
上有序,这个范围只有一个数,当然是有序的。
想让arr[0...1]
上有序,所以从arr[1]
开始往前看,如果arr[1] < arr[0]
,就交换。否则什么也不做。
以此类推...
想让arr[0...i]
上有序,所以从arr[i]
开始往前看,arr[i]
这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。
最后一步,
想让arr[0...N-1]
上有序, arr[N-1]
这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。
估算时发现这个算法流程的复杂程度,会因为数据状况的不同而不同。
示例图

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class Code_0002_InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
|
复杂度分析
- 最优:\(O(n)\)
- 最差:\(O(n^2)\)
选择排序
流程
arr[0...N-1]
范围上,找到最小值所在的位置,然后把最小值交换到0位置。
arr[1...N-1]
范围上,找到最小值所在的位置,然后把最小值交换到1位置。
arr[2...N-1]
范围上,找到最小值所在的位置,然后把最小值交换到2位置。
以此类推...
arr[N-1...N-1]
范围上,找到最小值位置,然后把最小值交换到N-1位置。
所以选择排序的时间复杂度为O(N^2)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public class Code_0001_SelectionSort {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
min = arr[j] < arr[min] ? j : min;
}
swap(arr, i, min);
}
}
private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
|
归并排序
采取分治的策略,递归求解

算法基本操作为合并两个最优排序子序列,因此可以通过一次\(n\)轮迭代得到上一层的最优排序父序列。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
package sortdemo;
import java.util.Arrays;
/**
* Created by chengxiao on 2016/12/8.
*/
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
|
复杂度分析
归并排序是利用了二叉树特性的排序,每次基本操作,即合并最优子序列的时间复杂度为\(O(n)\),而完全二叉树深度为\(log2n\),因此算法总的时间复杂度为\(O(n\log n)\)
桶排序
一种利用索引(index)达到存入表中时即自动找到其位置的排序方法,时间复杂度为线性时间\(O(n)\)