快排及链表排序

文章目录

• 一、普通的快排
• 二、链表的创建
• 三、链表的冒泡排序
• 四、链表快排
• 五、链表归并排序

一、普通的快排

void QuickSort(vector<int> &vec, int low, int high)
{
	int pivot = vec[low]; // 选择第一个元素作为枢纽元
	// mid总是指向最后一个比枢纽元小的位置，当需要交换元素时，先将mid加1，这时候
	// mid就指向了第一个大于枢纽元的位置
	int mid = low; 
	if (low >= high) return;
	for (int i = low + 1; i <= high; ++i)
	{
		if (vec[i] <= pivot)
		{
			swap(vec[i], vec[++mid]); // 比枢纽元小的都放前面
		}
	}
	swap(vec[low], vec[mid]); // 保证交换到头部的元素比枢纽元小
	QuickSort(vec, low, mid - 1);
	QuickSort(vec, mid + 1, high);
}

// 调用
QuickSort(num, 0, num.size()-1);

二、链表的创建

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int value) : val(value), next(nullptr) {}
};

ListNode *CreateList(vector<int> vec)
{
	ListNode *pHead = new ListNode(vec[0]);
	ListNode *pTmp = pHead;
	int cnt = 1, sz = vec.size();
	while (cnt < sz)
	{
		ListNode *pCurrent = new ListNode(vec[cnt]);
		pTmp->next = pCurrent;
		pTmp = pCurrent;
		cnt++;
	}
	pTmp->next = nullptr;
	return pHead;
}
void ShowList(ListNode* pHead)
{
	while (pHead)
	{
		cout << pHead->val << " ";
		pHead = pHead->next;
	}
	cout << endl;
}

三、链表的冒泡排序

与普通的冒泡排序类似，pHead1控制次数，pHead2 用于比较和交换。

ListNode* BubbleSortList(ListNode* pHead)
{
	if (pHead == nullptr)
		return nullptr;
	ListNode *pHead1, *pHead2;
	for (pHead1 = pHead; pHead1->next != nullptr; pHead1 = pHead1->next)
	{
		for (pHead2 = pHead; pHead2->next != nullptr; pHead2 = pHead2->next)
		{
			// 相邻元素比较交换
			if (pHead2->val > pHead2->next->val)
				swap(pHead2->val, pHead2->next->val);
		}
	}
	return pHead;
}

// 调用
ListNode* pHead = CreateList(vec);
BubbleSortList(pHead);

四、链表快排

和普通的快排基本上没有区别。

void QuickSortList(ListNode* pBegin, ListNode* pEnd)
{
	// 选取第一个结点为枢纽元，pmid 总是指向最后一个小于等于枢纽元的结点
	ListNode* pivot = pBegin, *pmid = pBegin, *ptmp;
	if (pBegin == pEnd || pBegin == nullptr) return;
	for (ptmp = pBegin->next; ptmp != pEnd; ptmp = ptmp->next)
	{
		if (ptmp->val <= pivot->val)
		{
			pmid = pmid->next;
			swap(ptmp->val, pmid->val);
		}
	}
	swap(pmid->val, pBegin->val);
	QuickSortList(pBegin, pmid);
	QuickSortList(pmid->next, pEnd);
}

// 调用
ListNode* pHead = CreateList(vec);
QuickSortList(pHead, nullptr);

五、链表归并排序

Node* MergeSort(Node* node) {
	// 先判断链表长度是否大于1，小于1时无须排序
	if (node != nullptr && node->next != nullptr) {
		// 运用快慢指针，找到链表的中间节点
		Node *fast = node->next;
		Node *slow = node;
		while (fast != nullptr && fast->next != nullptr) {
			fast = fast->next->next;
			slow = slow->next;
		}

		// 将链表分成两部分进行分割
		Node *p1 = MergeSort(slow->next);
		slow->next = NULL; // slow
		Node *p2 = MergeSort(node);

		// 对两段子链表进行归并
		Node *p0 = (Node *)malloc(sizeof(Node));
		Node *p = p0;
		while (p1 != NULL && p2 != NULL) {
			if (p1->val < p2->val) {
				p->next = p1;
				p1 = p1->next;
			}
			else {
				p->next = p2;
				p2 = p2->next;
			}
			p = p->next;
		}

		if (p1 != NULL) {
			p->next = p1;
		}

		if (p2 != NULL) {
			p->next = p2;
		}

		p = p0->next;
		free(p0);
		return p;
	}
	return node;
}