算法1：排序
算法：视频学习网址https://www.bilibili.com/video/BV1W54y1Q7iv?p=1
程序１：插入排序
#include<iostream>
using namespace std;
void swap(int*arr, int i,int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void insertionsort(int *arr, int size) // 传数组不能用引用的方式
{
if(arr==NULL||size<2)
{
return;
}
for(int i = 1;i<size;i++)
{
for(int j = i-1;j>=0&&arr[j]>arr[j+1];j--)
{
swap(arr,j,j+1);
}
}
}
int main()
{
int arr[] = {1, 8, 5, 6, 3, 4 ,9};
int size = sizeof(arr) / sizeof(int);
insertionsort(arr, size);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序２：对数器
程序３：归并排序
#include<iostream> //归并排序
using namespace std;
void mergesort(int* arr,int L,int mid,int R)
{
int help[R-L+1];
int p1 = L;
int p2 = mid+1;
int i = 0;
while(p1<=mid&&p2<=R)
{
help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid)
{
help[i++]=arr[p1++];
}
while(p2<=R)
{
help[i++]=arr[p2++];
}
for(int j = 0;j<sizeof(help)/sizeof(int);j++)
{
arr[L+j] =help[j]; //这里是arr[L+j],而不是arr[j]
}
}
void sortProcess(int* arr,int L, int R)
{
if(L==R)
{
return;
}
int mid = (L+ R)/2;
sortProcess(arr,L, mid);
sortProcess(arr, mid+1,R);
mergesort(arr, L, mid, R);
}
void guibingsort(int *arr,int size)
{
if(arr ==NULL||size<2)
{
return;
}
sortProcess(arr, 0, size-1);
}
int main()
{
int arr[] = {7, 4, 6, 5, 2, 3, 1,9};
int size = sizeof(arr)/sizeof(int);
guibingsort(arr, size);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序４：小和问题
#include<iostream> //小和问题,利用归并排序解决
using namespace std;
int mergesort(int* arr,int L,int mid,int R)
{
int res = 0;
int help[R-L+1];
int p1 = L;
int p2 = mid+1;
int i = 0;
while(p1<=mid&&p2<=R)
{
res+=arr[p1]<arr[p2]?arr[p1]*(R-p2+1):0; //小和问题的关键
help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid)
{
help[i++]=arr[p1++];
}
while(p2<=R)
{
help[i++]=arr[p2++];
}
for(int j = 0;j<sizeof(help)/sizeof(int);j++)
{
arr[L+j] =help[j]; //这里是arr[L+j],而不是arr[j]
}
return res;
}
int sortProcess(int* arr,int L, int R)
{
if(L==R)
{
return 0;
}
int mid = (L+ R)/2;
int res = sortProcess(arr,L, mid)+sortProcess(arr, mid+1,R)+mergesort(arr, L, mid, R); //
return res;
}
void guibingsort(int *arr,int size)
{
if(arr ==NULL||size<2)
{
return;
}
cout<<sortProcess(arr, 0, size-1)<<endl;
}
int main()
{
int arr[] = {5, 4, 2, 1,3};
int size = sizeof(arr)/sizeof(int);
guibingsort(arr, size);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序５：荷兰国旗问题
#include<iostream> //荷兰国旗问题
using namespace std;
void swap(int* arr,int i,int j)
{
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
void helanguoqi(int *arr,int num, int L,int R)
{
int less = L-1;
int more = R+1;
int current = L;
while(current <more)
{
if(arr[current]<num)
{
swap(arr,++less,current++);
}
else if(arr[current]>num)
{
swap(arr,--more,current);
}
else
{
current++;
}
}
}
int main()
{
int arr[] = {5, 4, 2, 1,8};
int size = sizeof(arr)/sizeof(int);
int num = 3;
int L = 0;
int R = size-1;
helanguoqi(arr,num,L,R);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}程序６：快速排序
#include<iostream> //快速排序
using namespace std;
void swap(int* arr,int i,int j)
{
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
int* helanguoqi(int *arr,int L,int R)
{
int less = L-1;
int more = R+1;
int current = L;
int num = arr[R];
while(current <more)
{
if(arr[current]<num)
{
swap(arr,++less,current++);
}
else if(arr[current]>num)
{
swap(arr,--more,current);
}
else
{
current++;
}
}
//int help[]={less,more}; 函数体内部创建的变量都是局部变量，当函数运行结束的时候会释放掉，这句只返回了一个指针，这个指针指向的内容在函数结束也就是return的那一刻之后就已被释放掉了
int *help = new int[2];
help[0] = less;
help[1] = more;
return help;
}
void quicksort(int* arr, int L,int R)
{
if(L<R)
{
int *p = helanguoqi(arr,L,R);
quicksort(arr,L, p[0]); //快排相当于递归的荷兰国旗问题
quicksort(arr,p[1], R);
if(p!=NULL) //将堆区的内容手动释放
{
delete p;
p=NULL;
}
}
}
int main()
{
int arr[] = {5, 4, 2, 1,8, 6};
int size = sizeof(arr)/sizeof(int);
int L = 0;
int R = size-1;
quicksort(arr, L,R);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序７：随机快排
#include<iostream> //随机快速排序
using namespace std;
#include<ctime>
#include <stdlib.h>
void swap(int* arr,int i,int j)
{
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
int* helanguoqi(int *arr,int L,int R)
{
int less = L-1;
int more = R+1;
int current = L;
int random = rand()%(R-L+1)+ L;
int num = arr[random]; // 将这里的num改为随机选取的L到Ｒ上的
while(current <more)
{
if(arr[current]<num)
{
swap(arr,++less,current++);
}
else if(arr[current]>num)
{
swap(arr,--more,current);
}
else
{
current++;
}
}
//int help[]={less,more}; 函数体内部创建的变量都是局部变量，当函数运行结束的时候会释放掉，这句只返回了一个指针，这个指针指向的内容在函数结束也就是return的那一刻之后就已被释放掉了
int *help = new int[2];
help[0] = less;
help[1] = more;
return help;
}
void quicksort(int* arr, int L,int R)
{
if(L<R)
{
int *p = helanguoqi(arr,L,R);
quicksort(arr,L, p[0]); //快排相当于递归的荷兰国旗问题
quicksort(arr,p[1], R);
if(p!=NULL) //将堆区的内容手动释放
{
delete p;
p=NULL;
}
}
}
int main()
{
srand((unsigned)time(NULL));
int arr[] = {5, 4, 2, 1,8, 6};
int size = sizeof(arr)/sizeof(int);
int L = 0;
int R = size-1;
quicksort(arr, L,R);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序８：堆结构
#include<iostream> //堆排序
using namespace std;
void swap(int* arr,int i,int j)
{
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
void heapInsert(int *arr,int i) //生成堆排序的过程
{
while (arr[i]>arr[(i-1)/2])
{
swap(arr, i,(i-1)/2);
i = (i-1)/2;
}
}
void heapify(int *arr,int index,int heapSize) //某一值发生改变重新调整，index为发生值改变的位置，heapSize为堆的大小
{
int left = 2*index+1;
while(left<heapSize)
{
int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left; //左右孩子中最大的下标
largest = arr[largest]>arr[index]?largest:index; //左右孩子中最大的与index的比较
if(largest==index)
{
break;
}
swap(arr,index,largest);
index=largest;
left = 2*index+1;
}
}
void heapsort(int* arr, int size)
{
if(arr==NULL||size<2)
{
return;
}
for(int i = 0;i<size;i++)
{
heapInsert(arr,i); //生成堆排序的过程,先生成大根堆
}
int heapSize = size-1;
swap(arr,0,heapSize--); //交换，将最大值放到数组末端
while(heapSize>0)
{
heapify(arr,0,heapSize);
swap(arr,0,heapSize--);
}
}
int main()
{
int arr[] = {5, 4, 2, 1, 8, 6,13,20,9};
int size = sizeof(arr)/sizeof(int);
heapsort(arr,size);
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<endl;
}
return 0;
}
程序９：比较器（简单实现）
#include<iostream> //比较器
using namespace std;
#include<algorithm> //包含的头文件
class Student
{
public:
Student(int age,int score,string name)
{
this->age = age;
this->score = score;
this->name = name;
}
int age;
int score;
string name;
};
bool compare(Student s1,Student s2) //自定义的排序方式
{
return s1.age<s2.age;
}
void classsort()
{
Student s1(35,66,"tom");
Student s2(20,87,"amy");
Student s3(45,56,"hello");
Student arr[] = {s1,s2,s3};
sort(arr,arr+sizeof(arr)/sizeof(s1),compare); //自带的排序
for(int i = 0;i<3;i++)
{
cout<<arr[i].age<<" ";
cout<<arr[i].score<<" ";
cout<<arr[i].name<<" ";
cout<<endl;
}
}
int main()
{
classsort();
return 0;
}
程序１０：桶排序（重要）
#include<iostream> //桶排序的例子
using namespace std;
#include<algorithm>
#include<limits.h>
int bucket(int num,int size,int max,int min) //应该在几号桶
{
return (num-min)*size /(max-min);
}
int maxGap(int *arr,int size)
{
if(arr ==NULL||size<2)
{
return 0;
}
int minof_arr = INT_MAX; //注意，最小设为最大
int maxof_arr = INT_MIN;
for(int i = 0;i<size;i++)
{
minof_arr = min(minof_arr,arr[i]); //algorithm里的
maxof_arr = max(maxof_arr,arr[i]);
}
if(minof_arr==maxof_arr)
{
return 0;
}
// bool hasNum[size+1]; //某个桶有无数
// int mins[size+1]; //某个桶的最小值
// int maxs[size+1]; //某个桶的最大值
bool *hasNum=new bool[size+1]; //某个桶有无数 //必须将数组开辟在堆区
int *mins=new int[size+1]; //某个桶的最小值
int *maxs=new int[size+1]; //某个桶的最大值
int bid=0;
for(int i=0;i<size;i++)
{
bid=bucket(arr[i],size,maxof_arr,minof_arr);
mins[bid]=hasNum[bid]?min(mins[bid],arr[i]):arr[i];
maxs[bid]=hasNum[bid]?max(maxs[bid],arr[i]):arr[i];
hasNum[bid] = true;
}
int res=0;
int lastMax=maxs[0];
for(int i=1;i<=size;i++)
{
if(hasNum[i])
{
res=max(res,mins[i]-lastMax);
lastMax=maxs[i];
}
}
if(hasNum!=NULL)
{
delete hasNum;
hasNum=NULL;
}
if(mins!=NULL)
{
delete hasNum;
mins=NULL;
}
if(maxs!=NULL)
{
delete hasNum;
maxs=NULL;
}
return res;
}
int main()
{
int arr[] = {4,7,2,3,4,10,2,5,20};
int size = sizeof(arr)/sizeof(int);
cout<<maxGap(arr,size)<<endl;
return 0;
}
剑心互娱一面2人在聊