太久不写排序了，限时写已经写不出来了。愧为acmer。
面试官出了个单链表的排序，让我选一种排序，我选了归并排序。大概写了20分钟，一运行就崩溃，由于面试时间有限，面试官看了看我的代码提了几个易错点（如指针判空，链表分治）。
惭愧。
今天把排序算法搬出来分别用数组和单链表写了一遍，温故而知新。
数组版排序
#includeusing namespace std; // 冒泡排序 void bubble_sort(int a[], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]); } } // 选择排序 void selection_sort(int a[], int n) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) if (a[i] > a[j]) swap(a[i], a[j]); } } // 插入排序 void insert_sort(int a[], int n) { for (int i = 1; i < n; i++) { int curr = a[i], k = i; for (k = i - 1; k >= 0 && a[k] > curr; k--) a[k + 1] = a[k]; a[k + 1] = curr; } } // 快速排序 严蔚敏版 void quick_sort(int a[], int L, int R) { if (L >= R) return; int temp = a[L], low = L, high = R; while (low < high) { while (low < high && a[high] >= temp) high--; a[low] = a[high]; while (low < high && a[low] <= temp) low++; a[high] = a[low]; } a[low] = temp; quick_sort(a, L, low - 1); quick_sort(a, low + 1, R); } // 快速排序 交换版 void quick_sort_2(int a[], int L, int R) { if (L >= R) return; int bound = a[L], low = L, high = R; while (low < high) { while (low < high && a[high] >= bound) high--; while (low < high && a[low] <= bound) low++; if (low < high) swap(a[low], a[high]); } swap(a[L], a[low]); quick_sort_2(a, L, low - 1); quick_sort_2(a, low + 1, R); } // 归并排序 void merge_sort(int a[], int L, int R) { if (L >= R) return; int mid = (L + R) / 2; merge_sort(a, L, mid); merge_sort(a, mid + 1, R); // copy array static int *temp = new int[R - L + 1]; for (int i = L; i <= R; i++) temp[i] = a[i]; // merge for (int i = L, first = L, second = mid + 1; i <= R; i++) { if (second > R || first <= mid && temp[first] < temp[second]) a[i] = temp[first++]; else a[i] = temp[second++]; } } // 堆排序 void heap_sort(int a[], int n) { auto heap_down = [=](int x, int max_node) { while (x * 2 + 1 <= max_node) // 大顶堆 { int max_child = x * 2 + 1; // 假设左孩子大 if (max_child + 1 <= max_node && a[max_child] < a[max_child + 1]) max_child = max_child + 1; if (a[x] < a[max_child]) { swap(a[x], a[max_child]); x = max_child; } else break; } }; for (int i = n / 2 - 1; i >= 0; i--) // 子树依次下沉 heap_down(i, n - 1); for (int i = n - 1; i >= 0; i--) { swap(a[i], a[0]); heap_down(0, i - 1); } } // 希尔排序 void shell_sort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) // 步长 { for (int start = 0; start < gap; start++) // 每组开头 { for (int i = start; i < n; i += gap) //第start组进行插入排序 { int temp = a[i], k = i; for (k = i - gap; k >= 0 && a[k] > temp; k -= gap) a[k + gap] = a[k]; a[k + gap] = temp; } } } } // 基数排序 void base_sort(int a[], int n) { int max_base = 1; // 最大基数 for (int i = 0; i < n; i++) { while (max_base < a[i]) max_base *= 10; } vector bucket[10]; for (int base = max_base / 10; base > 0; base /= 10) { for (int i = 0; i < 10; i++) bucket[i].clear(); for (int i = 0; i < n; i++) bucket[a[i] / base].push_back(a[i]); int count = 0; for (int i = 0; i < 10; i++) { for (auto &x : bucket[i]) a[count++] = x; } } } void output(int a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << (i < n - 1 ? " " : "n"); } int main() { int a[] = {14, 19, 11, 13, 16, 12, 10, 17, 15, 18}; int n = sizeof(a) / sizeof(int); output(a, n); // bubble_sort(a, n); // selection_sort(a, n); // insert_sort(a, n); // quick_sort(a, 0, n - 1); // quick_sort_2(a, 0, n - 1); // merge_sort(a, 0, n - 1); // heap_sort(a, n); // base_sort(a, n); shell_sort(a, n); output(a, n); }
单链表排序
#includeusing namespace std; struct Node { int val; Node *next; }; void output(Node *head, bool has_head = true) { if (has_head) head = head->next; for (Node *p = head; p; p = p->next) cout << p->val << (p->next ? ' ' : 'n'); } // 冒泡排序 含头结点 void bubble_sort(Node *head) { Node *sorted = NULL; // 保存已排序链表 while (head->next) { Node *pre = head; // 比较pre后的两结点，完成冒泡 for (; pre->next && pre->next->next; pre = pre->next) { Node *u = pre->next, *v = pre->next->next; if (u->val > v->val) // 交换结点 { u->next = v->next; v->next = u; pre->next = v; } } // 从链表中删除尾结点(即pre->next) Node *tail = pre->next; pre->next = NULL; // 选中的结点插入到有序区(头插法) tail->next = sorted; sorted = tail; } head->next = sorted; } // 选择排序 含头结点 void selection_sort(Node *head) { Node *sorted = NULL; // 保存已排序链表 while (head->next) { // 找到最大的结点(记其前驱), 头插法插入到有序区 Node *max_pre = head; for (Node *p = head->next; p && p->next; p = p->next) { if (max_pre->next->val < p->next->val) max_pre = p; } // 从链表中删除选中的结点 Node *max_node = max_pre->next; max_pre->next = max_pre->next->next; // 选中的结点插入到有序区(头插法) max_node->next = sorted; sorted = max_node; } head->next = sorted; } // 插入排序 含头结点 void insert_sort(Node *head) { Node *sorted = new Node(); sorted->next = NULL; while (head->next) { // 删除当前结点(head->next) Node *cur = head->next; head->next = head->next->next; // 当前结点插入到有序区合适位置 Node *pre = sorted; while (pre->next && pre->next->val < cur->val) pre = pre->next; cur->next = pre->next; pre->next = cur; } head->next = sorted->next; delete sorted; } // 快速排序 不含头结点 Node *quick_sort(Node *head) { if (!head || !head->next) return head; Node *first = NULL, *second = NULL, *bound = head; for (Node *p = head; p;) { Node *next = p->next; if (p->val <= bound->val) { p->next = first; first = p; } else { p->next = second; second = p; } p = next; } // 递归 first = quick_sort(first); // first一定至少包含一个元素bound second = quick_sort(second); // 拼接 Node *first_tail = first; while (first_tail->next) first_tail = first_tail->next; first_tail->next = second; return first; } // 归并排序 不含头结点 Node *merge_sort(Node *head) { if (!head || !head->next) return head; // 找到中间结点 Node *mid = head, *fast = head->next; while (fast && fast->next) { mid = mid->next; fast = fast->next->next; } // 分治 Node *first = head, *second = mid->next; mid->next = NULL; // 断开链表 first = merge_sort(first); second = merge_sort(second); // 归并 Node *sorted = new Node(), *tail = sorted; // 尾插法保存有序链表 while (first || second) { if (first && second && first->val < second->val || !second) { Node *next = first->next; first->next = NULL; tail->next = first; first = next; } else { Node *next = second->next; second->next = NULL; tail->next = second; second = next; } tail = tail->next; } head = sorted->next; delete sorted; return head; } int main() { int a[] = {14, 19, 11, 13, 16, 12, 10, 17, 15, 18}; int n = sizeof(a) / sizeof(int); Node *head = new Node(), *tail = head; for (int i = 0; i < n; i++) { Node *p = new Node(); p->val = a[i]; p->next = NULL; tail->next = p; tail = p; } output(head); // bubble_sort(head); // selection_sort(head); // insert_sort(head); // head->next = quick_sort(head->next); head->next = merge_sort(head->next); output(head); }
