排序还是最基础的。
链表的排序总共知道三种，插入、快排、归并。。经过分析之后惊奇的发现链表的快排是稳定的🤣
快排的思想，partition的时候分为三种情况，左 中 右 三段新链表。新数据小于base，接在左边的后面，大于base，接在右边的后边，否则接在中间的后边。
注意选基准值为第一个，第一个作为mid的开头即为稳定排序。
插排的思想，遍历listNode，一个个重新插入即可，插入的时候插在大于自己的位置左边。即为稳定排序，插排适合基本有序或者数据较短的情况。
归并的思想，快慢结点找到中间位置，断开成两段，归并一下即可。
数据的排序就不发了，资料都比较全了我写的也不好。放在最后两个展开的吧，一个是归并不递归，一个是快排不递归，都是python写的。
主要排序应用场景：
冒泡：排行榜
插排：基本有序，小数据
希尔排序：就是间隔从大到小在变的插排。适合当base排序，适合各种情况。速度不行再换别的，算是工具人(排序)了。
归并：各种程度上的稳定排序，空间复杂度O(n)算是比较高了，注意最好不要递归里频繁的开辅助空间，最好事先开好一个O(n)的辅助空间。最好是不递归的更快一点。速度比快排慢。
快排：快，O(1)辅助空间，随机基准位置+三路排序优化，实际中C++的标准sort是快排+插排，所以是不稳定的，但速度比快排的qsort快。想稳定用stable_sort,stable_sort是归并排序。这里产生了疑问，为什么stable_sort用归并排序呢？稳定的快排需要额外O(n)空间和归并应该一样呀。。.(stable_sort是稳定排序的简单证明小程序在最后，C++)
注意快排比归并快一半左右，所以常数差一倍。为啥快一半呢？个人愚见，，可以假设最理想情况下，快排每次切中间。这样快排和归并排序都是一样的切法。
在部分排序中，快排扫描一次，归并扫描两次，归并需要左右扫描到辅助数据里再拷贝原位置所以扫描赋值了两遍，快排是N，那么归并就是2N。
所以二者总复杂度常数差一倍，快排1s归并就需要2s。但是快排最好才是切到中间，所以快排的时间复杂度是归并的一半多一点点。
因为快排的情况是绝大多数情况下接近时间复杂度下界，所以平均复杂度比理想下界慢一点点。(只要随机选择base平均复杂度就比较接近下届了，但很多博客比较排序时间的时候都不写。。。)
但是稳定排序的快排需要辅助数组帮忙，而且是扫描两遍，那么我们就知道了，理想情况下稳定快排和归并时间复杂度一样，但是稳定快排最理想在中间，归并本来就在中间，所以稳定快排复杂度比归并高那么一丁点点。
所以猜测这就是sort用快排打基础，stable_sort用归并原因？
实际时间这里我查阅了不少网上的资料，我真的服了，时间复杂度比较，比个锤子。
首先在很多人的代码里，快排写不对，写个一路快排就当快排也就算了。。然后归并也写不对，比时间？。。。写的时候不用非递归的写法也就算了，最后得出的结论要么是归并排序比快排快，甚至是堆排序比快排快。我整个人都傻了。另一份帖子里归并慢的一批，比堆排序还慢，是快排时间的3倍多？喵喵喵？
我这里找到的一份时间资料，但是他没有给代码。。。个人觉得理论平均时间快排是归并的时间一半朝上都是可以的，最起码代码没写错。
计数排序：用于辅助桶排序，工具人。对数据范围有限但数据很多的情况下非常实用，比如高考成绩全排名。不稳定，但速度是数据个数和数据范围之和的线性关系(O(m)+O(n))。
桶排序：数据切成桶，里面再排序。用于数据非常非常非常多的时候，因为数据特别特别多，需要存到多个电脑里，然后每个电脑当成一个桶或者多个桶，能够获得非常理想的时间复杂度。
C++链表快排、归并、插排
#include <iostream>
#include <stack>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(const int&val0):val(val0),next(nullptr){};
void print()
{
ListNode* cur = this;//常指针不危险
while(cur->next)
{
cout<<cur->val<<"->";
cur = cur->next;
}
cout<<cur->val<<endl;
}
};
void delete_ListNode(ListNode*a)
{
stack<ListNode*>s;
while(a)
{
s.push(a);
a=a->next;}
while(s.empty()==false)
{
ListNode* cur = s.top();
s.pop();
delete cur;
}
return;
}
//链表快排似乎是稳定的
ListNode* qSort_ListNode(ListNode* head)
{
//C++只能有一个返回值呀,所以把部分排序拆开了
//三路快排
if(head==nullptr || head->next==nullptr)return head;
//前中后头结点
ListNode *L = new ListNode(-1);
ListNode *cur_L = L;
ListNode *M = head;
ListNode *cur_M = M;
ListNode *R = new ListNode(-1);
ListNode *cur_R = R;
//凡是递归里new出来的都要在递归里删掉
ListNode *cur = head->next;
while(cur)
{
if(cur->val < head->val)
{
cur_L->next = cur;
cur_L = cur_L->next;
cur = cur->next;
continue;
}
if(cur->val == head->val)
{
cur_M->next = cur;
cur_M = cur_M->next;
cur = cur->next;
continue;
}
if(cur->val > head->val)
{
cur_R->next = cur;
cur_R = cur_R->next;
cur = cur->next;
continue;
}
}
//添加结尾标志符号
cur_L->next = nullptr;
cur_R->next = nullptr;
//数据被分成了三段，分别是左 中 右
//中间与右边接起来
cur_M->next = qSort_ListNode(R->next);
//析构工具人
delete(R);
R=nullptr;
cur_L = qSort_ListNode(L->next);
delete L;
L = cur_L;
if(L == nullptr)return M;
//res代表最左边，不空，要遍历到结尾，导致链表的快排比归并慢一点。当然最根本的原因就是链表快排丧失了随机初始化的base选择和原地swap，而且稳定的快排并不比归并好多少，所以链表的快排并不如归并排序
while(cur_L->next)cur_L = cur_L->next;
//接起来
cur_L->next = M;
return L;
}
//两段链表merge连起来
ListNode* merge_ListNode(ListNode* left,ListNode* right)
{
ListNode* head = new ListNode(-1);
ListNode* cur= head;
while(left && right)
{
if(left->val<=right->val)//<=稳定排序
{
cur->next = left;
left = left->next;
cur = cur->next;
continue;
}else
{
cur->next = right;
right = right->next;
cur = cur->next;
continue;
}
}
if(left)cur->next = left;
if(right)cur->next = right;
cur = head->next;
delete head;
return cur;
}
ListNode* mergeSort_ListNode(ListNode* head)
{
if(head==nullptr || head->next==nullptr)// C++会更倾向于nullptr==head的写法，因为如果不小心==写成=,会报错，nullptr不允许赋值，容易排查出来
{
return head;
}
ListNode *fast = head,*slow = head;
while(fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;//slow停在中间或中间靠左的位置
}
//截成两半
fast = slow->next;
slow->next = nullptr;
head = mergeSort_ListNode(head);
fast = mergeSort_ListNode(fast);
return merge_ListNode(head,fast);
}
//插入
ListNode* insert(ListNode* head,ListNode* insert_ListNode)
{
if(head==nullptr)return insert_ListNode;
if(head->val > insert_ListNode->val)
{
insert_ListNode->next = head;
return insert_ListNode;
}
ListNode *cur = head;
while(cur->next && cur->next->val <= insert_ListNode->val)cur = cur->next;
insert_ListNode->next = cur->next;
cur->next = insert_ListNode;
return head;
}
//插入排序
ListNode *insertSort_ListNode(ListNode *head)
{
if(head==nullptr)return head;
ListNode *L = new ListNode(-1);
ListNode *cur = head;
while(cur)
{
head = head->next;
cur ->next = nullptr;
L->next = insert(L->next,cur);
cur = head;
}
cur = L->next;
delete(L);
return cur;
}
int main()
{
//List A;
//A.print();
ListNode*B = new ListNode(1);
B->next = new ListNode(5);
B->next->next = new ListNode(2);
B->next->next->next = new ListNode(4);
B->next->next->next->next = new ListNode(3);
B->print();
//B = qSort_ListNode(B);
B = mergeSort_ListNode(B);
//B = insertSort_ListNode(B);
B->print();
delete_ListNode(B);
return 0;
} python:没写插排 #qsort_listNode class listNode: def __init__(self,val,next=None): self.val = val self.next = next def print(self): res = [self.val] cur = self.next while cur: res.append(cur.val) cur = cur.next print(res) a = listNode(1) a.next,a.next.next,a.next.next.next,a.next.next.next.next,a.next.next.next.next.next,a.next.next.next.next.next.next=listNode(6),listNode(2),listNode(5),listNode(3),listNode(4),listNode(0) a.print() def partition_listNode(st): if not st or st.next is None: return (None,st,None) base = st #三路切分 left = listNode(-1) mid = listNode(-1) right = listNode(-1) head_l,head_m,head_r=left,mid,right cur = st.next while cur: if cur.val<base.val: left.next = cur left = left.next cur = cur.next continue if cur.val>base.val: right.next = cur right = right.next cur = cur.next continue mid.next = cur mid = mid.next cur = cur.next continue #这一步使得排序变得不稳定了 mid.next = base mid = mid.next #修改方法很简单,把下面注释的加上 #mid.next = None #base.next = head_m.next #head_m.next = base ## left.next =None mid.next = None right.next =None #头结点的下一个才是真正的开头 return (head_l.next,head_m.next,head_r.next) #快排，可以稳定 def qsort_List(st): if not st or st.next is None: return st res = partition_listNode(st) left,mid,right = res[0],res[1],res[2] #右边不空 if right: mid.next = qsort_List(right) res = mid if not left: return res #左边不空 res = qsort_List(left) cur = res #sort的返回值是头结点，如果可以返回头结点和尾节点，这里就不需要走到最后了 #这一步复杂度增加了n，总体复杂度是2nlog(n),还是nlog(n)复杂度 while cur.next: cur = cur.next cur.next = mid return res qsort_List(a).print() #归并排序，稳定 #merge_sort_listNode def merge_listNode(left,right): new = listNode(-1) cur = new while left and right: if left.val<=right.val: cur.next = left cur = cur.next left = left.next else: cur.next = right cur = cur.next right = right.next if left: cur.next = left else: cur.next = right return new.next def merge_sort_listNode(st): if not st or not st.next: return st fast,slow = st.next,st while fast and fast.next: fast = fast.next.next slow = slow.next #slow是中间结点 left_end,right = slow,slow.next left_end.next = None left,right = merge_sort_listNode(st),merge_sort_listNode(right) return merge_listNode(left,right) a = listNode(1) a.next,a.next.next,a.next.next.next,a.next.next.next.next,a.next.next.next.next.next,a.next.next.next.next.next.next=listNode(6),listNode(2),listNode(5),listNode(3),listNode(4),listNode(0) a.print() merge_sort_listNode(a).print()C++：stable稳定肉眼判定
因为数据少了，sort用的是插排，所以我看的一些网上的资料说sort和stable_sort排序结果没区别，我真服了，就几个数据，都掉用插入排序，肯定没区别呀
感兴趣的可以把
for(int j=0;j<500;j++)改小一点，5-15吧，发现两个排序结果一样了，原因就是sort函数调用的是插入排序而不是快排了，插入排序是稳定滴
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <iostream>
#include <cstdlib>
#include <ctime>
#define random(x) rand()%(x)
const int SIZE_CHAR = 6; //生成32 + 1位C Style字符串
using namespace std;
bool less_len(const string &str1, const string &str2)
{
return str1.length() < str2.length();
}
void print(vector<string>&data)
{
for(c:data)cout<<c<<"->";
cout<<endl;
}
int main()
{
string CCH = "_0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
srand(time(0));
vector<string>s1,s2;
for(int j=0;j<500;j++)
{
string tmp;
tmp="";
int size_s = rand()%SIZE_CHAR+1;
for (int i = 0; i < size_s; ++i)
{
int x = rand()/(RAND_MAX /(sizeof(CCH)-1));
tmp.push_back(CCH[x]);
}
s1.push_back(tmp);
s2.push_back(tmp);
}
print(s1);
cout<<endl;
cout<<endl;
cout<<endl;
cout<<endl;
cout<<endl;
sort(s1.begin(),s1.end(),less_len);
cout<<endl;
cout<<endl;
cout<<endl;
cout<<endl;
cout<<endl;
stable_sort(s2.begin(),s2.end(),less_len);
print(s1);
print(s2);
} 快排非递归，两路快排：
def q_sort_bottom(data,st=None,en=None): if not data: return if st is None: st = 0 if en is None: en = len(data)-1 if st>=en: return import queue q = queue.Queue() q.put((st,en)) while(q.empty()==False): cur = q.get() st,en = cur[0],cur[1] import random index = random.randint(st,en) data[index],data[st]=data[st],data[index] l,r = st+1,en base = data[st] index = st while l<=r: #左端点比叫base，小值则交换base和当前左端点，大值则当前左端点和尾端交换 if data[l]<base: data[index],data[l],index,l=data[l],data[index],index+1,l+1 continue if data[l]>base: data[l],data[r],r=data[r],data[l],r-1 continue l+=1 if st<index-1: q.put((st,index-1)) if r+1<en: q.put((r+1,en)) return data print(q_sort(old_data[:])) print(q_sort_bottom(old_data[:]))归并非递归:
写的很丑。。。
#非递归,每次相邻合并一下即可，步长从1自增 def merge(data,l1,r1,l2,r2,data_help): cur_index = 0 t_l1,t_l2=l1,l2 while(l1<=r1 and l2<=r2): if data[l1]<=data[l2]: data_help[cur_index],cur_index,l1,=data[l1],cur_index+1,l1+1 else: data_help[cur_index],cur_index,l2=data[l2],cur_index+1,l2+1 while(l1<=r1): data_help[cur_index],cur_index,l1,=data[l1],cur_index+1,l1+1 while(l2<=r2): data_help[cur_index],cur_index,l2=data[l2],cur_index+1,l2+1 l1,l2=t_l1,t_l2 for index in range(r1-l1+1): data[l1+index]=data_help[index] for index in range(r2-l2+1): data[l2+index]=data_help[index+r1-l1+1] def merge_bottom(data,st = None,en = None): if not data: return None if st is None: st = 0 if en is None: en = len(data)-1 step = 1 data_help = [0]*(en-st+1) while step<=en-st+1: for left in range(st,en-step+1,2*step): l1,r1,l2,r2 = left,left+step-1,left+step,left+2*step-1 if r2>en: r2=en merge(data,l1,r1,l2,r2,data_help) step*=2 print(data) merge_sort(old_data[:]) merge_bottom(old_data[:])非常粗糙简单的桶排序：
#工具人排序 def nums_sort(data): if not data: return [] min_data = min(data) max_data = max(data) nums = [0]*(max_data-min_data+1) for value in data: nums[value-min_data]+=1 cur = min_data for index in range (len(data)): while cur<= max_data and nums[cur-min_data]<=0: cur+=1 nums[cur-min_data]-=1 data[index] = cur return data print(nums_sort(old_data[:])) def bucket_sort(data,K = 10): if not data: return #K桶的大小 桶的大小 = data的范围时，就一个桶，可以退化为计数排序 if K<=0: K = 10 min_data = min(data) max_data = max(data) #//K向下取整，需要多补一个，计数排序返回空[]才可以用extend函数 buckets = [[] for _ in range(1+(max_data-min_data)//K)] for value in data: buckets[(value-min_data)//K].append(value) res = [] for i in buckets: res.extend(nums_sort(i)) return res print(bucket_sort(old_data[:],K=2))
京公网安备 11010502036488号