首页 > 代码库 > 63.如何对单链表进行快排?和数组快排的分析与对比[quicksort of array and linked list]
63.如何对单链表进行快排?和数组快排的分析与对比[quicksort of array and linked list]
【本文链接】
http://www.cnblogs.com/hellogiser/p/quick-sort-of-array-and-linked-list.html
【题目】
单链表的特点是:单向。设头结点位head,则最后一个节点的next指向NULL。如果只知道头结点head,请问怎么将该链表排序?
【分析】
对于数组的快排:有2种方式。
(1)指针相向移动:一个指针i指向头,一个指针j指向尾,然后两个指针相向运动并按一定规律交换值,最后找到一个支点p使得支点左边的值小于支点,支点右边的值大于支点。由于单链表只有next指针,没有前驱指针,因此这种方法行不通。
(2)指针同向移动:两个指针i和j,这两个指针均往数组的右方移动,移动的过程中保持i之前的值都小于选定的key,i和j之间的值都大于选定的key,那么当j走到末尾的时候便完成了一次支点的寻找。这个思路非常适合单链表。
对于数组,我们很容易写出下面的代码。
【代码1】
C++ Code
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 | /* version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/5/30 */ // i from left,j from right // i------------>p<-----------------j int Partition(int a[], int left, int right) { // partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p] int pivot = a[left], i = left , j = right; while (i < j) { while (a[i] <= pivot) i++; while (a[j] > pivot) j--; if (i < j) myswap(a[i], a[j]); } myswap(a[left], a[j]); return j; } void QuickSort(int a[], int left, int right) { if(left < right) // less { int p = Partition(a, left, right); QuickSort(a, left, p - 1); QuickSort(a, p + 1, right); } } void QuickSort(int a[], int n) { QuickSort(a, 0, n - 1); } |
【代码2】
C++ Code
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 | /* version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/5/30 */ // i and j both from left // i,j----------------> int Partition2(int a[], int left, int right) { // partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p] // left----i<=pivot, i----j>=pivot int pivot = a[left], i = left , j = left + 1; while (j <= right) { if (a[j] < pivot) { i++; myswap(a[i], a[j]); } j++; } myswap(a[left], a[i]); return i; } void QuickSort2(int a[], int left, int right) { if(left < right) // less { int p = Partition2(a, left, right); QuickSort2(a, left, p - 1); QuickSort2(a, p + 1, right); } } void QuickSort2(int a[], int n) { QuickSort2(a, 0, n - 1); } |
对于链表而言,借鉴(2)指针同向移动的思想容易改成如下代码。
【代码】
C++ Code
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 | /* version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/5/30 */ // i and j both from left // i,j----------------> node *Partition2_List(node *left, node *right) { // partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p] // left----i<=pivot, i----j>=pivot node *pivot = left, *i = left , *j = left->next; while (j != right) { if (j->value < pivot->value) { i = i->next; myswap(i->value, j->value); } j = j->next; } myswap(left->value, i->value); return i; } void QuickSort2_List(node *left, node *right) { if(left != right) // less { node *p = Partition2_List(left, right); QuickSort2_List(left, p); QuickSort2_List(p->next, right); } } void QuickSort2_List(node *head) { QuickSort2_List(head, NULL); } |
【参考】
http://blog.csdn.net/wumuzi520/article/details/8078322
【本文链接】
http://www.cnblogs.com/hellogiser/p/quick-sort-of-array-and-linked-list.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。