冒泡排序、插入排序、选择排序、归并排序、快排、堆排序
冒泡排序、插入排序、选择排序,这种简单的时间复杂度是O(n2)
归并排序、快排、堆排序时间复杂度O(nlogn)
#include <iostream>
using namespace std;
template<class type> void arr_show(type arr[],int L,int R);
template<class type> void sort_bubble(type arr[],int L,int R)//冒泡排序排数组arr[L,R) 左闭右开
{
for(int i=R-1;i>L;i--)
{
for(int j=L;j<i;j++)
{
if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);
}
}
}
template<class type> void sort_insert(type arr[],int L,int R)//插入排序
{
for(int i=L+1;i<R;i++)//从L+1 到R-1的数都要向前找对应位置
{
for(int j=i-1;j>=L;j--)
{
if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);
else break;
}
}
}
template<class type> void sort_choice(type arr[],int L,int R)//选择排序
{
//从待选序列选出最小的放在生成序列最后面
//简单来说就是依次选出最小的放在位置L L+1 L+2 ...R-2
for(int i=L;i<R-1;i++)//放在i位置
{
int MIN=arr[i];//先假定arr[i]是目前最小的数
int MIN_index=i;//记录最小数的下标
for(int j=i+1;j<R;j++)//遍历带选择序列【i+1 R-1】
{
if(arr[j]<MIN)
{
MIN=arr[j];
MIN_index=j;
}
}
swap(arr[i],arr[MIN_index]);//把最小的数放在i位置 i位置得数放在待选则序列中
}
}
template<class type> void sort_merge(type arr[],int L,int R)//归并排序
{
if(R-L<=1)return;//不够两个元素不需要排
int middle=(R+L)/2;
sort_merge(arr,L,middle);
sort_merge(arr,middle,R);
//开始归并(merge)
type *box=new type[R-L];//开辟与原数组相同大小的空间
int arrow1=L;
int arrow2=middle;
int I=0;
while(arrow1<middle && arrow2<R)
{
box[I++]=arr[arrow1]<arr[arrow2]?arr[arrow1++]:arr[arrow2++];
}
while(arrow1<middle)
{
box[I++]=arr[arrow1++];
}
while(arrow2<R)
{
box[I++]=arr[arrow2++];
}
//复制回去
for(int i=L;i<R;i++)
{
arr[i]=box[i-L];
}
delete[] box;
}
template<class type> void sort_quick(type arr[],int L,int R)//快排
{
if(R-L<=1)return;
int r1=L; //小于区域 【L,r1)
int r2=R; //大于区域 【r2,R)
int num=arr[L]; //把arr[L]当做基准数
int i=L;
while(i<r2) //
{
if(arr[i]<num)
{
swap(arr[i++],arr[r1++]);
}
else if(arr[i]>num)
{
swap(arr[--r2],arr[i]);
}
else i++;
}
sort_quick(arr,L,r1);
sort_quick(arr,r2,R);
}
template<class type>
class heap
{
private:
type *H;
int length;
int now_size;
public:
heap(type arr[],int L,int R):length(R-L)//建大顶堆
{
H=new type[length];
for(int i=0;i<length;i++)
{
H[i]=arr[L+i];
adjust_up(i);
}
}
~heap()
{
delete[] H;
}
void sort_myheap()
{
now_size=length;
for(int i=length-1;i>0;i--)
{
swap(H[0],H[i]);//依次将堆顶元素与堆最后一个元素交换
now_size--;
adjust_down(0); //堆顶元素向下调整
}
}
void adjust_down(int loc)
{
int max_index;
while(loc*2+1<now_size)
{
if(loc*2+2<now_size && H[loc*2+2]>H[loc*2+1])max_index=loc*2+2;
else max_index=loc*2+1;
if(H[max_index]>H[loc])
{
swap(H[max_index],H[loc]);
loc=max_index;
}
else break;
}
}
void adjust_up(int locate)
{
while(H[(locate-1)/2]<H[locate])
{
swap(H[(locate-1)/2],H[locate]);
locate=(locate-1)/2;
}
}
void paste(type arr[],int L)
{
for(int i=0;i<length;i++)
{
arr[L+i]=H[i];
}
}
int get_length(){return length;}
};
template<class type> void sort_myheap(type arr[],int L,int R)//堆排序
{
heap<int> Heap(arr,L,R);
Heap.sort_myheap();
Heap.paste(arr,L);
}
template<class type> void arr_show(type arr[],int L,int R) //打印数组arr[L,R)的值
{
for(int i=L;i<R;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
int arr[10]={4,5,1,3,6,9,7,8,5,0};
int arr2[10]={4,5,1,3,6,9,7,8,5,0};
int arr3[10]={4,5,1,3,6,9,7,8,5,0};
int arr4[10]={4,5,1,3,6,9,7,8,5,0};
int arr5[10]={4,5,1,3,6,9,7,8,5,0};
int arr6[10]={4,5,1,3,6,9,7,8,5,0};
sort_bubble(arr,0,sizeof(arr)/sizeof(int));
arr_show(arr,0,10);
sort_insert(arr2,0,sizeof(arr)/sizeof(int));
arr_show(arr2,0,10);
sort_choice(arr3,0,sizeof(arr)/sizeof(int));
arr_show(arr3,0,10);
sort_merge(arr4,0,sizeof(arr4)/sizeof(int));
arr_show(arr4,0,sizeof(arr4)/sizeof(int));
sort_quick(arr5,0,sizeof(arr5)/sizeof(int));
arr_show(arr5,0,sizeof(arr5)/sizeof(int));
sort_myheap(arr6,0,sizeof(arr6)/sizeof(int));
arr_show(arr6,0,sizeof(arr6)/sizeof(int));
return 0;
}