276-对链表进行快速排序

太过爱你忘了你带给我的痛 2023-01-13 10:54 124阅读 0赞

## 对链表进行快速排序 ##

## 定义链表 ##

typedef int ElemType;
    typedef struct ListNode
    {
        
    	ElemType data;
    	ListNode* next;
    }ListNode, * LinkList;

## 对链表的初始化 ##

**尾插法**

ListNode* Init_List(const vector<int>& br)
    {
        
    	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    	head->data = br[0];
    	head->next = nullptr;
    	ListNode* p = head;
    	for (int i = 1; i < br.size(); ++i)
    	{
        
    		ListNode* s = (ListNode*)malloc(sizeof(ListNode));
    		s->data = br[i];
    		s->next = nullptr;
    		p->next = s;
    		p = p->next;
    	}
    	return head;
    	
    }

## 打印链表 ##

void Print_List(ListNode* p)
    {
        
    	while (p != nullptr)
    	{
        
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }

## 对链表的划分 ##

![在这里插入图片描述][20210418193950763.png_pic_center]

ListNode* LinkParition(ListNode* left, ListNode* right)
    {
        
    	ListNode* ip = left;
    	ListNode* jp = left->next;
    	int tmp = left->data;
    	while (jp != right)
    	{
        
    		if (jp->data <= tmp)
    		{
        
    			ip = ip->next;
    			std::swap(ip->data, jp->data);
    		}
    		jp = jp->next;
    	}
    	std::swap(left->data, ip->data);
    	return ip;
    }

## 对链表快速排序 ##

void QuickPass(ListNode* left, ListNode* right)
    {
        
    	if (left != right)
    	{
        
    		ListNode* p = LinkParition(left, right);
    		QuickPass(left, p);
    		QuickPass(p->next, right);
    	}
    }
    void ListQuickSort(ListNode* head)
    {
        
    	QuickPass(head, nullptr);
    }

## 书写主函数 ##

int main()
    {
        
    	vector<int> ar = {
         56,34,23,78,90,12,45,67,89,100 };
    	LinkList head = Init_List(ar);
    	Print_List(head);
    	ListQuickSort(head);
    	Print_List(head);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[20210418193950763.png_pic_center]: /images/20221022/cf5eb04a726f455d9951fa545783aa63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/61e01c9beef24da7854c6e8238d5b1c4.png