数据结构之排序算法

总结常用的排序算法。

排序算法比较

排序算法

tips:归并排序的空间辅助空间为O(n)
tips:希尔排序的平均时间复杂度为O(nlogn)


插入排序

插入排序

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


冒泡排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSort(vector<int> &A) {
int flag = true;
int n = A.size();
for (int i=0; i<n-1; ++i) {
for (int j=1; j<n-i; ++j) {
if (A[j] < A[j-1]) {
swap(A[j], A[j-1]);
flag = false;
}
}
if (flag) {
break;
}
}
}


选择排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectSort(vector<int> &A) {
int n = A.size();
for (int i=0; i<n-1; ++i) {
int min = i;
for (int j=i+1; j<n; ++j) {
if (A[j] < A[min]) {
min = j;
}
}
if (min != i) {
swap(A[i], A[min]);
}
}
}


归并排序

归并排序

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
void mergeSort(vector<int> &A, int start, int end) {
if (start >= end) {
return;
}
int mid = start + ((end - start) >> 1);
mergeSort(A, start, mid);
mergeSort(A, mid + 1, end);
merge(A, start, mid, end);
}
void merge(vector<int> &A, int start, int mid, int end) {
vector<int> res;
int i = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (A[i] <= A[j]) {
res.push_back(A[i]);
++i;
} else {
res.push_back(A[j]);
++j;
}
}
while (i <= mid) {
res.push_back(A[i]);
++i;
}
while (j <= end) {
res.push_back(A[j]);
++j;
}
for (int k=start; k<=end; ++k) {
A[k] = res[k-start];
}
}

希尔排序

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void ShellSort(int arr[], int n) {
if (arr == NULL || n == 0) return;
if (n == 1) return;
int gap = n >> 1;
while (gap > 0) {
for (int i=gap; i<n; ++i)
for (int j=i; j-gap>=0; j-=gap)
if (arr[j-gap] > arr[j])
swap(arr[j-gap], arr[j]);
gap >>= 1;
}
}


快速排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void quickSort(vector<int> &A, int start, int end) {
if (start >= end) {
return;
}
int left = start;
int right = end;
int pivot = A[left];
while (left < right) {
while (left < right && A[right] >= pivot) {
--right;
}
A[left] = A[right];
while (left < right && A[left] <= pivot) {
++left;
}
A[right] = A[left];
}
A[left] = pivot;
quickSort(A, start, left - 1);
quickSort(A, left + 1, end);
}


堆排序

堆排序

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
void heapSort(vector<int> &A) {
int n = A.size();
for (int i=n/2; i>=0; --i) {
heapify(A, i, n - 1);
}
for (int i=n-1; i>0; --i) {
swap(A[i], A[0]);
heapify(A, 0, i - 1);
}
}
void heapify(vector<int> &A, int start, int end) {
int parent = start;
int child = 2 * parent + 1;
while (child <= end) {
int right = child + 1;
if (right <= end) {
child = (A[child] >= A[right] ? child : right);
}
if (A[parent] >= A[child]) {
return;
}
swap(A[parent], A[child]);
parent = child;
child = 2 * parent + 1;
}
}

参考资料:
Insertion sort
Bubble sort
Selection sort
Merge sort
Shellsort
Heapsort
常见排序算法C++总结