基于单链表的快速排序算法（C++）

刺骨的言语ヽ痛彻心扉 2023-06-22 14:56 60阅读 0赞

考研倒计时4天，写个代码放松放松。

国科大19年863最后一题数据结构大题：待排序列采用带头结点的单链表，写出在其上进行的快速排序的递归算法。

算法思想：快排核心思想是每一趟确定一个基元素的最终位置，小于它的在左边，大于它的在右边。题目给了单链表，那就没办法随机访问，但是不影响将一段链表分为两段的操作，那就用几个指针通过一次遍历将一段链表分为两段，然后基元素放中间，最后递归左右两段链表就行了。时间复杂度不变的，依然是O(n log n)。

代码如下：

#include <iostream>
    using namespace std;
    /*
    题目：链式存储的快排
    作者：伊特玛德神
    算法思想：
    每一趟以第一个元素为基准
    q依次后移，若小于基准，则与p交换
    p与q之间的维持大于基准的元素
    最后将基准与p交换
    此时基准左边是小于的链表，右边是大于的
    然后进行下一趟
    快排左边和右边的链表
    */
    typedef struct node {
    	int val;
    	node* next;
    }node;
    
    void my_swap(node* p, node* q) {
    	// 自写交换函数
    	// 只交换值，不更改链表指针，减少执行时间
        // 这里如果想交换指针，就需要增加前驱，麻烦点而已
    	int tmp = p->val;
    	p->val = q->val;
    	q->val = tmp;
    }
    
    void quick_sort_list(node* head, node* tail) {
    	if (head == tail || head == NULL || head == tail->next)return; // 递归出口
    	node* p, * q, * pre;
    	p = q = pre = head;
    	while (q != tail) {
    		q = q->next; // 对于一个链表只遍历一遍
    		if (q->val < head->val) {
    			// 如果q的值大于base则放在p左边
    			pre = p;
    			p = p->next;
    			my_swap(p, q);
    		}
    	}// 执行while完毕后的情况：
    	// base在head,[head->next,p]小于base,[p->next,tail]大于base
    	my_swap(head, p); // 将base放在最终位置
    	quick_sort_list(head, pre);
    	quick_sort_list(p->next, tail);
    }
    
    int main(){
    	node* List = new node;//带头结点的链表
    	node* p = List;
    	int n = 0;
    	cout << "要输入几个数字？" << endl;
    	cin >> n;
    	for (short i = 0; i < n; i++) {
    		node* q = new node;
    		cin >> q->val;
    		q->next = NULL;
    		p->next = q; p = q;		
    	}
    	quick_sort_list(List->next, p);
    	p = List -> next;
    	while (p != NULL) {
    		cout << p->val << " ";
    		p = p->next;
    	}
    	cout << "执行结束" << endl;
    	return 0;
    }

唉，多么希望可以考上研究生，可惜复习太差，今年无缘呐！