1. 排序的种类
  2. 时间频度和特点
  3. 时间复杂度
  4. 冒泡排序
  5. 选择排序
  6. 插入排序
  7. 希尔排序
  8. 快速排序
  9. 归并排序
  10. 基数排序
  11. 堆排序

以下只给出思路与关键方法,算法的源代码放在了git中,需要的自取

leidl97/algorithm-src

排序的种类

排序分为内部排序外部排序

一般为内部排序,可以划分为8大排序

插入排序:直接插入 | 希尔排序

选择排序:简单选择 | 堆排序

交换排序:冒泡排序 | 快速排序

归并排序(分治算法)

基数排序(桶排序)

时间频度和特点

1、常数项可以忽略

2、低次方项可以忽略

3、次方项的系数可以忽略

时间复杂度

1、一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大的时候,T(n) / f(n)的极限值为不等于0的常数,则称f(n)是T(n)的同数量级函数,记作T(n) = O(f(n)), O(f(n))称为算法的渐进时间复杂度,简称时间复杂度

2、T(n)不同,但时间复杂度可能相同

计算方法

用常数1表示运行中所有加法常数

只保留最高阶项

去掉最高阶的系数

常用的时间复杂度

由小到大

常数阶O(1):没有循环等复杂结构

对数阶O(log2n):if(i < n)一直循环 i = i * 2,n多大执行log2n遍,也就是说2^次数=n,次数=log2n

线性阶O(n):i++或者一层for循环,都是一个意思,n多大执行多少遍

线性对数阶O(nlog2n):for循环中套了一个对数阶

平方阶O(n^2):两层for循环

立方阶O(n^3):三层for循环

k次方阶O(n^k):n层for循环

指数阶O(2^n):

img

图片来源于网络

冒泡排序

思想:两个for循环,比数组大小-1次,每次比较数组大小-1次,从数组的第一个数字开始与下一个比较,如果第一个比第二个大则交换,否则第二个跟第三个比较

img

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//冒泡排序
public static void sort(int[] a) {
//只能用于判断趟数,省趟数,不省次数
boolean flag = true;
for (int i = 0; i < a.length - 1; i++) {
//排序n - 1趟
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j+1]) {
swag(a,j,j+1);
flag = false;
}
}
if (flag) {
break;
} else {
//不重置只要交换过就没用了
flag = true;
}
}
}

选择排序

思想

将数组中的数据遍历,先拿第一个进行比较,看后面的有没有比这更小的,有的话交换,没有就第二个进行比,依次比较,一共需要比数组大小-1次

img

代码实现

1
2
3
4
5
6
7
8
9
10
private static void sort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
for (int j = i; j < a.length-1; j++) {
if (a[j+1] < a[i]) {
//交换两数
swag(a,i,j+1);
}
}
}
}

插入排序

思想:将一个数组中的数据看作两个数组,有序和无序数组,由于第一个无需比较,所以需要比n-1次,将无需数组的第一个与有序数组的最后一个依次对比,并且插入合适的位置

一个for循环,一个while解决

初始为数组的第二个元素,依次与前面的比较,如果小的话一直比,直到遇到大的,则将找到的该元素后移,将比较的元素插入找到元素的后面,一轮结束,一共需要数组大小-1轮比较

img

图片来源于网络

代码实现

1
2
3
4
5
6
7
8
9
10
11
private static void sort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
int arr = a[i+1];
int index = i;
while (index >= 0 && arr < a[index]) {
a[index + 1] = a[index];
index--;
}
a[index+1] = arr;
}
}

希尔排序

如果存在一个数组为{2,3,4,5,6,1}那么使用插入排序会导致算法效率很慢

所以说是对插入排序的一种优化,它是分组对每组进行排序,又叫做缩小增量排序

img

图片来源于网络

为什么希尔排序效率更高

由于开始时,步长的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期步长取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。就是判断的多了,移动的次数变少,所以速度变快。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void shellSort(int[] a) {
int count = 0;
for (int gap = a.length /2; gap > 0; gap /= 2) {
for (int i = gap; i < a.length; i++) {
int index = i;
int arr = a[index];
if (arr < a[index-gap]) {
while (index - gap >= 0 && arr < a[index-gap]) {
count ++ ;
a[index] = a[index-gap];
index-=gap;
}
a[index] = arr;
}
}
}
System.out.println("一共:"+count+"次");
}
int[] a = {4,3,5,2,1,9,8,10,7,6};

同样的数组,用插入需要16次,用希尔只需要8次

快速排序

特点就是递归,通过一个中间数,将该数的左右分别排序好,先找一个基准值,一般为数组大小/2,左边找到一个比基准值大的数,右边找到一个比基准值小的数,然后进行交换,算完之后左边的都为比基准值小的,右边都为比基准值大的,但不能保证他们是有序的,所以还需要对左右生成的数据进行二次排序

img

代码实现

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
private static void sort(int left, int right, int[] arr) {
int l = left;
int r = right;
int center = arr[(l+r)/2];
int temp = 0;

while (l < r) {
while (arr[l] < center) {
l += 1;
}

while (arr[r] > center) {
r -= 1;
}

if (l >= r) {
break;
}

//交换顺序,指针改变
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;

l+=1;
r-=1;
}

if (l == r) {
l+=1;
r-=1;
}

if (left < r) {
sort(left,r,arr);
}

if (right > l) {
sort(l,right,arr);
}
}
}

归并排序

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

img

分而治之

img

图片来源网络

img

图片来源网络

思想

先将数组中的一组数据进行划分,最后去比较划分好的数据然后逐级比较合并

代码实现

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
private static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
//左归并
sort(arr, left, mid);
//右归并
sort(arr, mid + 1, right);
//归并计算
merge(arr, left, mid, right);
}
}

private static void merge(int[] arr, int left, int mid, int right) {
count ++ ;
int i = left;
int j = mid + 1;
int[] temp = new int[right-left+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[t++] = arr[i++];
}

while (j <= right) {
temp[t++] = arr[j++];
}

//将temp的数据放入arr中
t = 0;
while (t < temp.length) {
arr[left++] = temp[t++];
}
}
}

基数排序

img

img

图片来源于网络

难点

1、取数组内最大数字的位数

2、求次方

3、求本次遍历应该取个位还是什么位,如何取

4、桶应该如何创建

代码实现

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
private static void sort(int[] arr) {
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int size = (max + "").length();
/**
* size表示循环的次数,根据最大数的位数决定,n表示当前应该取哪一位数,n为1的时候表示取个位
* n为10表示取百位,以此类推,每次遍历都创建一个length*10的桶,保证数据不会出错
* 存的时候是按照行列存储的,但取得时候按照列行取(按照人的思维)
*/
for (int k = 0, n = 1; k < size; k++, n *= 10) {
//创建一个二维数组用来表示放置的桶
int[][] bucket = new int[arr.length][10];
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
int gewei = temp / n % 10;
bucket[i][gewei] = temp;
}
int t = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < arr.length; j++){
if (bucket[j][i] != 0) {
arr[t++] = bucket[j][i];
}
}
}
System.out.println(Arrays.toString(arr));
}
}

堆排序(用顺序存储二叉树的思想进行排序)

相关概念

堆这种数据结构是一种排序算法,堆排序是一种选择排序,它的最坏最好,平均复杂度均未nlogn,为不稳定排序

大顶堆:每个结点的值都大于等于他的左右孩子结点的值,比如下图

img

小顶堆:相反,每个结点的值都小于等于他的左右孩子结点的值,比如下图

img

大小是对于顶点来说的,一般大顶堆做升序,小顶堆做降序

堆排序思想

如果是升序,也就是从小到大排,那么就需要构建大顶堆,然后想根节点元素与最后一个叶子进行交换,重复除了已经筛选好的叶子节点这个过程

也可以说将数组按照树的思想进行排序。树只是一个逻辑上的概念

步骤,刚开始如下图

img

1、首先找到第一个非叶子节点,公式 a.length / 2 - 1,将叶子结点大的值进行交换

img

2、然后在找到下一个非叶子节点重复1的操作

img

3、排完在返回来进行之前左子树的排序,因为结构已经混乱(程序不用递归怎么回来的,在上一步已经做了遍历操作,可以看作23是一起的)

img

4、最后形成一个大顶堆,将堆顶元素与最后一个叶子节点交换值,除去该值,继续重复上面的过程

img

5、重新调整结构,继续构建大顶堆

img

6、重复进行

img

难点

1、构建大顶堆 / 构建小堆顶

2、边界值判断

自己思路写出的代码如下,完了思考这个复杂度怎么都上n2了啊

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
public class HeapSort {
public static void main(String[] args) {
int[] a = {4,6,8,5,9};
System.out.println("排序前:"+ Arrays.toString(a));
sort(a);
System.out.println("排序后:"+ Arrays.toString(a));
}

/**
* 构建大顶堆(升序)
* @param a 待处理的数组
* @param i 待处理非叶子节点
* @param length 待处理数组的长度
*/
private static void heapSort(int[] a, int i, int length) {
while (i >= 0) {
//从该节点的索引下进行调整,将i节点之下构建为一个大顶堆
for (int j = 2 * i + 1; j <= length; j = j * 2 + 1) {
//此时j为左子树
if (j+1 <= length && a[j] < a[j+1]) {
//若左子树大于右子树,则挪动指针,指向右子树
j++;
}
if (a[i] < a[j]) {
//将大元素放置顶堆
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
i--;
}
}

private static void sort(int[] a) {
//构建大顶堆
for (int length = a.length - 1; length > 0; length--) {
heapSort(a, length / 2 - 1, length);
//将堆顶堆底元素互换
int temp = a[0];
a[0] = a[length];
a[length] = temp;
}
}
}

改进版(逻辑上更好理解了,老师的思路,但复杂度我觉得没有达到nlogn)

1、先构建大顶堆,然后在进行堆顶元素的顺序调整,一个需要遍历数组个数-1次,剩下那个自动就是有序的,所以为for (int j = a.length; j > 1; j–) {}

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
26
27
28
29
30
31
32
33
34
35
private static void adjustSort(int[] a) {
//构建大顶堆
for (int j = a.length; j > 1; j--) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
adjustHeap(a, i, j);
}
//将堆顶元素与堆底互换
int temp = a[0];
a[0] = a[j - 1];
a[j - 1] = temp;
}
}

/**
* 构建大顶堆(升序)
* @param a 待处理的数组
* @param i 待处理非叶子节点
* @param length 待处理数组的长度
*/
private static void adjustHeap(int[] a, int i, int length) {
int temp = a[i];
for (int k = 2 * i + 1; k < length; k = 2 * i + 1) {
if (k + 1 < length && a[k] < a[k+1]) {
k++;
}
if (a[k] > temp) {
a[i] = a[k];
i = k;
} else {
//如果当前节点不大于索引节点,那么大顶堆已形成,因为是从下之上的
break;
}
}
a[i] = temp;
}