数据结构|各种排序算法梳理|复习版-创新互联
👋本篇基于Fire_Cloud_1大佬的超棒博客和菜鸟教程的排序算法教程，并结合以往笔记，对所涉及到的排序算法进行梳理，主要用于期末复习😓，重点侧重于算法思想。
成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站设计、成都网站设计、武陵网络推广、重庆小程序开发公司、武陵网络营销、武陵企业策划、武陵品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；成都创新互联为所有大学生创业者提供武陵建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com
👋学习目标
- 能清楚给定一个序列在不同排序算法下不同趟后的结果（明确思路）
- 知道相关特征（复杂度、稳定性）
🚀冒泡排序
🔔动图演示👉笔记博客链接：实验2 排序算法
每次冒泡依次比较相邻元素，并将相邻元素的较大(小)元向右移动，每一次会把大(小)的换至最右，并重复这一操作。
🔔代码实现💯数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到
size-1次，后面的比较没有意义的。如何优化❓
- 设置标志位judge
- 如果发生了交换，judge设置为true；如果没有交换就设置为false。
- 这样当一轮比较结束后如果judge仍为false即这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去，实现及时终止。
templatevoid bubbleSort(T *array,int n)
{int temp;//交换用临时变量
bool judge = true;//标志是否继续交换
for (int i = 0;judge && (i< n-1);i++)
{//每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
bool judge = false;
for(int j = n-1;j >i;j--)
{//把array[0:n-1]中大元素移到右边
if(array[j]< array[j-1])
{ temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
//只要有发生交换，judge就置为true
judge = true;
}
}
}
} 👉时间复杂度：O( n 2 n^2 n2)
🚀选择排序
🔔动图演示👉笔记博客链接：实验2 排序算法
遍历全部数组，把最小的往前排（把大的往后排也可以）
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
…
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
💯数据的顺序排好之后，选择排序算法仍然会继续进行下一轮的选择，直到n-1次，后面的比较同样也是没有意义的，优化方法同冒泡排序，实现及时终止。
- 设置标志位judge
- 如果发生了最小值(大值)更新，judge设置为true；如果没有就设置为false。
- 这样当一轮比较结束后如果judge仍为false即说明数据的顺序已经排好，没有必要继续进行下去，实现及时终止。
templatevoid selectionSort(T *array,int n)
{int temp;
bool judge = true;
for(int i = 0;judge && (i< n-1);i++)//终止条件
{int Min = i;
judge = false;
for(int j = i+1;j< n;j++)
{ if(array[Min] >array[j]) Min = j;
else judge = true;
}
if(Min != i)
{ int temp = array[i];
array[i] = array[Min];
array[Min] = temp;
}
}
} 👉时间复杂度：O( n 2 n^2 n2)
🚀插入排序
🔔动图演示👉笔记博客链接：实验2 排序算法
把每一个元素依次作为插入元素 ，找到合适的位置插入，维护一个有序列。（就和玩扑克牌理扑克牌顺序一个道理）
🔔代码实现
- 采用升序插入排序，即先把数组的第一个元素视为已排序元素
- 后将第二个元素拿去插入，若比第一个小，就插到第一个前，反之插到其后
- 再把第三个元素拿去插入，和前两个元素都比较，找到合适的位置。
- 以此类推。
templatevoid insertSort(T *array,int n)
{for (int i = 1;i< n;i++)
{T x = array[i];//把每一个元素依次作为插入元素
int j;
for(j = i-1;j >= 0 && x< array[j];j--)
{ array[j + 1] = array[j];
}
array[j + 1] = x;
}
} 👉时间复杂度：O( n 2 n^2 n2)
🚀桶排序
🔔动图演示👉笔记博客链接：第六章：线性表链式描述
分配：将待排序的数组(链表)中每一个数根据他们的范围一一放入对应的桶中
排序：在每一个桶的内部分别对其进行排序(这里的排序考虑那些内部排序)
收集：从第一个桶开始，将其中的数据一一放回原数组(链表)
第六章笔记有一个链表桶排序例子
🔔代码实现因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间。
👉有一个范围设定参考公式：范围
gap = (max - min + 1)/桶数👉在元素分配时：
元素值整除(gap + 1)落到对应的桶
针对这一组数据，gap = 9，以下为该组数据的数组实现
void BucketSort(int* a, int n)
{int bucket[5][5];// 分配五个桶。
int bucketsize[5];// 每个桶中元素个数的计数器。
// 初始化桶和桶计数器。
memset(bucket, 0, sizeof(bucket));
memset(bucketsize, 0, sizeof(bucketsize));
// 把数组a的数据按照范围放入对应桶中
for (int i = 0; i< n; ++i)
{bucket[a[i] / 10][bucketsize[a[i] / 10]++] = a[i];
}
// 分别对每个桶中的数据进行排序
for (int i = 0; i< 5; ++i)
{//这里用的是快速排序
QuickSort(bucket[i], 0, bucketsize[i] - 1);
}
// 将把每个桶中的数据依次放回数组a中
int index = 0;
for (int i = 0; i< 5; ++i)
{for (int j = 0; j< bucketsize[i]; ++j)
{ a[index++] = bucket[i][j];
}
}
}👉时间复杂度：O( n + k n+k n+k)，n是数据规模，k是桶数
🚀基数排序
🔔动图演示👉笔记博客链接：第六章：线性表链式描述
将整数按某种基数r切割成不同的数字，然后对数字依次进行排序。一般是按基数10，因此直接按位数分解。
🔔扩展：用队列实现应用举例
(重点关注方法，给出链表序列能给出第n趟之后的序列)
🔑基本思路：
- 每一数位排序要完成分发和回收，且要实现先分发入桶中的数据先回收出来，基于队列后，【分发数据】就是【尾插】，【回收数据】就是【头删】
- 针对要比较几次：在分发数据前我们应该先去求出这些数中大的那个数，然后再求出这个数的位数，那它的位数多少位，那就需要比较多少次
🔑算法图解:
🔑代码实现
#include#define RADIX 10 //表示基数的个数
queuequ[RADIX]; //定义桶（每个桶均为一个队列）
//主体代码
void RadixSort(int* a, int n)
{//首先求出数组中的大值
int max = GetMax(a, n);
//求出大值的位数
int k = GetDigit(max);
//进行k次的数据分发和回收
for (int i = 0; i< k; ++i)
{//分发数据
Distribute(a, n, i);
//回收数据
Collect(a);
}
}
//-------------功能补充------------------
//求解数组中的大值
int GetMax(int* a, int n)
{int max = a[0];
for (int i = 0; i< n; ++i)
{if (a[i] >max)
max = a[i];
}
return max;
}
//求解大值的位数
int GetDigit(int num)
{//num : 10000
int count = 0;
while (num >0)
{count++;
num /= 10;
}
return count;
}
//获取数位逻辑
int GetKey(int value, int k)
{int key = 0;
while(k >= 0)
{key = value % 10;
value /= 10;
k--;
}
return key;
}
//分发数据逻辑
void Distribute(int* a, int n, int k)
{for (int i = 0; i< n; ++i)
{int key = GetKey(a[i], k);
qu[key].push(a[i]);
}
}
//回收数据逻辑
void Collect(int* a)
{int index = 0;
for (int i = 0; i< RADIX; ++i)
{while (!qu[i].empty())
{ a[index++] = qu[i].front();
qu[i].pop();
}
}
} 👉时间复杂度：O( n × k n×k n×k)，n是数据规模，k是桶数
🚀堆排序
🔔动图演示👉笔记博客链接：
- 第十二章：优先级队列，在了解堆排序之前，一定要先学习堆的相关概念
- 实验10.1 堆的操作
将要排序的n个元素初始化为一个大（小）根堆
每次从堆中提取（即删除）元素。
即
初始化+依次pop
- 初建小根堆操作后，
输出一次top，就pop一下，pop完后又是合规的小根堆就又把top输出，这个过程就是如上的依次pop操作从而实现排序，并借助依次输出top(即根)实现了升序输出。
- 如果想让降序输出，可以尝试将每次pop掉的存入栈，存完再出去，依据后进先出，实现小根堆堆排序降序输出。
🔑图解示例
这里贴的就是实验10.1的代码
#includeusing namespace std;
//将一个一维数组的长度从oldLength变成newLength。（后续push操作会用到）
templatevoid changeLengthID(T*& array, int oldLength, int newLength)
{T* newarray = new T[newLength];//函数首先分配一个新的、长度为newLength的数组
int number = (oldLength< newLength) ? oldLength : newLength; //取min {oldLength, newLength}
for (int i = 0; i< number; i++)
newarray[i] = array[i];//然后把原数组的前min {oldLength, newLength} 个元素复制到新数组中
delete[] array;//释放原数组所占用的空间
array = newarray;//将新数组赋值到旧数组完成更改
}
//小根堆定义及实现
templateclass minHeap
{public:
minHeap(int initialCapacity = 10)
{//构造
arrayLength = initialCapacity + 1;
heap = new T[arrayLength];
heapSize = 0;
}
~minHeap() {delete[] heap; }//析构
const T& top()
{//返回优先级大的元素的引用
return heap[1];
}
void pop();//删除
void push(const T&theElement);//插入
void initialize(T*theHeap, int theSize);//初始化
void output(ostream& out) const;//输出
private:
T* heap;//一个类型为T的一维数组
int arrayLength;//数组heap的容量
int heapSize;//堆的元素个数
};
//小根堆的插入
templatevoid minHeap::push(const T& theElement)
{//把元素theElement加入堆
//必要时增加数组长度
if (heapSize == arrayLength - 1)
{//数组长度加倍
changeLengthID(heap, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
//为元素theElement寻找插入位置
//小根堆要求老叶子比新叶子小
int currentNode = ++heapSize;//currentNode从新叶子向上移动，就从最底下开始
while (currentNode != 1 && heap[currentNode / 2] >theElement)
{//这个时候老叶子比新叶子大，不能把元素放在这
heap[currentNode] = heap[currentNode / 2]; //把大的那个元素赋给currentNode，相当于把大的元素往下移
currentNode /= 2;//同时把currentNode（一个打算插入theElement的位置）移向双亲，就往上移
}
//循环结束，即找到合适的位置插入
heap[currentNode] = theElement;
}
//删除操作是针对堆顶元素而言的，即把末尾元素移动到堆顶，再自顶向下(重复构建堆的操作)，递归调整。
templatevoid minHeap::pop()
{//删除堆顶元素
heap[1].~T();
//删除最后一个元素，然后重新建堆（这一步相当于把末尾元素拿出来）
T lastElement = heap[heapSize--];
//开始给拿出来的末尾元素找合适的放入位置，从顶开始，自顶向下调整
int currentNode = 1,
child = 2;//currentNode的孩子
while (child<= heapSize)
{//heap[child]应该是currentNode的更大的孩子（就是说它的值太大了，应该往后头放）
if (child< heapSize && heap[child] >heap[child + 1])
child++;
//可以把lastElement放在heap[currentNode]吗？
//可以
if (lastElement<= heap[child])
break;
//不可以（以下操作和上述push相关操作同理）
heap[currentNode] = heap[child];//把孩子child向上移动
currentNode = child;//向下移动一层寻找位置
child *= 2;
}
heap[currentNode] = lastElement;
}
//初始化一个非空小根堆
templatevoid minHeap::initialize(T* theHeap, int theSize)
{//在数组theHeap[1:theSize]中建小根堆（参考p304-305)
delete[] heap;
heap = theHeap;
heapSize = theSize;
//堆化
for (int root = heapSize / 2; root >= 1; root--)
{T rootElement = heap[root];
int child = 2 * root;
while (child<= heapSize)
{ //heap[child]应该是兄弟中的较小者
if (child< heapSize && heap[child] >heap[child + 1])
child++;
//可以把rootElement放在heap[child / 2]吗?
//可以（原理同上
if (rootElement<= heap[child])
break;
//不可以
heap[child / 2] = heap[child];
child *= 2;
}
heap[child / 2] = rootElement;
}
}
int main(void)
{int m, n;
cin >>n;
minHeapminheap(n);
for (int i = 0; i< n; i++)
{int num;
cin >>num;
minheap.push(num);
}
cout<< minheap.top()<< endl;
cin >>m;
for (int i = 0; i< m; i++)
{int op, num;
cin >>op;
if (op == 1)
{cin >>num;
minheap.push(num);
cout<< minheap.top()<< endl;
}
if (op == 2)
{minheap.pop();
cout<< minheap.top()<< endl;
}
if (op == 3)
{int p;
cin >>p;
minHeapminheap1(p);
for (int i = 0; i< p; i++)
{int number;
cin >>number;
minheap1.push(number);
}
for (int i = 0; i< p; i++)
{cout<< minheap1.top()<< " ";
minheap1.pop();
}
}
}
return 0;
} 👉时间复杂度：O( n l o g n nlogn nlogn)
🚀归并排序
🔔动图演示👉笔记博客链接：第十八章：分而冶之
- 利用分而治之方法进行排序算法：
- 将n个元素按非递增顺序排列
- 若n为1，算法终止；
- 否则
- 将这一元素集合
分割成两个或更多个子集合 - 对每一个子集合
分别排序 - 将排好序的子集合
归并为一个集合
- 将这一元素集合
- 即 先使每个子序列有序，再使子序列段间有序
templatevoid mergeSort(T a[],int n)
{//使用归并排序算法对a[0:n-1]进行排序
T*b = new T[n];
int segmentSize = 1;//段的大小
while(segmentSize< n)
{mergePass(a,b,segmentSize,n);//从a归并到b
segmentSize += segmentSize;
mergePass(b,a,segmentSize,n);//从b归并到a
segmentSize += segmentSize;
}
}
templatevoid mergePass(T x[],T y[],int segmentSize,int n)
{int i = 0;
while(i<= n-2*segmentSize)
{//归并两个大小为segmentSize的相邻段
merge(x,y,i,i+segmentSize-1,i+2*segmentSize-1);
i = i+2*segmentSize;
}
//剩下不足2*segmentSize个元素
if(i+segmentSize< n)
merge(x,y,i,i+segmentSize-1,n-1);
else
for(int j = i;j<= n-1;j++)
y[j] = x[j];//把最后一段复制到y
}
templatevoid merge(T c[],T d[],int startOfFirst,int endOfFirst,
int endOfSecond)
{int first = startOfFirst,//第一段的游标
second = endOfFirst+1,//第二段的游标
result = startOfFirst;//结果段的游标
//当两个被归并段都未处理完，则不断进行归并
while((first<= endOfFirst) && (second<= endOfSecond))
{if(c[first]<= c[second])
d[result++] = c[first++];
else
d[result++] = c[second++];
}
//考虑余下的部分
if (first >endOfFirst)
{//剩下第二段
for(int q = second;q<= endOfSecond;q++)
d[result++] = c[q];
}
else
{for(int q = first;q<= endOfFirst;q++)
d[result++] = c[q];
}
} 👉时间复杂度：O( n l o g n nlogn nlogn)
🚀快速排序
🔔动图演示👉笔记博客链接：第十八章：分而冶之
- 从数列中取出一个数作为
基准数 - 分区
- 将比这个数大的数全放到它的右边
- 小于或等于它的数全放到它的左边
- 再对左右区间重复第二步，直到各区间只有一个数
void Sort(node *array,int low,int high)//排序
{if(low >high) return;//排好了，不运行了
int i,j;
node index;
node index;
index = array[low];//定义基准数
i = low;
j = high;
while(i< j)
{while(i< j && array[j].weight >= index.weight)
{ //从右往左找比基准数小的
j--;
}
if(j >i)
{ //交换array[i]和array[j]，并把i右移一位
array[i++] = array[j];
}
while(i< j && array[i].weight< index.weight)
{ //从左往右找比基准数大的
i++;
}
if(j >i)
{//交换array[i]和array[j]，并把j左移一位
array[j--] = array[i];
}
}
array[i] = index;//基准点归位
Sort(array,low,i-1);//递归调用快排比基准点小的元素
Sort(array,i+1,high);//递归调用快排比基准点大的元素
}👉时间复杂度：O( n l o g n nlogn nlogn)
🚀名次排序补充
🔔一句话思路👉也出现过，所以也放它进来吧，但是它似乎没有趟的概念😢
👉笔记博客链接：实验2 排序算法
先计算每个元素的具体位置，再将其移动到相应位置
🔔代码实现templatevoid rankSort(T *array,int n)
{T *new_array = new T [n];//创建附加数组
int assist[100];
for(int i = 0;i< n;i++)
{ assist[i] = 0;
}
for(int i = 1;i< n;i++)
{for(int j = 0;j< i;j++)
{if(array[j]<= array[i])
assist[i]++;
else
assist[j]++;
}
}
for (int i = 0;i< n;i++)
{//利用辅助数组，按照名次将array[i]暂时贴到新开辟的new_array[]中
new_array[assist[i]] = array[i];
}
for (int j = 0;j< n;j++)
{array[j] = new_array[j];//将数组array重新进行赋值操作
}
delete []new_array;
} 🚀比较总结
- n：数据规模
- k："桶"的个数
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
- 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：数据结构|各种排序算法梳理|复习版-创新互联
文章链接：http://ybzwz.com/article/degosh.html
