本站消息
【建议收藏】数据结构考研常用的8种排序算法
发布于2021-06-07 21:32 阅读(824) 评论(0) 点赞(3) 收藏(1)
最近在准备考研，正好在学习数据结构的排序，发现下面这位大佬总结的很详细，不过是用java，我得用c++来考试，所有用c++来总结一下。
大多图片均来自于：
作者：三四月事八九月果
java实现10种排序算法
作者：一像素
十大经典排序算法
c++代码学习：天勤考研
1.冒泡排序
思路：
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。
代码：
#include <bits/stdc++.h>
using namespace std;
void bubleSort(int arr[],int n)
{
int i,j,flag;
for(i=0;i<n-1;i++)
{
flag=0;
for(int j=0;j<n-1-i;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr[j],arr[j+1);
flag=1;
}
}
//如果flag等于0,证明排序已经完成，不需要继续排序
if(flag==0)
return;
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
bubleSort(arr,15);
printLn(arr,15);
}
2.插入排序
思路：
当遍历元素为i时，依次与它前面的i-1,i-2等比较大小。
当遇到元素小于遍历元素时，循环停止，记录遍历元素i应该插入的位置。
代码：
#include <bits/stdc++.h>
using namespace std;
void insertSort(int arr[],int n)
{
for( int i = 1 ; i < n ; i ++ ) {
int e=arr[i];
int j; // j保存元素e应该插入的位置
for (j = i; j > 0 && arr[j-1] > e; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
insertSort(arr,15);
printLn(arr,15);
}
3.简单选择排序
思路：
每次遍历依次找出最小值，放到最前面，
然后继续找出它后面剩余元素的最小值，直到剩余元素只有一个时，遍历完成。
代码：
#include <bits/stdc++.h>
using namespace std;
void selectSort(int arr[],int n)
{
int i,j,k;
for(i=0;i<n;++i)
{
k=i; //记录最小值
for(j=k+1;j<n;++j)
if(arr[k]>arr[j])
k=j;
swap(arr[i],arr[k]);
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
selectSort(arr,15);
printLn(arr,15);
}
4.希尔排序
图片地址：
作者：the3times
#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[],int n)
{
int temp;
for(int gap=n/2;gap>0;gap/=2)
{
for(int i=gap;i<n;++i)
{
temp=arr[i];
int j;
for(j=i;j>gap&& arr[j-gap]>temp;j-=gap);
arr[j]=arr[j-gap];
arr[j]=temp;
}
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
shellSort(arr,15);
printLn(arr,15);
}
5.快速排序
思路：
1.从数列中挑出一个元素，称为 “基准”。
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码：
#include<bits/stdc++.h>
using namespace std;
void quickSort(int arr[],int low,int high)
{
int temp;
int i=low,j=high;
if(low<high)
{
temp=arr[low];
while(i<j)
{
while(i<j&&arr[j]>=temp)
--j;
if(i<j)
{
arr[i]=arr[j];
++i;
}
while (i<j&&arr[i]<temp)
++i;
if(i<j)
{
arr[j]=arr[i];
--j;
}
arr[i]=temp;
quickSort(arr,low,i-1);
quickSort(arr,i+1,high);
}
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quickSort(arr,0,14);
printLn(arr,15);
}
快速代码的改进：
我比较喜欢第一种，看个人喜欢
#include<bits/stdc++.h>
using namespace std;
int _partition(int arr[],int l,int r){
int v=arr[l];
int j=l;
for(int i=l+1;i<=r;i++){
if(arr[i]<v){
swap(arr[++j],arr[i]);
}
}
swap(arr[l],arr[j]);
return j;
}
void _quickSort(int arr[],int l,int r){
if(l>=r)
return ;
int p=_partition(arr,l,r);
_quickSort(arr,l,p-1);
_quickSort(arr,p+1,r);
}
void quickSort(int arr[],int n){
_quickSort(arr,0,n-1);
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quickSort(arr,15);
printLn(arr,15);
}
6.归并排序
代码：
#include<bits/stdc++.h>
using namespace std;
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
void _merge(int arr[], int l, int mid, int r){
int aux[r-l+1];
for( int i = l ; i <= r; i ++ )
aux[i-l] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l] < aux[j-l] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
void _mergeSort(int arr[], int l, int r){
if( l >= r )
return;
int mid = (l+r)/2;
_mergeSort(arr, l, mid);
_mergeSort(arr, mid+1, r);
_merge(arr, l, mid, r);
}
void mergeSort(int arr[], int n){
_mergeSort( arr , 0 , n-1 );
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
mergeSort(arr,15);
printLn(arr,15);
}
7.基数排序
图片来源
数据结构和算法(二十)基数排序算法
思路：
1.首先看最大位为多少位，例如最大位1100，则有4位。
2.依次遍历所有数据的个位，十位，百位等进行入“桶”(桶是指1~9)。
当遇到有的元素是2位，有的元素是3位时，可以把十位的数据的前面补0
例如：10 100这些数据，我们可以看成010 100进入依次入“桶”。
代码：
#include <bits/stdc++.h>
using namespace std;
int Max_bit(int arr[],int n)
{
int maxSize=arr[0];
for(int i=0;i<n;i++)
if(maxSize<arr[i])
maxSize=arr[i];
return maxSize;
}
void radixSort(int a[],int n) //基数排序
{
queue<int> temp[10];
int mod=10;
int div=1;
int j=0;
int num=0;
int max_bit;
max_bit=Max_bit(a,n);
string s=to_string(max_bit);
max_bit=s.size();
for(int i=0;i<max_bit;i++,mod*=10,div*=10)
{
for(j=0;j<n;j++)
{
num=(a[j]%mod)/div;
temp[num].push(a[j]);
}
int pos=0;
for(j=0;j<10;j++)
{
while(!temp[j].empty())
{
a[pos++]=temp[j].front();
temp[j].pop();
}
}
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
radixSort(arr,15);
printLn(arr,15);
}
8.堆排序
建大顶堆：
代码对应；
每次取出堆中最大的数据：
上面一张的图的作用是为下面做铺垫，因为只有你的数组一开始变为大顶堆的结构，下面这张才能起到作用。上图类似于是下图的初始化。
代码对应:
思路：
如果对二叉树不了解的可以去看这篇博客
二叉树
1)参数解释
1.结构为完全二叉树结构
2.最后一个非叶子结点的下标:n/2-1
3.左孩子结点下标:2*i+1 右孩子结点下标:2*i+2
4.堆结构：大顶堆(根结点比左右孩子结点大)
2）首先思路
1.建立大顶堆结构
2.每次取出最大值
代码：
#include<bits/stdc++.h>
using namespace std;
void sift(int arr[],int low,int high)
{
//j指向的是i的左孩子结点
int i=low,j=2*i+1;
int temp=arr[i];
while(j<high)
{
//比较i的左孩子结点和右孩子结点的大小，谁大就把值赋值给i
if(j<high && arr[j]<arr[j+1])
++j;
if(temp<arr[j])
{
//把左右孩子结点中大的值赋值给i
arr[i]=arr[j];
//把i指向它的孩子结点，把j指向它的左孩子结点
i=j;
j=2*i+1;
}else{
break;
}
}
arr[i]=temp;
}
void heapSort(int arr[],int n)
{
int i;
int temp;
//n/2-1的作用的指向最后一个非叶子结点
//下面代码的作用：把二叉树变为大顶堆的结构
//大顶堆：root结点比左右孩子结点大
//1.建大顶堆
for(i=n/2-1;i>=0;--i)
sift(arr,i,n-1);
//因为上面求出的大顶堆的下标为0处的值一定的最大的。
//所以我们可以把下标被0的值与i的值进行交换
//然后继续让它变为大顶堆，所有它的下标为0处的值一定是最大
//然后只需要把它和i-1的值进行交换就可以了
//循环进行，直到i=0时。
//2.每次取出堆中 最大值
for(i=n-1;i>0;--i)
{
temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
//把下标为0的值变为最大值
sift(arr,0,i-1);
}
}
//打印
void printLn(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
heapSort(arr,15);
printLn(arr,15);
}
9.复杂度分析和稳定性
复杂度分析一般的人都很清楚，但是对于稳定性分析可能不是很清楚。那我这里主要说一下稳定性分析。
稳定性:两个相同的元素在进行相应的排序之后，如果相同元素之前的相对位置发生了改变，则证明不稳定；反之则稳定。
所属网站分类: 技术文章 > 博客
作者：bbjbbh
链接：http://www.phpheidong.com/blog/article/89868/be5d2abc5029c529251b/
来源：php黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
3
0
收藏该文
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力
程序员的那些事(new)
电子书(new)
博客(new)
视频教程(new)
问答(new)
游戏(new)