常用排序算法

在这里做个记录,将常用的三大排序算法列出来,方便查看复习,算法主要是理清思路,最近在刷leetcode发现自己脑子是有点笨的。 For Java.


冒泡排序

冒泡是我觉得最简单的一个排序算法了,也是我记的最早的一个排序算法。

冒泡,顾名思义,泡泡往上冒,也就是每次都将最大值放在末尾,剩余值继续冒泡。

其时间复杂度为O(n²)。详解:冒泡排序

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 冒泡排序
*
* @param arr
* @return
*/
public static int[] MPSort(int[] arr) {
// 外循环一次就将最大的值放最后
for (int i = 1; i < arr.length; i++) {
// 内循环剩余值比较 找出最大值
for (int j = 0; j < arr.length - i; j++) {
// 比较 满足条件互换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;

}

插入排序

插入排序也是比较好理解的一个排序算法,别看这名字挺粗鲁的,其实它还就那么回事。

插入排序,挨个遍历,发现比前数值还要小的数就把该数前移比较并换值,直到满足的位置为止。

是挺粗鲁的一个算法,不过这很直接,我喜欢。其时间复杂度为O(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
/**
* 插入排序
*
* @param arr
* @return
*/
public static int[] insertSort(int[] arr) {
System.out.println(Arrays.toString(arr));
// j = ++i 保证了i和j两个数一样
for (int i = 0, j = i; i < arr.length - 1; j = ++i) {
int num = arr[i + 1];
// 有较小值就前移并换值
while (arr[j] > num) {
arr[j + 1] = arr[j];
// 使下标递减去比较
if (j-- == 0) {
break;
}
}
// 较小值新赋值
arr[j + 1] = num;

}
return arr;
}

快速排序

快排就是比较经典了,快排是对冒泡的一种改进,由C. A. R. Hoare在1962年提出。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

详解:快速排序

参考代码:

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
/**
* 快速排序
*
* @param arr
* @param lo
* @param hi
* @return
*/
public static int[] quickSort(int[] arr, int lo, int hi) {
if (lo >= hi)
return arr;
int num = partition(arr, lo, hi);
quickSort(arr, lo, num - 1);
quickSort(arr, num + 1, hi);
return arr;
}

/**
* 排序数组 返回基准值
*
* @param arr
* @param lo
* @param hi
* @return
*/
public static int partition(int[] arr, int lo, int hi) {
int num = arr[lo];
if (lo >= hi)
return 0;
while (lo < hi) {
while (hi > lo && arr[hi] >= num) {
hi--;
}
arr[lo] = arr[hi];
while (hi > lo && arr[lo] <= num) {
lo++;
}
arr[hi] = arr[lo];
}
arr[hi] = num;
return hi;
}


End.

文章作者: Folgerjun
文章链接: http://putop.top/2018/08/10/sort-algorithm/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 DoubleFJ の Blog