未分类

【分治策略】归并排序算法总结

数据结构与算法

归并排序思想

归并排序的思想很简单，拿到一个无序的序列，先从序列的中间位置将其切分成两个子序列，然后对两个子序列递归地进行归并排序，最后，将排好序的子序列合并成一个完整的有序序列。归并排序算法的伪代码如下：

1
2
3
4
5
6
序列seq = [s1, s1, s3, ..., sn]
归并排序：
  将seq切分成两个部分seq1, seq2;
  对seq1进行归并排序;
  对seq2进行归并排序;
  把seq1和seq1合并称为一个完整的序列seq;

数组归并排序

对数组进行归并排序，需要开一个临时数组以便合并时可以使用。在普通的数组归并排序实现中，空间开销可能会达到O(nlogn)或者更差的复杂度，这里介绍另外一种方式，在O(n)的空间开销内完成数组的归并排序。C++代码实现如下所示，以下面代码为例，在归并排序时，开了两个数组arr和tmp，通过不断交换两个数组来实现空间的高效利用。假如归并当前这一层需要将元素存在arr中，那么下一层就反过来将元素存在tmp中，就这样不断轮替，就不用再每一层的合并操作里都开临时数组去辅助实现。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;

class SortingArray {
public:
  SortingArray(const int& size): size(size) {
    entry = new int[size];
  }
  ~SortingArray() {
    if (entry != NULL) {
      delete [] entry;
    }
  }
  int operator[](int i) const { return entry[i%size]; }
  int& operator[](int i) { return entry[i%size]; }
  void sort() {
    int* tmp = new int[size]; // 临时数组
    mergeSort(entry, tmp, 0, size-1, true);
    delete [] tmp;
  }
private:
  void mergeSort(int* arr, int* tmp, int beg, int end, bool inArr) {
    if (beg < end) {
      int mid = (beg + end) / 2;
      mergeSort(arr, tmp, beg, mid, !inArr);
      mergeSort(arr, tmp, mid+1, end, !inArr);
      // arr和tmp轮替
      if (inArr) {
        merge(arr, tmp, beg, mid, end);
      } else {
        merge(tmp, arr, beg, mid, end);
      }
    } else {
      // 如果到最后一层需要考虑这层的元素是否需要转移到tmp上
      if (!inArr)
        tmp[beg] = arr[beg];
    }
  }
  void merge(int* arr1, int* arr2, int beg, int mid, int end) {
    int i = beg, j = mid+1, k = beg;
    while (i != mid+1 && j != end+1) {
      if (arr2[i] < arr2[j])
        arr1[k++] = arr2[i++];
      else
        arr1[k++] = arr2[j++];
    }
    while (i != mid+1) arr1[k++] = arr2[i++];
    while (j != end+1) arr1[k++] = arr2[j++];
  }
  int* entry;
  int size;
};

int main() {
  int size;
  cin >> size;
  SortingArray sa(size);
  for (int i = 0; i < size; ++i) {
    cin >> sa[i];
  }

  sa.sort();

  for (int i = 0; i < size; ++i) {
    cout << sa[i] << ' ';
  }
  cout << endl;
  return 0;
}

链表归并排序

对链表进行归并排序就比较简单且高效了，不仅时间复杂度只有O(nlogn)，而且空间复杂度仅为O(1)。主要流程还是一样，切分，排序，合并。不过，在对链表沿着中间点切分成两部分可能要麻烦点，我这里采取的方法是常见的链表切分方法，快慢指针法。具体的C++代码实现如下所示，切分链表时，定义两个指针，一个快指针和一个慢指针，快指针一次移动2步，慢指针一次移动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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
using namespace std;

struct Node {
  Node(int entry = 0, Node* next = NULL): entry(entry), next(next) {}
  int entry;
  Node* next;
};

class SortingList {
public:
  SortingList(): head(NULL), last(NULL) {}
  ~SortingList() {
    while (head != NULL) {
      Node* tmp = head;
      head = head->next;
      delete tmp;
    }
  }
  void push(const int& e) {
    if (head == NULL) {
      head = new Node(e);
      last = head;
    } else {
      last->next = new Node(e);
      last = last->next;
    }
  }
  void sort() {
    // 排序可能使得头尾节点产生变化，注意重新调整
    head = mergeSort(head);
    last = head;
    while (last != NULL && last->next != NULL)
      last = last->next;
  }
  int pop() {
    int e = head->entry;
    Node* tmp = head;
    head = head->next;
    delete tmp;
    return e;
  }
private:
  // 需要注意排序使得结点顺序改变可能导致头指针发生变化，因此需要返回新的头指针
  Node* mergeSort(Node* subList) {
    if (subList != NULL && subList->next != NULL) {
      Node* mid = divideIntoTwoList(subList);
      subList = mergeSort(subList);
      mid = mergeSort(mid);
      subList = merge(subList, mid);
    }
    return subList;
  }
  // 快慢指针法切分链表
  Node* divideIntoTwoList(Node* subList) {
    Node* fast = subList->next;
    Node* slow = subList;
    while (fast != NULL) {
      fast = fast->next;
      if (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
      }
    }
    fast = slow->next;
    slow->next = NULL;
    return fast;
  }
  // 合并两个链表，空间开销O(1)
  Node* merge(Node* list1, Node* list2) {
    Node fakeHead;
    Node* last = &fakeHead;
    while (list1 != NULL && list2 != NULL) {
      if (list1->entry < list2->entry) {
        last->next = list1;
        list1 = list1->next;
      } else {
        last->next = list2;
        list2 = list2->next;
      }
      last = last->next;
    }
    if (list1 != NULL) last->next = list1;
    else last->next = list2;
    return fakeHead.next;
  }
  Node* head;
  Node* last;
};

int main() {
  int n, e;
  cin >> n;
  SortingList sl;
  for (int i = 0; i < n; ++i) {
    cin >> e;
    sl.push(e);
  }

  sl.sort();

  for (int i = 0; i < n; ++i) {
    cout << sl.pop() << ' ';
  }
  cout << endl;
  return 0;
}

分享到