复习一下排序算法
概览
| 排序算法 |
时间复杂度 |
最好情况 |
最坏情况 |
空间复杂度 |
排序方式 |
稳定性 |
| 冒泡排序 |
O(n2) |
O(n) |
O(n2) |
O(1) |
in-place |
稳定 |
| 选择排序 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
in-place |
不稳定 |
| 插入排序 |
O(n2) |
O(n) |
O(n2) |
O(1) |
in-place |
稳定 |
| 希尔排序 |
O(nlogn) |
O(nlongn) |
O(nlogn) |
O(1) |
in-place |
不稳定 |
| 归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
out-place |
稳定 |
| 快速排序 |
O(nlogn) |
O(nlogn) |
O(n2) |
O(logn) |
in-place |
不稳定 |
| 堆排序 |
O(n logn) |
O(n logn) |
O(n logn) |
O(1) |
in-place |
不稳定 |
| 计数排序 |
O(n + k) |
O(n + k) |
O(n + k) |
O(k) |
out-place |
稳定 |
| 桶排序 |
O(n + k) |
O(n + k) |
O(n2) |
O(n + k) |
out-place |
稳定 |
| 基数排序 |
O(n * k) |
O(n * k) |
O(n * k) |
O(n + k) |
out-place |
稳定 |
冒泡排序
冒泡排序对数组进行两层遍历,每一步比较相邻的两项,如果这两项排序错了则对其进行交换
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void bubble(int[] arr) {
int temp;
int len = arr.length;
for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
|
评价
冒泡排序通常被认为是最低效的排序方法
但是冒泡排序如果在某次遍历中发现没有交换值,就可以提前结束
优化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static void bubbleEnhance(int[] arr) {
int temp;
int len = arr.length;
boolean changed;
for (int i = len - 1; i >= 0; i--) {
changed = false;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
changed = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if(!changed){
break;
}
}
}
|
选择排序
选择排序对数组进行两层遍历,每次遍历找到最小的项,遍历完成后再把最小的项放到正确的位置
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static void selection(int[] arr){
int temp,currentMinIndex;
int len = arr.length;
for(int i = 0; i < len - 1; i++){
currentMinIndex = i;
for(int j = i + 1; j < len; j++){
if(arr[currentMinIndex] > arr[j]){
currentMinIndex = j;
}
}
temp = arr[currentMinIndex];
arr[currentMinIndex] = arr[i];
arr[i] = temp;
}
}
|
插入排序
插入排序总是保持一个位置靠前的以排好的子表,然后每一个新数据项被插入到前边的子表里
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static void insertion(int[] arr) {
int currentValue, position;
int len = arr.length;
for (int i = 1; i < len; i++) {
currentValue = arr[i];
position = i;
while (position > 0 && currentValue < arr[position - 1]) {
arr[position] = arr[position - 1];
position -= 1;
}
arr[position] = currentValue;
}
}
|
希尔排序
希尔排序又叫"缩小间隔排序",它以插入排序为基础,将原来要排序的列表划分为一些字列表,再对每一个子列表执行插入排序
划分子列表的方法是希尔排序的关键.我们并不是将原始列表分成含有连续元素的子列,而是确定一个特别的分量"i",这个i更准确地说是划分的间隔.然后把每间隔为i的所有元素选出来组成子列表,然后对每个子序列进行插入排序,最后当i=1时,对整体进行一次插入排序
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def shellSort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap):
gapInsetionSort(alist, i, gap)
gap = gap // 2
return alist
def gapInsetionSort(alist,startpos,gap):
for i in range(startpos+gap,len(alist),gap):
position=i
currentvalue=alist[i]
while position>startpos and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position=position-gap
alist[position]=currentvalue
|
归并排序
归并排序是一种递归算法,它持续地将一个列表分成两半进行排序.
快速排序
通过一趟排序将要排序的数据分成独立的两部分,其中一部分的数据比另外一部分的所有数据都要小,然后按此方法对这两部分数据分别进行快速排序.
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
| public void quickSort(int[] arr, int start, int end){
if(end <= start){
return;
}
int p = partition(arr, start, end);
quickSort(arr,start,p - 1);
quickSort(arr,p + 1,end);
}
public int partition(int[] arr, int start, int end) {
System.out.println("============↓↓↓开始执行↓↓↓=============");
System.out.println("本次执行数组: " + Arrays.toString(Arrays.copyOfRange(arr,start,end)));
float pos = r.nextFloat();
int posInt = (int) (pos * (end - start) + start);
int tmp = arr[posInt];
System.out.println("本次选定基准: arr[" + (posInt - start) + "] = " + tmp);
arr[posInt] = arr[start];
arr[start] = tmp;
int pivot = arr[start];
int j = start;
int i = start + 1;
while (i < end) {
if (arr[i] <= pivot) {
tmp = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tmp;
j += 1;
}
i += 1;
}
tmp = arr[j];
arr[j] = arr[start];
arr[start] = tmp;
System.out.println("本次执行完事后数组: " + Arrays.toString(Arrays.copyOfRange(arr,start,end)));
return j;
}
|