开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 排序总结系列(C++) -> 正文阅读

[数据结构与算法]排序总结系列(C++)

1.插入排序

类似打扑克牌，拿牌阶段；
一个数组[2,3,4,5,3,2,2,1]

降序排序

类似打扑克拍抓牌阶段，让每次抓了牌以后插入手中已有的牌中，使得最后的牌序是升序的；

for(int i=1;i<Arr.size();i++)
{
	for(int j=i-1;j>=0 && Arr[j]>flag_num;j--)
	{
		swap(Arr[j],Arr[i]);
	}
}

升序排序

for(int i=Arr.size()-1;i>=0;i--)
{
	int flag_num = Arr[i];
	j = i+1;
	while(j<Arr.size() && Arr[j]>flag_num)
	{
		swap(Arr[j],flag_num);
		j++;
	}
}

单向链表插入排序

力扣147：
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;   
        ListNode* cur=head->next;;
        ListNode* per_cur=head;
        while(cur!=NULL)
        {
            ListNode* per_ins=dummyhead;
            if(cur->val < per_cur->val)
            {
                while(per_ins->next->val <= cur->val)
                {
                    per_ins = per_ins->next;
                }
                per_cur->next = cur->next;
                cur->next = per_ins->next;
                per_ins->next = cur;
            }
            else
            {
                per_cur = per_cur->next;     
            }
            cur = per_cur->next;
        }
        return dummyhead->next;
    }
};

双向链表插入排序

2.选择排序

选择排序分为两步

选择i~N-1位置的数组上最小值所在的索引，i依次加1
交换i位置与最小值索引位置的数值

for(int i=0;i<N;i++)
{
	int minidx = i;
	for(int j=i+1;j<N;j++)
	{
		minidx = Arr[minidx]<Arr[j] ? minidx : j;
	}
	swap[Arr[i],Arr[minidx]];
}

3.冒泡排序

每次排出一个元素，放在数组头部或者尾部

在0~N-1的范围内，依次比较12位置，23位置，…,N-2 N-1位置，小数前移
在0~N-2的范围内，依次比较12位置，23位置，…,N-3 N-2位置，小数前移

for(int i=N-1;i>=0;i--)
{
	for(int j=0;j<i;j++)
	{
		if(Arr[j]>Arr[j+1])
			swap(Arr[j],Arr[j+1]);
	}
}

4. 归并排序

时间复杂度O(N)*logN

思路过程:
a. 找到中点，对左右两部分进行排序
b. 合并排序以后的左右两部分数组
code

void merge(vector<int>& Arr,int L,int mid,int R)
{
	vector<int> res;
	int i = L;
	int j = mid + 1;
	while (i <= mid &&  j <= R)
	{
		if (Arr[i] > Arr[j])
		{
			res.push_back(Arr[j]);
			j++;
		}
		else
		{
			res.push_back(Arr[i]);
			i++;
		}
	}
	while (i <= mid)
	{
		res.push_back(Arr[i]);
		i++;
	}
	while (j <= R)
	{
		res.push_back(Arr[j]);
		j++;
	}
	for (auto num : res)
	{
		Arr[L] = num;
		L++;
	}
}

void merge_sort(vector<int>& Arr, int L, int R)
{
	if (L == R)
		return;
	int mid = (L + R) >> 1;
	merge_sort(Arr, L, mid);
    merge_sort(Arr, mid + 1, R);
	merge(Arr,L,mid,R);
}


int main()
{
	vector<int> Arr{ 1,2,3,7,5,3,9,3,5 };
	int R = Arr.size()-1;
	int L = 0;
	merge_sort(Arr, L, R);
	for (int i = 0; i < Arr.size(); i ++ )
		cout << Arr[i] << " ";
	return 0;
}

归并排序符合master公式求时间复杂度
子问题的规模等规模都是N/2,为2T(N/2)
决策过程主要是比较递归层是否返回和merge过程，时间复杂度为O(N);
所以归并排序的时间复杂度master计算公式为
T(N) = 2 $\times$ T( $\frac{N}{2}$ ) + O(N)
根据master公式求时间复杂度的公式可以算出复杂度为O(NlogN)
master公式参考链接

还有合并两个升序数组的经典写法如下：


vector<int> merge(vector<int> left_Arr, vector<int>& right_Arr)
{
	vector<int> res;
	int idx1 = 0;
	int idx2 = 0;
	
	while (idx1 < left_Arr.size() && idx2 < right_Arr.size())
	{
		if (left_Arr[idx1] > right_Arr[idx2])
		{
			res.push_back(right_Arr[idx2]);
			idx2 ++;
		}
		else
		{
			res.push_back(right_Arr[idx1]);
			idx1++;
		}
	}
	while (idx1 < left_Arr.size())
	{
		res.push_back(left_Arr[idx1]);
		idx1++;
	}
	while (idx2 < right_Arr.size())
	{
		res.push_back(left_Arr[idx2]);
		idx2++;
	}
	return res;
}

力扣归并排序的题目
【链表排序问题】148排序链表
【小和问题】315. 计算右侧小于当前元素的个数
【逆序对问题】剑指 Offer 51. 数组中的逆序对

5. 快速排序

快速排序视频讲解：毕站传送门

快排思想的由来，两个荷兰国旗题目介绍

在这里插入图片描述

a) 题目1：题目：数组Arr=[3,5,3,7,4,6,5,8]，pvoit=5；使得小于5的元素分布在数组的左侧，大于5的元素分布在数组的右侧
题目1思路从左往右遍历数组元素，如果元素小于等pvoit的，与小于区域的下一位元素做交换，然后小于等于区域右扩；如果元素大于pvoit，无操作，继续往右遍历数组；当遍历数组越界的时候，就停止返回；这个时候的数组就完成了元素pvoit的定位。
题目1 code

vector<int> Arr{3,5,3,7,4,6,5,8};
int pvoit = 5;
int part_L = -1;//小于等于区域的边界
for(int i=0;i<Arr.size();i++)
{
	if(Arr[i]>pvoit)
		continue;
	else
	{
		swap(Arr[++part_L],Arr[i]);
	}
}
return part_L;

b) 题目2：数组Arr=[3,0,5,3,4,5,2,6,9,6],pvoit为5。要求是数组左侧是小于5的元素，中间是等于5的元素(如果数组中国存在元素pvoit)，右侧是大于5的元素

题目2思路：
从左往右遍历数组，遍历元素的索引记为i
有三个策略：
i) 当索引i的元素Arr[i]<pvoit。Arr[i]元素与小于区的下一个元素做交换，小于区右扩一位，遍历索引i++；
ii) 当索引i的元素Arr[i]==pvoit, i++
iii) 当索引i的元素Arr[i]>pvoit,Arr[i]与大于区的前一个元素做交换，大于区左扩一位，i不变
当大于区的左边界于遍历的索引i相遇的时候，停止

题目2 code

vector<int> Arr{3,0,5,3,4,5,2,6,9,6};
int pvoit = 5;
int part_L = -1;
int part_R = Arr.size();
for(int i = 0 ;i < Arr.size();i++)
{
	if(i==part_R)
		break;
	if(Arr[i]==pvoit)
		continue;
	else if(Arr[i]<pvoit)
		swap(Arr[++part_L],Arr[i]);
	else
	{
		swap(Arr[--part_R],Arr[i]);
		i--;
	}
}
return Arr;

快速排序1.0版本思路讲解
a) 快速排序每次可以完成一个数字的排序，选定参考轴pvoit，然后让数组中小于pvoit的元素放到其左侧，让大于pvoit的元素放到其右侧;这样一次循环就完成了一个元素的位置确定；
b) 假设每次都选定数组的最左侧元素看作pvoit轴
快速排序code


int Paritition1(vector<int>& Arr, int low, int high) {
    int pivot = Arr[low];
    while (low < high) {
        while (low < high && Arr[high] >= pivot) {
            --high;
        }
        Arr[low] = Arr[high];
        while (low < high && Arr[low] <= pivot) {
            ++low;
        }
        Arr[high] = Arr[low];
    }
    Arr[low] = pivot;
    return low;
}

void Quick_Sort(vector<int>& Arr, int low, int high) //快排母函数
{
    if (low < high) {
        int pivot = Paritition1(Arr, low, high);
        Quick_Sort(Arr, low, pivot - 1);
        Quick_Sort(Arr, pivot + 1, high);
    }
}

因为每次都选取最左侧元素为pvoit那么如果最差的时间复杂度为O(N²），版本1.0一次只能解决一个数的位置；下面的2.0版本会稍微提一点速

快速排序2.0版本思路讲解
根据荷兰国旗的题目2，用在快速排序里边的话，如果数组中有重复元素，那么一次就可可以解决多个数的位置；
快速排序2.0版本code

#include<iostream>
#include<vector>
using namespace std;

vector<int> Arr{ 3,5,3,7,4,6,5,8 };
int part_L = -1;
int part_R = Arr.size();
void partition(vector<int>& Arr, int L, int R)
{
	part_L = L-1;//小于区域的边界
	part_R = R+1;;
	int pvoit = Arr[L];
	for (int i = L; i <= R; i++)
	{
		if (i == part_R)
			break;
		if (Arr[i] < pvoit)
		{
			swap(Arr[i], Arr[part_L + 1]);
			part_L++;
		}
		else if (Arr[i] == pvoit)
			continue;
		else
		{
			swap(Arr[i], Arr[part_R-1]);
			part_R--;
			i--;
		}

	}
}

void Quick_sort(vector<int>& Arr, int L, int R)
{
	if (L < R)
	{
		partition(Arr, L, R);
		
		Quick_sort(Arr, L, part_L);
		Quick_sort(Arr,  part_R, R);
	}
}

int main()
{
	vector<int> Arr{ 3,5,3,7,4,6,5,8 };
	int L = 0;
	int R = Arr.size() - 1;
	Quick_sort(Arr, L, R);
	for (int i = 0; i < Arr.size(); i++)
		cout << Arr[i] << " ";
	return 0;
}

快速排序2.0版本，如果原始数据不友好，时间复杂度仍旧是O(N²);
因为每一次选定的pvoit都是最左侧的元素，这这就导致每一次都有可能取到效果最差的情况；可以每次选取数据作为pvoit时用随机选取数字的方式，这样每种情况出现的情况都是等概率的，最后所有情况求期望得到快速排序3.0的时间复杂度为O(n*logN)

快速排序3.0思路讲解
在1.0版本上进行修改，每一次不是选取最左侧元素作为pvoit，而是随机选取一个元素作为pvoit，然后于最左侧元素互换，其他思路完全一样
快速排序3.0code

#include<iostream>
#include<vector>
using namespace std;

int Paritition1(vector<int>& Arr, int low, int high) {
    int rand_num = (rand() % (high - low + 1)) + low;

    swap(Arr[low], Arr[rand_num]);
    int pivot = Arr[low];
    while (low < high) {
        while (low < high && Arr[high] >= pivot) {
            --high;
        }
        Arr[low] = Arr[high];
        while (low < high && Arr[low] <= pivot) {
            ++low;
        }
        Arr[high] = Arr[low];
    }
    Arr[low] = pivot;
    return low;
}

void Quick_Sort(vector<int>& Arr, int low, int high) //快排母函数
{
    if (low < high) {
        int pivot = Paritition1(Arr, low, high);//占一个额外空间复杂度
        Quick_Sort(Arr, low, pivot - 1);
        Quick_Sort(Arr, pivot + 1, high);
    }
}
int main()
{
	vector<int> Arr{ 3,5,3,7,4,6,5,8 };
	int L = 0;
	int R = Arr.size() - 1;
	Quick_Sort(Arr, L, R);
	for (int i = 0; i < Arr.size(); i++)
		cout << Arr[i] << " ";
	return 0;
}

快速排序额外度分析
每次递归都要储存一个pvoit的值，最差结果就是O(N);最好的结果就是每次的pvoit都差不多是中间位置，空间复杂度为O(logN)
快速排序题目
912排序数组

未完待续

桶排序

拓扑排序

力扣207

堆排序

最大堆

使用二叉树构建大根堆

#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) {
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { 
        if (son + 1 <= end && arr[son] < arr[son + 1]) 
            son++;
        if (arr[dad] > arr[son]) 
            return;
        else { 
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

优先队列依据堆来实现
题目链接：https://leetcode-cn.com/problems/top-k-frequent-elements/submissions/

class Solution {
public:
    static bool cmp(pair<int,int>& P1,pair<int,int>& P2)
    {
        return P2.second < P1.second;   
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> radio_nums;
        for(int n:nums)
        {
            radio_nums[n]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)>  q(cmp);
        for(auto [key,val]:radio_nums)
        {
            if(q.size()==k)
            {
                if(q.top().second < val)
                {
                    q.pop();
                    q.emplace(key,val);
                }
            }
            else
            {
                q.emplace(key,val);
            }
        }
        vector<int> res;
        for(int i=0;i<k;i++)
        {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};