网站语言编程,罗定城乡建设局网站,王也台球,郑州信息网平台归并排序能够有两种思路----top-down 和 bottom-up top-down: 递归实现#xff0c;将数组分成两半。分别处理。再合并。 伪代码例如以下#xff1a; split ( A[], l, r)
{if ( r - l 2) return;m (r l) / 2;split ( A, l, m); //split A[l…m-1]split ( A, m, r); //s… 归并排序能够有两种思路----top-down 和 bottom-up top-down: 递归实现将数组分成两半。分别处理。再合并。 伪代码例如以下 split ( A[], l, r)
{if ( r - l 2) return;m (r l) / 2;split ( A, l, m); //split A[l…m-1]split ( A, m, r); //split A[m…r-1]merge ( A, l, m, e); //merge A[l…m-1] and A[m…e-1]
}bottom-up: 循环实现。将数组看做n个长度为1的组数组。 用width控制每次merge的子数组长度。width每次翻倍 伪代码例如以下 sort ( A[], n)
{for (width 1; width n; width * 2){for (i 0; i n; i 2 * width){merge(A, i, min(i width, n), min(i 2 * width, n));}}
} Sort list中使用链表。不能在O(1)的时间内訪问随意节点同一时候注意要处理尾部节点的next置为NULL 和上面的伪代码类似首先实现merge函数 ListNode * merge(ListNode * h1, int s1, ListNode * h2, int s2){if (h2 NULL) return h1;ListNode * h;if (h1-val h2-val)h advance(h1, s1);elseh advance(h2, s2);ListNode * cur h;while (s1 s2){if (h1-val h2-val)cur-next advance(h1, s1);elsecur-next advance(h2, s2);cur cur-next;}if (s1){cur-next h1;while(s1) advance(h1, s1);}if (s2){cur-next h2;while(s2) advance(h2, s2);}return h;}ListNode * advance(ListNode * ( n), int size){ListNode * temp n;if (size 1) n-next NULL;n n-next;size--;return temp;}同一时候实现工具函数訪问任何位置节点 ListNode * getNode(ListNode * head, int len){while (len -- head) head head-next;return head;}循环版本号主函数例如以下 ListNode *sortList(ListNode *head) {ListNode * cur head;int size 0;while (cur){size ;cur cur-next;}ListNode * pre;for (int w 1; w size; w * 2){cur head;for (int i 0; i size; i w*2){ListNode * h1 cur, * h2 getNode(cur, w), * next getNode(cur, 2 * w);cur merge(h1, min(w, size - i), h2, min(w, size - i - w));if (i 0) head cur;else pre-next cur;pre getNode(cur, min(2 * w, size - i) - 1);cur next;}}return head;}递归版本号主函数例如以下 ListNode *sortList(ListNode *head) {ListNode * cur head;int size 0;while (cur){size ;cur cur-next;}return sort(head, size - size / 2, getNode(head, size - size / 2), size / 2);}ListNode * sort(ListNode * h1, int s1, ListNode * h2, int s2){if (s1 0) return h2;if (s2 0) return h1;h1 sort(h1, s1 - s1 / 2, getNode(h1, s1 - s1 / 2), s1 / 2);h2 sort(h2, s2 - s2 / 2, getNode(h2, s2 - s2 / 2), s2 / 2);return merge(h1, s1, h2, s2);} 转载于:https://www.cnblogs.com/blfbuaa/p/6743700.html
