快排

void quickSort(vector<int> &vec, int start, int end) {
	if (start < end) {
		int i = start, j = end-1;
		int middle = (i + j) / 2;
		swap(vec[end], vec[middle]);
		while (i <= j) {
			while (i <= j && vec[i] <= vec[end])
				i++;
			while (i <= j && vec[j] > vec[end])
				j--;
			if (i < j)
				swap(vec[i], vec[j]);
		}
		swap(vec[i], vec[end]);

		quickSort(vec, start, i - 1);
		quickSort(vec, i + 1, end);
	}
}

单链表快排

leetcode 148. Sort List

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

ListNode *Partition(ListNode *pBegin, ListNode *pEnd){
    int key = pBegin->val;
    ListNode *p = pBegin, *q = pBegin->next;
    while(q != pEnd){
        if(q->val < key){
            p = p->next;
            if(p!=q){
                swap(p->val, q->val);
            }
        }
        q = q->next;
    }
    swap(p->val, pBegin->val);
    return p;
}

void quickSort(ListNode *pBegin, ListNode *pEnd){
    if(pBegin!=pEnd){
        ListNode *partition = Partition(pBegin, pEnd);
        quickSort(pBegin, partition);
        quickSort(partition->next, pEnd);
    }
}

ListNode* sortList(ListNode* head) {
    quickSort(head, nullptr);
    return head;
}

非递归快排

int Pritation(int* a, int left, int right)
{
    if (a == NULL || left < 0 || right <= 0||left>=right)
        return -1;
    int pivot = a[left];
    int i = left, j = right;
    while (i < j)
    {
        while (i < j&&a[j] >= priot)
            j--;
        if(i<j)
            a[i]=a[j];
        while (i < j&&a[i] <= priot)
            i++;
        if(i<j)
            a[j]=a[i];
    }
    a[i] = priot;
    return i;
}

void QuickSort(int *a, int left,int right)
{
    if (a == NULL || left < 0 || right <= 0 || left>right)
        return;
    stack<int>temp;
    int i, j;
    //（注意保存顺序）先将初始状态的左右指针压栈
    temp.push(right);//先存右指针
    temp.push(left);//再存左指针
    while (!temp.empty())
    {
        i = temp.top();//先弹出左指针
        temp.pop();
        j = temp.top();//再弹出右指针
        temp.pop();
        if (i < j)
        {
            int k = Pritation(a, i, j);
            if (k > i)
            {
                temp.push(k - 1);//保存中间变量
                temp.push(i);  //保存中间变量 
            }
            if (j > k)
            {
                temp.push(j);
                temp.push(k + 1);
            }
        }

    }
    
}

归并

void Merge(vector<int> &nums, int start, int end) {
	vector<int> tmp;
	int middle = (start + end) / 2;
	int i = start, j = middle + 1;
	while (i <= middle && j <= end) {
		if (nums[i] < nums[j]) {
			tmp.push_back(nums[i]);
			i++;
		}
		else {
			tmp.push_back(nums[j]);
			j++;
		}
	}
	while (i <= middle) {
		tmp.push_back(nums[i]);
		i++;
	}
	while (j <= end) {
		tmp.push_back(nums[j]);
		j++;
	}
	for (auto n : tmp) {
		nums[start] = n;
		start++;
	}
}

void MergeSort(vector<int> &nums, int start, int end) {
	if (start >= end)
		return;
	int middle = (start + end) / 2;
	MergeSort(nums, start, middle);
	MergeSort(nums, middle + 1, end);
	Merge(nums, start, end);
}

单链表归并

//链表用归并排序效率比快排好很多
struct ListNode {
	int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *Merge(ListNode *l1, ListNode *l2){
	if(!l1) return l2;
	if(!l2) return l1;
	if(l1->val < l2->val){
		l1->next = Merge(l1->next, l2);
		return l1;
	}
	else{
		l2->next = Merge(l1, l2->next);
		return l2;
	}
}

ListNode *MergeSort(ListNode *head){
	if(head==nullptr || head->next==nullptr)
		return head;
	ListNode *slow = head, *fast = head, *pre = head;
	//将链表对半拆分
	while(fast && fast->next){
		pre = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	pre->next = nullptr;
	return Merge(MergeSort(head), MergeSort(slow));
}

堆排序

//构造最大堆
void MaxHeapFixDown(vector<int> &a, int i, int n) {
	int j = 2 * i + 1;
	int temp = a[i];
	while (j<n) {
		if (j + 1<n&&a[j]<a[j + 1])
			++j;
		if (temp>a[j])
			break;
		else {
			a[i] = a[j];
			i = j;
			j = 2 * i + 1;
		}
	}
	a[i] = temp;
}

//堆排序
void HeapSort(vector<int> &a, int n) {
	for (int i = n / 2 - 1; i >= 0; i--)
		MaxHeapFixDown(a, i, n);
	for (int i = n - 1; i >= 1; i--) {
		swap(a[i], a[0]);
		MaxHeapFixDown(a, 0, i);
	}
}