排序算法

复习一下排序算法

概览

排序算法 时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 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

# # start子数列开始的起始位置, gap表示间隔

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

归并排序

归并排序是一种递归算法,它持续地将一个列表分成两半进行排序.
20190725102453.png

快速排序

通过一趟排序将要排序的数据分成独立的两部分,其中一部分的数据比另外一部分的所有数据都要小,然后按此方法对这两部分数据分别进行快速排序.

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;
}