使用QuickSort快速排序算法,排序一个链表。
下面是quickSort,因为quickSort算法的最坏情况是O(n*n), 所以如果做LeetCode上的Sort List这道题目,会遇上最坏情况超时的,不过这是个很好的算法,故此贴出来。
参考网站:
http://www.geeksforgeeks.org/quicksort-on-singly-linked-list/
也看了有些博客或什么网站也写有quickSort排序链表的文章,注意看清楚了,很多并不是真正的链表排序,而是排序了链表的值,那样并不是链表操作,不能算链表的quicksort。
有几个地方需要注意的:
1 分成两个链表的时候,注意把结尾=NULL,重新合并中间的pivot不要忘了,不然会断链的。
2 指针传递要注意:指针值传递和指针地址传递
class Solution2QuickSort {
public:
ListNode *sortList(ListNode *head)
{
return quickSort(head, getTail(head));
}
ListNode *getTail(ListNode *h)
{
while (h && h->next) h = h->next;
return h;
}
ListNode *partition(ListNode *h, ListNode *t, ListNode **nh, ListNode **nt)
{
ListNode *pivot = t;
ListNode *pre = NULL, *cur = h, *tail = t;
while (cur != pivot)
{
if (cur->val < pivot->val)
{
if (!(*nh)) (*nh) = cur; //注意:不能是nh=&cur
pre = cur;
cur = cur->next;
}
else
{
if (pre) pre->next = cur->next;
ListNode *tmp = cur->next;
cur->next = pivot->next;
pivot->next = cur;
cur = tmp;
if (tail == t) tail = tail->next;
}
}
if (!(*nh)) (*nh) = pivot;
(*nt) = tail;
return pivot;
}
ListNode *quickSort(ListNode *h, ListNode *t)
{
if (!h || h == t) return h;
ListNode *nh = nullptr, *nt = nullptr;
ListNode *pivot = partition(h,t,&nh,&nt);
if (nh != pivot)
{
ListNode *tmp = nh;
while (tmp->next != pivot) tmp = tmp->next;
tmp->next = nullptr;
nh = quickSort(nh, tmp);
tmp = getTail(nh);
tmp->next = pivot;
}
pivot->next = quickSort(pivot->next, nt);
return nh;
}
};
分享到:
相关推荐
// 对L.r[low]——L.r[high] 子序列进行一趟快速排序,返回分界线位置,即枢轴 L.r[0]=L.r[low]; int pivotkey=L.r[0].key; while (low) { while (low[high].key>=pivotkey) { high--; } L.r[low]=...
)栈(堆栈)类别(队列)链表(LinkedList)单链表(LinkedList)双链表(DoublyLinkedList)循环链表(CircularLinkedList)判断链表是否成环(LinkedListWithCycle)链表插入排序(InsertionSort)链表快速排序...
快速排序 mergeSort 归并排序 stack 栈 leetCode maximumProduct 628. 三个数的最大乘积 numEquivDominoPairs 1128. 等价多米诺骨牌对的数量 pivotIndex 724. 寻找数组的中心索引 minimumEffortPath 1631. 最小体力...
目录 02.字符串 03.树 04.哈希表 05.栈和队列 06.图 07.位运算 08.链表 程序基本输入输出 基础算法 返回目录 # English Title Chinese Title ...QuickSort 快速排序 Java 11 HeapSort 堆排序 Java 1
快速排序 QuickSort 插入排序 InsertSort 数据结构 Data Structure 二叉搜索树 BinarySearchTree 设计模式 Design Patterns 单例模式 Singleton 观察者模式 Observer 多线程 Concurrent 自旋锁 SpinLock 任务调度器 ...
结构体 在PHP中进行数据结构的小实验数据结构BinarySearchTree 最小堆最大堆链表双链表哈希图堆排序算法快速排序随机快速排序中间枢轴Quicksort 插入排序
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:sort...
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:sort...
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 ...QuickSort: 快速排序(单路,双路,三路) SelectionSort: 选择排序 ShellSort: 希尔排序 UnionFind: 并查集 graph_dfs: 图的深度遍历
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:sort...
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:sort...
快速排序: quickSort 堆排序: heapSort 计数排序: countSort 215. 数组中的第K个最大元素: 347. 前 K 个高频元素: 451. 根据字符出现频率排序: 75. 颜色分类: 经典贪心问题: 455. 分发饼干: 435. 无重叠区间: 452. ...
快速排序(QuickSort) 锦标赛排序(Tournament) (3)其他 快速地址排序(QkAddrst) 基数排序(RadixSort) 13. 外部排序 (1)多路平衡归并排序(K-Merge) (2)置换-选择排序(Repl_Selection)
快速排序(QuickSort) 锦标赛排序(Tournament) (3)其他 快速地址排序(QkAddrst) 基数排序(RadixSort) 13. 外部排序 (1)多路平衡归并排序(K-Merge) (2)置换-选择排序(Repl_Selection)
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
快速排序(QuickSort) 锦标赛排序(Tournament) (3)其他 快速地址排序(QkAddrst) 基数排序(RadixSort) 13. 外部排序 (1)多路平衡归并排序(K-Merge) (2)置换-选择排序(Repl_Selection) 三、 ...
leetcode103 leetcodeProgram 个人刷题记录 仅供参考 全部题目全部写入arith.go文件,每道题目对应一个api,不定期更新 题目 api leetcode103 二叉树的锯齿形层次遍历 ...非常golang的快速排序 QuickSort
演算法搜索: 二进制搜索( / ) 快速选择( ) 最短路径( )排序: 冒泡排序( ) 计数排序( / ) 堆排序( ) 插入排序( ) Knuth随机播放( ) 合并排序( ) 就地合并排序( ) quicksort( / / ) 基数排序...