发布于2021-06-07 21:32 阅读(845) 评论(0) 点赞(3) 收藏(1)
最近在准备考研,正好在学习数据结构的排序,发现下面这位大佬总结的很详细,不过是用java,我得用c++来考试,所有用c++来总结一下。
大多图片均来自于:
作者:三四月事八九月果
java实现10种排序算法
作者:一像素
十大经典排序算法
c++代码学习:天勤考研
思路:
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);
}
思路:
当遍历元素为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);
}
思路:
每次遍历依次找出最小值,放到最前面,
然后继续找出它后面剩余元素的最小值,直到剩余元素只有一个时,遍历完成。
代码:
#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);
}
图片地址:
作者: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);
}
思路:
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);
}
代码:
#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);
}
图片来源
数据结构和算法(二十)基数排序算法
思路:
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);
}
建大顶堆:
代码对应;
每次取出堆中最大的数据:
上面一张的图的作用是为下面做铺垫,因为只有你的数组一开始变为大顶堆的结构,下面这张才能起到作用。上图类似于是下图的初始化
。
代码对应:
思路:
如果对二叉树不了解的可以去看这篇博客
二叉树
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);
}
复杂度分析一般的人都很清楚,但是对于稳定性分析可能不是很清楚。那我这里主要说一下稳定性分析。
稳定性:两个相同的元素在进行相应的排序之后
,如果相同元素之前的相对位置发生了改变
,则证明不稳定
;反之则稳定
。
作者:bbjbbh
链接:http://www.phpheidong.com/blog/article/89868/be5d2abc5029c529251b/
来源:php黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 php黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-4
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!