排序算法

1. 计数排序 一共进项了n(n-1)/2次比较和2n次元素移动

//名次计算函数，比较次数为1+2+3+4+...+n-1
template<class T>
void rank(T a[],int n,int r[])
{
for(int i=0;i!=n;++i)
r[i]=0;

for(int i=1;i!=n;++i)
{
for(int j=0;j!=n;++j)
{
if(a[j]<a[i])
++r[i];
else 
++r[j];
}
}
}

//按名次排序，计算出名次后进行排序称为计数排序
template<class T>
void rearrange(T a[],int n,int r[])
{
T*u=new T[n];
for(int i=0;i!=n;++i)
u[r[i]]=a[i];//

for(int i=0;i!=n;++i)
a[i]=u[i]; 

delete [] u;
}

2. 选择排序

//找出最大元素
template<class T>
int indexOfMax(T a[],int n)
{
if(n<=0)
throw illegalParameterValue("n  must be >0")

int indexOfMax=0;
for(int i=1;i<n;i++)
{
if(a[indexOfMax]<a[i])
indexOfMax=i;
return indexOfMax;
}
}
// 选择最大的元素放到数组末尾，数组倒数第二位，...，以此类推
template<class T>
void selectionSort(T a[],int n)
{
for(int size=n;size>1;size--)
{
int j=indexOfMax(a,size);
swap(a[j],a[size-1]);
}
}

//选择排序在元素已经到达正确顺序之后，程序继续运行，进行n-1次迭代

//不断更新数组尾部的size-1
template<class T>
int indexOfMax(T a[],int n)
{
bool sorted=false;
for(int size=n;!sort&&(size>1);size--)
{
int indexOfMax=0;
sort=true;
for(int i=0;i<size;i++)//for循环找出数组中的最大值
{
if(a[indexOfMax]<=a[i])
indexOfMax=i;
else sort=false;
}
swap(a[indexOfMax],a[size-1]);
}
}

可以运行的选择排序

#include <iostream>
#include <vector>
using namespace std;

int selectMaxPos(vector<int>& num, int n){
int maxNum=num[0];
int pos=0;
for(int i=1; i<n; ++i)
{
if(maxNum<num[i])
{
maxNum=num[i];
pos=i;
}
}
return pos;
}

void select_sort(vector<int>& num, int n)
{
for(int i=n; i>0; --i)
{
int pos=selectMaxPos(num,i);
swap(num[pos],num[i-1]);
}
}

int main()
{
vector<int> num{1,4,2,3,7,5,4,9,7};
int n=num.size();
select_sort(num,n);
for(auto c:num)
cout<<c<<" ";
return 0;
}

3. 冒泡排序

//左右相邻比较，左侧元素比右侧大，则左右交换，完成一次冒泡过程之后末尾元素是最大元素
template<class T>
void double(T a[],int n)
{
for(int i=0;i<n-1;i++)
if(a[i+1]<a[i])
swap(a[i],a[i+1]);
}

//冒泡排序
template<class T>
void bubbleSort(T a[],int n)
{
for(int size=n;size>1;size--)
bubble(a,i);
}

//即时终止的冒泡排序
template<class T>
void double(T a[],int n)
{
bool swapped=false;
for(int i=0;i<n-1;i++)
if(a[i+1]<a[i])
{
swap(a[i],a[i+1]);
swapped=true;
}
return swapped;
}
template<class T>
void bubbleSort(T a[],int n)
{
for(int size=n;size>1&&bubble(a,i);size--)
//bubble(a,i)调用bubble()，并判断swapped是否为false
}

可以运行的冒泡排序

#include <iostream>
#include <vector>

using namespace std;

void bubble(vector<int>& num, int n)
{
for(int i=0; i<n-1; ++i)
{
if(num[i+1]<num[i])
swap(num[i],num[i+1]);
}
}

void bubble_sort(vector<int>& num, int n)
{
for(int i=n; i>=0; --i)
{
bubble(num,i);
}
}

int main()
{
vector<int> num{1,4,2,3,7,5,4,9,7};
int n=num.size();
bubble_sort(num,n);
for(auto c:num)
cout<<c<<" ";
return 0;
}

4. 插入排序

1. 在有序数组中插入元素，保持顺序

   template<class T>
   void insert(T [],int &n,const T& x)
   {
   int i;
   //一定会有常量x插入到数组的，比较x与a[i]，数组末尾元素向后移动一位
   for(i=n-1;i>=1&&x<a[i];i--)
   a[i+1]=a[i];
   a[i+1]=x;
   n++;
   }
   
   
   template<class T>
   void insert(T a[],int n,const T&x)
   {
   int i;
   for(i=n-1;i>=0&&x<a[i];i--)
   a[i+1]=a[i];
   a[i+1]=x;
   }
   
   template<class T>
   void inserttionSort(T a[];int n)
   {
   for(int i=1;i<n;i++)
   {
   T t=a[i];
   insert(a,i,t);
   }
   }

可以运行的插入排序

#include <iostream>
#include <vector>
using namespace std;

void insertNum(vector<int>& num, int n)
{
int key=num[n];
int i=n;
while(i>0 && num[i-1]>key)
{
num[i]=num[i-1];
--i;
}
num[i]=key;
}

void insert_sort(vector<int>& num, int n)
{
for(int i=1; i<n; ++i)
insertNum(num,i);
}

int main()
{
vector<int> num{1,4,2,3,7,5,4,9,7};
int n=num.size();
insert_sort(num,n);
for(auto c:num)
cout<<c<<" ";
return 0;
}