排序算法

排序算法是最基本最常用的算法,是算法与数据结构的基础,也是面试中常见的一类问题。

插入排序 Insertion sort

插入排序方法类似于我们整理手上的扑克牌,在数据量小的时候是一种高效的的排序算法。

插入排序通常只需要用到O(1)的额外空间:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

伪代码

升序

示例代码

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(vector<int> &a) {
for(int j = 1;j<a.size();j++) {
int key = a[j];
int i = j - 1;
while (i>=0 && a[i]>key) {
a[i+1] = a[i];
i-- ;
}
a[i+1] = key;
}
}

归并排序

归并排序是分治法的一个实现:

Divide: 把长度为n的序列分成两个长度为n/2的子序列

Conquer:递归的使用归并排序将子序列排序

Combine:将两个排好序的子序列合并成一个序列

伪代码:

归并操作:

例如上图所示,归并操作将A分成L和R两个数组,然后根据每个元素的大小依次将元素重新填入到A中。

归并排序:

代码

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
//C++
void merage(vector<int> &A,int p, int q, int r) {
int n1 = q - p +1;
int n2 = r - q;
vector<int> L(n1+1), R(n2+1);
for (int i = 0; i < n1; i++) {
L[i] = A[p+i-1];
}
for (int j = 0; j < n2; j++) {
R[j] = A[q + j];
}

L[n1+1] = INT_MAX;
R[n1+1] = INT_MAX;
int i = 0;
int j = 0;

for(int k = p;k<r;k++) {
if(L[i]<=R[j]) {
A[k] = L[i];
i++;
}
else {
A[k] = R[j];
j++;
}

}
}

void merage_sort(vector<int> &A,int p, int r) {
if (p<r) {
int q = int((p+r-0.5)/2);
merage_sort(A, p, q);
merage_sort(A, q+1, r);
merage(A, p, q, r);
}
}

冒泡排序

冒泡排序是一种简单的排序方法,通过重复的走访需要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

冒泡排序的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

伪代码

代码

1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int> &a) {
for (int i = 0; i<a.size(); i++) {
for(int j = a.size()-1;j>i+1;j--) {
if (a[i]>a[j]) {
swap(a[i], a[j]);
}
}
}
}

参考资料:

Introduction to Algorithms Thomas H. Cormen

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

打赏