文章目录
  1. 1. 缘起
  2. 2. 冒泡排序
    1. 2.1. 简单思路描述
    2. 2.2. 代码
  3. 3. 选择排序
    1. 3.1. 简单思路描述
    2. 3.2. 代码
  4. 4. 插入排序
    1. 4.1. 简单描述
    2. 4.2. 代码
  5. 5. 快速排序
    1. 5.1. 简单描述
    2. 5.2. 代码
  6. 6. 归并排序
    1. 6.1. 简单描述
    2. 6.2. 代码
  7. 7. 碎碎念

一些常见的排序算法总结,为了防止自己哪天忘了可以回顾下,算法代码都用C语言来写,毕竟自己学的第一门语言。

缘起

这几个月面试了三四家公司,其中第一家

面试官:知道有哪些排序算法吗
我:嗯,冒泡,插入,选择,快排,归并,桶排
面试官:恩好,下一题
我:。。。。

如果他面试官按照常理出牌说说一下某某排序的具体思路,这就好玩了,因为有一半的我不会!!我在给自己挖坑,结果还没坑到自己。

还有一次面试

面试官:解释一下冒泡算法
我:%&¥%#……×&%%¥%¥
面试官:额。。。恩。。。。下一题。

结果证明我知道的排序算法都能解释的非常模糊,等于没讲,所以就整理一下思路,省的以后面试还是解释不清楚

为了方便说明,现在有一个数组arr,长度为n,然后按照从小到大进行排序

冒泡排序

该冒泡算法的时间复杂度是O(n2)

简单思路描述

首先arr[0]与arr[1]比较,如果arr[0]大于arr[1]则两者交换,否则不动,然后比较arr[1]与arr[2],如果arr[1]大于arr[2]则两者交换,否则不动,以此类推,直到arr[n-1]与arr[n]比较处理完,此时最大的数就像冒泡泡那样移到arr[n]。此时第一轮循环结束,然后以此类推第二轮循环找出最大的移动arr[n-1]的位子,然后以此类推不断将最大的往后挪。

也就是说不断的访问要排序的数列,每次比较两个元素,如果这两个元素排列错误则交换过来,这样大的元素就慢慢移到后面。

图片摘自维基百科

代码

1
2
3
4
5
6
7
8
9
10
11
12
void bubble_sort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

选择排序

选择排序的时间复杂度和冒泡排序一样都是O(n2)

简单思路描述

首先,找到数组中最小的,并将它与第一个交换,然后找到扫一遍找到第二个最小的,并将它与第二个数交换,然后以此类推数组就排序好了

也就是说在未排序的序列中找到最小的元素,放到起始位子,然后在剩余未排序的选取最小的元素,放到排好序列的最后,这样以此类推就排好了。

图片摘自维基百科

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(int arr[], int n) {
int i, j, min, temp;
for (i = 0; i < n; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}

插入排序

插入排序的时间复杂度也是O(n2)

排序,插入,还有冒泡,这三种算法是我最熟悉的,因为当初大一学C语言的时候,这三种排序考试必考,不会也得会啊。当然相应的也是最简单的排序方法,所以从时间复杂度来讲也是最耗时的=。=

简单描述

首先看arr[1]与arr[0]的大小关系,将两者的顺序从小到大排序,这样从arr[0]到arr[1]是排好的,然后将arr[2]插入到arr[0]到arr[1]这序列中,使arr[0]到arr[2]是有序的序列,然后是arr[4]插入进来,以此类推就成了有序的序列。

也就是说通过构建有序序列,对于位排序的数据在已排序中进行扫描,找到相应的位子插进去。

图片摘自维基百科

代码

1
2
3
4
5
6
7
8
9
10
void insertion_sort(int arr[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
for (j = i-1; j >= 0 && arr[j] > arr[j+1]; j--) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

快速排序

个人感觉最重要的排序就是排序,然而现在才开始学习实在是惭愧=。=

时间复杂度为O(n*logn),而且该算法在同为O(n*logn)的几种排序算法中效率更高。

简单描述

从大体上来说,该算法采用的是分治法的思想。详细步骤如下:

1、从序列中挑选出一个基准,可以是第一个,也可以是最后一个,也可以是中间的,这里以取最后一个为例。
2、重新排列序列,将比基准大的放一边,比基准小的放另一边,这样基准就处于两边的中间位子。以最后一个为基准的话,首尾指针双管齐下,首先通过首指针往后扫描找到比基准大的,然后将其移到尾指针的位置,然后尾指针往前扫描直至找到比基准小的,将其移到首指针处,如此下去直至首尾指针相遇,此时首尾指针处就是基准存放的地方。更为详细白话的介绍戳这里
3、然后对左右分区重复上述1、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
36
37
38
39
void quick_sort_recurse(int arr[], int start, int end) {
int flag, left, right, i;
if (start >= end) return;

srand((unsigned)time(NULL));
i = rand()%(end-start) + start;
flag = arr[i]; //flag选取随机数,避免O(n<sup>2</sup>)的最坏情况

/*将选取的随机数与最后一个交换*/
i = arr[end];
arr[end] = flag;
flag = i;

left = start;
right = end;
while (left < right) {
while (left < right && arr[left] <= flag) {
left++;
}
if (left < right) {
arr[right] = arr[left];
right--;
}
while (left < right && arr[right] >= flag) {
right--;
}
if (left < right) {
arr[left] = arr[right];
left++;
}
}
arr[left] = flag;
quick_sort_recurse(arr, start, left-1);
quick_sort_recurse(arr, left+1, end);
}

void quick_sort(int arr[], int n) {
quick_sort_recurse(arr, 0, n-1);
}

归并排序

时间复杂度同样为O(n*logn),该算法的效率也是非常不错的,只不过相比于快排,需要额外的存储空间。

简单描述

该算法也是典型的采用分治法。其思想简单的描述就是将排序好的两个序列合并成一个序列,要得到排序好的序列,就需要不断的将序列再平分,直至序列里面只有一个数字,此时序列肯定是有序的,然后再不断的合并上去,直至合并成一个有序的序列。

所以该算法的核心也就是如何有效的合并两个序列,由于序列是有序的,所以只要安排两个指向他们首部的指针,然后看两个指针指向的内容哪个小就取出来存在临时的序列中,并且指针向后移,然后接着比较两个指针指向的内容,直至某个指针指到末尾,然后另个序列的余下内容再接着补上。

图片摘自维基百科

代码

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
void merge_sort_recurse(int arr[], int temp[], int start, int end) {
int mid, left, right, merge;
if (start >= end) return;

mid = (end-start) / 2 + start;
merge_sort_recurse(arr, temp, start, mid);
merge_sort_recurse(arr, temp, mid+1, end);
left = merge = start;
right = mid+1;

while (left <= mid && right <= end)
temp[merge++] = (arr[left] < arr[right]) ? arr[left++] : arr[right++];

while (left <= mid)
temp[merge++] = arr[left++];

while (right <= end)
temp[merge++] = arr[right++];

for (merge = start; merge <= end; merge++)
arr[merge] = temp[merge];
}

void merge_sort(int arr[], const int n) {
int temp[n];
merge_sort_recurse(arr, temp, 0, n-1);
}

碎碎念

以上则是比较常用的排序算法,祝自己找到好的实习T_T

The End~

文章目录
  1. 1. 缘起
  2. 2. 冒泡排序
    1. 2.1. 简单思路描述
    2. 2.2. 代码
  3. 3. 选择排序
    1. 3.1. 简单思路描述
    2. 3.2. 代码
  4. 4. 插入排序
    1. 4.1. 简单描述
    2. 4.2. 代码
  5. 5. 快速排序
    1. 5.1. 简单描述
    2. 5.2. 代码
  6. 6. 归并排序
    1. 6.1. 简单描述
    2. 6.2. 代码
  7. 7. 碎碎念