Sort

排序

时间复杂度、稳定性等

算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(1) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
希尔排序 O(n^1.3) O(n^2) O(n) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(n^2) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

冒泡排序

冒泡排序的原理是依次比较两个相邻的数,将较小的数放在前面,即每次的流程为,第一趟,比较第1个和第2个数,较小的放在前面,然后比较第2个和第3个,将较小的放在前面,直至最后两个元素。因此第一趟的过程的结果是将所有数中最大的那个数交换到了数组的最后一个位置。因此随后可以利用上述过程对除最后一个元素外的剩余元素进行排序,直到所有元素均有序。

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

选择排序

选择排序的原理是每次从待排序的记录中选择最大的元素再与待排序的最后一个元素进行交换,然后对剩余元素再进行选择排序,直到所有元素均有序。

1
2
3
4
5
6
7
8
9
10
11
12
void selectionSort(std::vector<int> & data) {
for (int end=data.size()-1; end>0; end--) {
int max = 0;
for (int i=1; i<=end; i++) {
if (data[i]>data[max]) {
max = i;
}
}
std::swap(data[max],data[end]);
}
return;
}

插入排序

插入排序的原理是当仅有一个数字时必定是有序的,随后的过程中每次将一个新的元素插入已有序列中并保证这个序列是有序的,直到序列中的所有元素均是有序的。

1
2
3
4
5
6
7
8
9
10
void insertSort(std::vector<int> & data) {
for (int current=1,sz=data.size(); current<sz; current++) {
for (int i=current; i>0; i--) {
if (data[i]<data[i-1]) {
std::swap(data[i], data[i-1]);
}
}
}
return;
}

希尔排序

希尔排序其实也是插入排序,不过相比与简单插入排序,其效率会更好一点。其原理是将记录按照一定的下标的一定增量进行分组,然后对每组均使用插入排序进行排序,随着增量的减少,每组所包含的数据会逐渐增多,最后一次进行插入排序时增量为1,最后所有元素均有序。其思想是每次保证数据先较为有序的分布,从而减少随后的插入排序的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void shellSortAux(std::vector<int> & data, int gap) {
for (int start=0; start<gap; start++) {
for (int end=start+gap,sz=data.size(); end<sz; end+=gap) {
for (int current=end; current>start; current-=gap) {
if (data[current]<data[current-gap]) {
std::swap(data[current], data[current-gap]);
}
}
}
}
return;
}

void shellSort(std::vector<int> & data) {
for (int gap=data.size()/2; gap>=1; gap/=2) {
shellSortAux(data, gap);
}
return;
}

堆排序

堆是一种特殊的完全二叉树,它的特点时其父节点比其两个子节点都要大。在利用堆进行排序时,每次均会取堆顶的元素,之后将堆顶的元素与最后一个元素进行交换,将堆的大小缩小1,之后由于堆顶元素进行了变更,因此可能违反了堆的性质,因此需要利用heapify来维护堆的性质,这样一直重复,知道堆的大小变为0,此时数组的内容即为有序的。

heapify:该函数接受一个数组和一个下标,并假设该下标所代表根节点的左子树和右子树均为最大堆,但此时该下标所代表元素可能小于其子节点,此时需要将该节点的元素进行下降到合适的位置,从而使下标所指的树维持最大堆的性质。

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
void heapify(std::vector<int> & data, int index, int sz) {
int current = index;
for (; current<sz;) {
int left = current*2;
int right = left+1;
int max = current;
if (left<sz && data.at(left)>data.at(max)) {
max = left;
}
if (right<sz && data.at(right)>data.at(max)) {
max = right;
}

if (max == current) {
break;
} else {
std::swap(data.at(max), data.at(current));
current = max;
}
}
}

void buildHeap(std::vector<int> & data) {
for (int i=data.size()/2; i>0; i--) {
heapify(data, i, data.size());
}
}

void heapSort(std::vector<int> & data) {
for (int i=data.size()-1; i>1; i--) {
std::swap(data.at(i), data.at(1));
heapify(data, 1, i);
}
}

快速排序

快速排序的思想是每次选择一个元素作为枢纽值,将所有小于等于该枢纽的元素划到该元素左半边,大于等于该枢纽的元素划到该元素的右半边,然后分别对这两边分别递归调用快速排序,从而最终保证整个序列有序。

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
int partition(std::vector<int> & data, int l, int r) {
int left = l;
int right = r;
int pivot = data.at(r);

for (; left<right; ) {
for(; left<right && data[left]<=pivot; left++);
for(; left<right && data[right]>=pivot; right--);

std::swap(data.at(left), data.at(right));
}
std::swap(data.at(r), data.at(left));
return left;
}

int partition2(std::vector<int> & data, int l, int r) {
int pivot = data[r];
int pre = l-1;
int cur = l;
for (; cur<r; cur++) {
if (data[cur] <= pivot) {
pre++;
std::swap(data.at(pre), data.at(cur));
}
}
std::swap(data.at(pre+1), data.at(r));
return pre+1;
}

void quickSort(std::vector<int> & data, int l, int r) {
if (l < r) {
int mid = partition(data, l, r);
quickSort(data, l, mid-1);
quickSort(data, mid+1, r);
}
}

归并排序

归并排序使用的是分治思想,通过将问题分解为多个范围更小但形式相同的问题进行求解,在求解完子问题后再将问题求解的结果进行合并获取整个问题的解。归并排序每次将数据分为两个子数组,首先利用归并排序将两个子数组排列至有序,之后将两个有序的子数组利用归并来合并为一个有序的数组,如果两个子数组的大小为0或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
25
26
27
28
29
30
void merge(std::vector<int> & data, int l, int mid, int r, std::vector<int> & buffer) {
int l1 = l;
int l2 = mid+1;
int cur = l;
for (; l1<=mid || l2<=r; cur++) {
int * pcur = nullptr;
if (l1 > mid) {
pcur = &l2;
} else if (l2 > r) {
pcur = &l1;
} else {
pcur = (data.at(l1)<data.at(l2) ? &l1:&l2);
}

buffer.at(cur) = data.at(*pcur);
(*pcur)++;
}
for (int i=l; i<=r; i++) {
data[i] = buffer[i];
}
}

void mergeSort(std::vector<int> & data, int l, int r, std::vector<int> & buffer) {
if (l < r) {
int mid = (l+r)/2;
mergeSort(data, l, mid, buffer);
mergeSort(data, mid+1, r, buffer);
merge(data, l, mid, r, buffer);
}
}

链表的排序

链表的插入排序:

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* linkedListInsertionSort(ListNode * head) {
for (ListNode * current=head; current!=NULL; current=current->next) {
int lastValue = current->val;
for (ListNode * i=head; i!=current; i=i->next) {
if (i->val >= current->val) {
std::swap(i->val, lastValue);
}
}
current->val = lastValue;
}
return head;
}

链表的归并排序:

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
ListNode * merge(ListNode * lhs, ListNode * rhs) {
ListNode * tail = NULL;
ListNode * head = NULL;
for (; lhs != NULL && rhs != NULL; ) {
ListNode * & current = (lhs->val < rhs->val ? lhs:rhs);
if (tail == NULL) {
tail = current;
head = current;
} else {
tail->next = current;
tail = current;
}
current = current->next;
}

ListNode * remain = (lhs == NULL ? rhs:lhs);
if (remain != NULL) {
if (tail == NULL) {
head = remain;
} else {
tail->next = remain;
}
}
return head;
}

ListNode * linkedListMergeSort(ListNode * head) {
if (head == NULL || head->next == NULL) {
return head;
}

ListNode * slow = head;
ListNode * fast = head;

for (; fast->next != NULL && fast->next->next != NULL;) {
fast = fast->next->next;
slow = slow->next;
}


ListNode * r = linkedListMergeSort(slow->next);
slow->next = NULL;
ListNode * l = linkedListMergeSort(head);
return merge(l, r);
}

链表的快速排序:这里使用的Partition函数仅需单向遍历链表

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
ListNode * partition(ListNode * begin, ListNode * end) {
ListNode * prev = begin;
int pivot = begin->val;
for (ListNode * current=begin->next; current!=end; current=current->next) {
if (current->val < pivot) {
prev = prev->next;
std::swap(prev->val, current->val);
}
}
std::swap(prev->val, begin->val);
return prev;
}

// [)
void linkedListQuickSortAux(ListNode * begin, ListNode * end) {
if (begin == end) {
return;
}
ListNode * mid = partition(begin, end);
linkedListQuickSortAux(begin, mid);
linkedListQuickSortAux(mid->next, end);
}

ListNode * linkedListQuickSort(ListNode * head) {
linkedListQuickSortAux(head, NULL);
return head;
}

引用

https://www.cnblogs.com/onepixel/articles/7674659.html
https://www.cnblogs.com/TenosDoIt/p/3666585.html