链表 quicksort
时间: 2024-08-17 09:00:14 浏览: 31
快速排序(Quicksort)是一种高效的排序算法,其基本思想是分而治之,通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后分别对这两部分再进行排序,整个排序过程递归进行,直到所有元素有序。
在链表上实现快速排序的主要挑战在于,链表不像数组那样可以直接访问任意位置的元素,所以我们不能像处理数组那样通过索引直接交换元素。但我们可以采用类似的方法:
1. **选择基准**:在链表中随机选择一个节点作为基准值pivot。
2. **分区操作**:遍历链表,找到小于基准的节点和大于基准的节点,分别放在两个新的链表中。这个过程可能需要创建新的链接节点,因为原链表不可修改。
3. **递归**:对小于基准的子链表和大于基准的子链表再次执行快速排序。
4. **合并**:最后,把排序后的两个子链表连接起来,并返回新形成的链表头节点。
由于链表操作涉及到节点移动而非简单的元素交换,所以快速排序的实现相比数组会稍微复杂一些,但它的时间复杂度依然保持在平均情况下为O(n log n)。
相关问题
c语言链表排序
链表排序一般采用归并排序或快速排序。
1. 归并排序
归并排序的基本思路是分治法,将链表分成若干个子链表,对每个子链表进行排序,然后合并子链表,直到最后只剩下一个有序链表。具体实现如下:
```c
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode *next;
}ListNode;
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode *head = NULL;
ListNode *tail = NULL;
// 将较小的结点作为头结点
if (l1->val < l2->val) {
head = l1;
l1 = l1->next;
}
else {
head = l2;
l2 = l2->next;
}
// 遍历两个链表,依次取出较小的结点
tail = head;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
}
else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 将剩余结点接到尾部
if (l1 != NULL) {
tail->next = l1;
}
else if (l2 != NULL) {
tail->next = l2;
}
return head;
}
// 归并排序
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
// 快慢指针找到链表中点
ListNode *fast = head;
ListNode *slow = head;
while (fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
// 将链表分成两个子链表
ListNode *head1 = head;
ListNode *head2 = slow->next;
slow->next = NULL;
// 递归排序两个子链表
head1 = sortList(head1);
head2 = sortList(head2);
// 合并两个子链表,返回头结点
return mergeTwoLists(head1, head2);
}
```
2. 快速排序
快速排序的基本思路是选取一个元素作为基准值,将链表分成小于基准值和大于等于基准值的两部分,然后递归地对两部分进行快速排序。具体实现如下:
```c
// 获取链表结点数量
int getListLength(ListNode *head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
// 快速排序
ListNode* quickSort(ListNode *head, ListNode *tail) {
if (head == NULL || head == tail) {
return head;
}
// 将链表分成小于基准值和大于等于基准值的两部分
ListNode *pivot = head;
ListNode *p = head;
ListNode *q = head->next;
while (q != tail) {
if (q->val < pivot->val) {
p = p->next;
int tmp = p->val;
p->val = q->val;
q->val = tmp;
}
q = q->next;
}
int tmp = p->val;
p->val = pivot->val;
pivot->val = tmp;
// 递归地对两部分进行快速排序
quickSort(head, p);
quickSort(p->next, tail);
return head;
}
// 快速排序入口函数
ListNode* sortList(ListNode* head) {
int len = getListLength(head);
return quickSort(head, NULL);
}
```
链表快速排序的递归算法
链表快速排序的递归算法可以通过以下步骤实现:
1. 选择链表中的一个元素作为基准值(pivot)。
2. 将链表分成两个部分,一个部分包含所有小于等于基准值的元素,另一个部分包含所有大于基准值的元素。
3. 对两个部分分别进行递归排序。
4. 将排序后的两个部分连接起来,得到最终排序后的链表。
下面是一个示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def partition(head, end):
pivot = head.val
slow = head
fast = head.next
while fast != end:
if fast.val < pivot:
slow = slow.next
slow.val, fast.val = fast.val, slow.val
fast = fast.next
slow.val, head.val = head.val, slow.val
return slow
def quickSort(head, end):
if head != end:
pivot = partition(head, end)
quickSort(head, pivot)
quickSort(pivot.next, end)
def sortList(head):
quickSort(head, None)
return head
```
这段代码中,`ListNode` 是链表节点的定义,`partition` 函数用于将链表分成两个部分,`quickSort` 函数用于递归排序,`sortList` 函数是入口函数,用于调用快速排序算法。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)