## Sunday, November 29, 2015

http://yuanhsh.iteye.com/blog/2186111
http://www.cnblogs.com/TenosDoIt/p/3666585.html

`    ``ListNode *mergeSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``//链表归并排序`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``else`
`        ``{`
`            ``//快慢指针找到中间节点`
`            ``ListNode *fast = head,*slow = head;`
`            ``while``(fast->next != NULL && fast->next->next != NULL)`
`            ``{`
`                ``fast = fast->next->next;`
`                ``slow = slow->next;`
`            ``}`
`            ``fast = slow;`
`            ``slow = slow->next;`
`            ``fast->next = NULL;`
`            ``fast = sortList(head);``//前半段排序`
`            ``slow = sortList(slow);``//后半段排序`
`            ``return` `merge(fast,slow);`
`        ``}`
`        `
`    ``}`
`    ``// merge two sorted list to one`
`    ``ListNode *merge(ListNode *head1, ListNode *head2)`
`    ``{`
`        ``if``(head1 == NULL)``return` `head2;`
`        ``if``(head2 == NULL)``return` `head1;`
`        ``ListNode *res , *p ;`
`        ``if``(head1->val < head2->val)`
`            ``{res = head1; head1 = head1->next;}`
`        ``else``{res = head2; head2 = head2->next;}`
`        ``p = res;`
`        `
`        ``while``(head1 != NULL && head2 != NULL)`
`        ``{`
`            ``if``(head1->val < head2->val)`
`            ``{`
`                ``p->next = head1;`
`                ``head1 = head1->next;`
`            ``}`
`            ``else`
`            ``{`
`                ``p->next = head2;`
`                ``head2 = head2->next;`
`            ``}`
`            ``p = p->next;`
`        ``}`
`        ``if``(head1 != NULL)p->next = head1;`
`        ``else` `if``(head2 != NULL)p->next = head2;`
`        ``return` `res;`
`    ``}`
``````    public Node merge_sort(Node head) {
Node middle = getMiddle(head);      //get the middle of the list
Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

}

public Node merge(Node a, Node b) {
while(a !=null && b!= null) {
if(a.info <= b.info) { curr.next = a; a = a.next; }
else { curr.next = b; b = b.next; }
curr = curr.next;
}
curr.next = (a == null) ? b : a;
}

Node slow, fast; slow = fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next; fast = fast.next.next;
}
return slow;
}``````

`void` `quicksort(vector<``int``>&arr, ``int` `low, ``int` `high)`
`{`
`  if``(low < high)`
`  {`
`   int` `middle = mypartition(arr, low, high);`
`   quicksort(arr, low, middle-1);`
`   quicksort(arr, middle+1, high);`
`  }`
`}`

`    ``ListNode *quickSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``//链表快速排序`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``qsortList(head, NULL);`
`        ``return` `head;`
`    ``}`
`    ``void` `qsortList(ListNode*head, ListNode*tail)`
`    ``{`
`        ``//链表范围是[low, high)`
`        ``if``(head != tail && head->next != tail)`
`        ``{`
`            ``ListNode* mid = partitionList(head, tail);`
`            ``qsortList(head, mid);`
`            ``qsortList(mid->next, tail);`
`        ``}`
`    ``}`
`    ``ListNode* partitionList(ListNode*low, ListNode*high)`
`    ``{`
`        ``//链表范围是[low, high)`
`        ``int` `key = low->val;`
`        ``ListNode* loc = low;`
`        ``for``(ListNode*i = low->next; i != high; i = i->next)`
`            ``if``(i->val < key)`
`            ``{`
`                ``loc = loc->next;`
`                ``swap(i->val, loc->val);`
`            ``}`
`        ``swap(loc->val, low->val);`
`        ``return` `loc;`
`    ``}`

`    ``ListNode *quickSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``//链表快速排序`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``ListNode tmpHead(0); tmpHead.next = head;`
`        ``qsortList(&tmpHead, head, NULL);`
`        ``return` `tmpHead.next;`
`    ``}`
`    ``void` `qsortList(ListNode *headPre, ListNode*head, ListNode*tail)`
`    ``{`
`        ``//链表范围是[low, high)`
`        ``if``(head != tail && head->next != tail)`
`        ``{`
`            ``ListNode* mid = partitionList(headPre, head, tail);``//注意这里head可能不再指向链表头了`
`            ``qsortList(headPre, headPre->next, mid);`
`            ``qsortList(mid, mid->next, tail);`
`        ``}`
`    ``}`
`    ``ListNode* partitionList(ListNode* lowPre, ListNode* low, ListNode* high)`
`    ``{`
`        ``//链表范围是[low, high)`
`        ``int` `key = low->val;`
`        ``ListNode node1(0), node2(0);``//比key小的链的头结点，比key大的链的头结点`
`        ``ListNode* little = &node1, *big = &node2;`
`        ``for``(ListNode*i = low->next; i != high; i = i->next)`
`            ``if``(i->val < key)`
`            ``{`
`                ``little->next = i;`
`                ``little = i;`
`            ``}`
`            ``else`
`            ``{`
`                ``big->next = i;`
`                ``big = i;`
`            ``}`
`        ``big->next = high;``//保证子链表[low,high)和后面的部分连接`
`        ``little->next = low;`
`        ``low->next = node2.next;`
`        ``lowPre->next = node1.next;``//为了保证子链表[low,high)和前面的部分连接`
`        ``return` `low;`
`    ``}`

`    ``ListNode *insertionSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``ListNode *p = head->next, *pstart = ``new` `ListNode(0), *pend = head;`
`        ``pstart->next = head; ``//为了操作方便，添加一个头结点`
`        ``while``(p != NULL)`
`        ``{`
`            ``ListNode *tmp = pstart->next, *pre = pstart;`
`            ``while``(tmp != p && p->val >= tmp->val) ``//找到插入位置`
`                ``{tmp = tmp->next; pre = pre->next;}`
`            ``if``(tmp == p)pend = p;`
`            ``else`
`            ``{`
`                ``pend->next = p->next;`
`                ``p->next = tmp;`
`                ``pre->next = p;`
`            ``}`
`            ``p = pend->next;`
`        ``}`
`        ``head = pstart->next;`
`        ``delete` `pstart;`
`        ``return` `head;`
`    ``}`
`void` `insertionSort(``struct` `node **head_ref)`
`{`
`    ``// Initialize sorted linked list`
`    ``struct` `node *sorted = NULL;`
`    ``// Traverse the given linked list and insert every`
`    ``// node to sorted`
`    ``struct` `node *current = *head_ref;`
`    ``while` `(current != NULL)`
`    ``{`
`        ``// Store next for next iteration`
`        ``struct` `node *next = current->next;`
`        ``// insert current in sorted linked list`
`        ``sortedInsert(&sorted, current);`
`        ``// Update current`
`        ``current = next;`
`    ``}`
`    ``// Update head_ref to point to sorted linked list`
`    ``*head_ref = sorted;`
`}`
`/* function to insert a new_node in a list. Note that this`
`  ``function expects a pointer to head_ref as this can modify the`
`  ``head of the input linked list (similar to push())*/`
`void` `sortedInsert(``struct` `node** head_ref, ``struct` `node* new_node)`
`{`
`    ``struct` `node* current;`
`    ``/* Special case for the head end */`
`    ``if` `(*head_ref == NULL || (*head_ref)->data >= new_node->data)`
`    ``{`
`        ``new_node->next = *head_ref;`
`        ``*head_ref = new_node;`
`    ``}`
`    ``else`
`    ``{`
`        ``/* Locate the node before the point of insertion */`
`        ``current = *head_ref;`
`        ``while` `(current->next!=NULL &&`
`               ``current->next->data < new_node->data)`
`        ``{`
`            ``current = current->next;`
`        ``}`
`        ``new_node->next = current->next;`
`        ``current->next = new_node;`
`    ``}`
`}`

`    ``ListNode *selectSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``//选择排序`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``ListNode *pstart = ``new` `ListNode(0);`
`        ``pstart->next = head; ``//为了操作方便，添加一个头结点`
`        ``ListNode*sortedTail = pstart;``//指向已排好序的部分的尾部`
`       `
`        ``while``(sortedTail->next != NULL)`
`        ``{`
`            ``ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;`
`            ``//寻找未排序部分的最小节点`
`            ``while``(p != NULL)`
`            ``{`
`                ``if``(p->val < minNode->val)`
`                    ``minNode = p;`
`                ``p = p->next;`
`            ``}`
`            ``swap(minNode->val, sortedTail->next->val);`
`            ``sortedTail = sortedTail->next;`
`        ``}`
`       `
`        ``head = pstart->next;`
`        ``delete` `pstart;`
`        ``return` `head;`
`    ``}`

`    ``ListNode *bubbleSortList(ListNode *head) {`
`        ``// IMPORTANT: Please reset any member data you declared, as`
`        ``// the same Solution instance will be reused for each test case.`
`        ``//链表快速排序`
`        ``if``(head == NULL || head->next == NULL)``return` `head;`
`        ``ListNode *p = NULL;`
`        ``bool` `isChange = ``true``;`
`        ``while``(p != head->next && isChange)`
`        ``{`
`            ``ListNode *q = head;`
`            ``isChange = ``false``;``//标志当前这一轮中又没有发生元素交换，如果没有则表示数组已经有序`
`            ``for``(; q->next && q->next != p; q = q->next)`
`            ``{`
`                ``if``(q->val > q->next->val)`
`                ``{`
`                    ``swap(q->val, q->next->val);`
`                    ``isChange = ``true``;`
`                ``}`
`            ``}`
`            ``p = q;`
`        ``}`
`        ``return` `head;`
`    ``}`