排序算法实现
1.插入排序[cpp]
template <typename Comparable>
void insertionSort(vector<Comparable>& a)
{
int j;
for(int p=1;p<a.size();p++)
{
Comparable tmp=a[p];
for(j=p;j>0&&tmp<a[j-1];j--)
a[j]=a[j-1];
a[j]=tmp;
}
}
有R个逆序，因此运行时间为O(R+N)。若逆序数为O(N)，则以线性时间运行。R为N(N-1)/4，因此为Ω(N^2).
2.希尔排序（有时也叫缩减增量排序）
a.希尔排序（基于插入排序，使用希尔增量）
[cpp]
template <typename Comparable>
void shellsort(vector<Comparable>& a)
{
for(int gap=a.size()/2;gap>0;gap/=2)
for(int i=gap;i<a.size();i++)
{
Comparable tmp=a[i];
int j=i;
for(;j>=gap&&tmp<a[j-gap];j-=gap)
a[j]=a[j-gap];
a[j]=tmp;
}
}
b.希尔排序（基于简单交换排序，使用希尔增量）
[cpp]
void shellsort(int v[],int n)//based on 易做图 exchange sort
{
int gap,i,j,temp;
for(gap=n/2;gap>0;gap/=2)
for(i=gap;i<n;i++)
for(j=i-gap;j>=0&&v[j]>v[j+gap];j-=gap){
temp=v[j];
v[j]=v[j+gap];
v[j+gap]=temp;
}
}
使用希尔增量的希尔排序每一趟排序是插入排序或简单交换排序，因此最坏是O(N^2)的。
3.堆排序
[cpp]
inline int leftChild(int i)//root index is 0
{
return 2*i+1;
}
template <typename Comparable>
void percDown(vector<Comparable>& a,int i,int n)
{
int child;
Comparable tmp;
for(tmp=a[i];leftChild(i)<n;i=child)
{
child=leftChild(i);
if(child!=n-1&&a[child]<a[child+1])//if there is right child
child++;
if(tmp<a[child])
a[i]=a[child];
else
break;
}
a[i]=tmp;
}
template <typename Comparable>
void heapsort(vector<Comparable>& a)
{
for(int i=a.size()/2;i>=0;i--)//buildHeap
percDown(a,i,a.size());
for(int j=a.size()-1;j>0;j--) //deleteMax
{
swap(a[0],a[j]);//通过最大堆将数组以递增序排列，可节省一个辅助数组。
percDown(a,0,j);
}
}
构建堆花费O(N)，然后执行N次deleteMax操作，每次花费O(log N)。因此总运行时间为O(N log N)。
4.归并排序
[cpp]
template <typename Comparable>
void merge(vector<Comparable>& a,vector<Comparable>&tmpArray,int leftPos,int rightPos,int rightEnd)
{
int leftEnd=rightPos-1;
int tmpPos=leftPos;
int numElements=rightEnd-leftPos+1;
while(leftPos<=leftEnd&&rightPos<=rightEnd)
{
if(a[leftPos]<a[rightPos])
tmpArray[tmpPos++]=a[leftPos++];
else
tmpArray[tmpPos++]=a[rightPos++];
}
while(leftPos<=leftEnd)
tmpArray[tmpPos++]=a[leftPos++];
while(rightPos<=rightEnd)
tmpArray[tmpPos++]=a[rightPos++];
for(int i=0;i<numElements;i++,rightEnd--)
a[rightEnd]=tmpArray[rightEnd];
}
template <typename Comparable>
void mergeSort(vector<Comparable>& a,
vector<Comparable>& tmpArray,int left,int right)
{
if(left<right)
{
int center=(left+right)/2;
mergeSort(a,tmpArray,left,center);
mergeSort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}
template <typename Comparable>
void mergeSort(vector<Comparable>& a)
{
vector<Comparable> tmpArray(a.size());
mergeSort(a,tmpArray,0,a.size()-1);//单参驱动多参函数
}
O(N log N)。
5.快速排序
从左向右依次判断，取中间索引为分划枢纽：
[cpp]
//order v ascendent
void qsort(int v[],int left,int right)
{
int i,last;
void swap(int v[],int i,int j);
if(left>=right)
return;
swap(v,left,(left+right)/2);//the element to d
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊