基本的排序算法有如下特点：
1.几种容易的算法都是以O(N2)排序的
2.Shell排序编程简单，其也是以O(N2)排序的，在实践中用的很多
3.复杂的排序算法往往都是按照O(NlogN)尽心排序的
4.任何通用的排序算法都需要NlogN次比较。
还有两个定理应该记一下，证明略：
1. N个互异数组的平均逆序数是N(N-1)/4
2. 通过交换相邻元素进行排序的任何算法平均都需要O(N^2)的时间
插入排序
首先当然是插入排序啦，算法的时间复杂度其实是O(N^2)的
先来个一般的描述：
template<typename Comparable>
void insertSort(vector<Comparable> & a)
{
int j;
for (int p = ; p < a.size(); p++)
{
Comparable tmp = a[p];
for (int j = p - ; j > && tmp < a[j - ]; j--)
a[j] = a[j - ];
a[j] = tmp;
}
}
再就是stl的描述，主要分为四个部分，比较麻烦
template <typename Iterator>
void insertionSort(const Iterator & begin, const Iterator & end)
{
if (begin != end)
insertSortionHelp(begin, end, *begin);//用于解析类型
} template <typename Iterator, typename Object>
void insertionSortHelp(const Iterator & begin, const Iterator & end, const Object & obj)
{
insertionSort(begin, end, less<Object>());
} template <typename Iterator, typename Comparator>
void insertionSort(const Iterator & begin, const Iterator & end, Comparator lessThan)
{
if (begin ！ = end)
insertionSort(begin, end, lessThan, *begin);
} template <typename Iterator, typename Comparator, typename Object>
void insertionSort(const Iterator & begin, const Iterator & end, Comparator lessThan, const Object & obj)
{
Iterator j;
for (Iterator p = begin + ; p != end; p++)
{
Object tmp = *p;
for (ｊ = p; j != begin && lessThan(tmp, *(j - )); --j)
*j = *(j - );
*j = tmp;
}
//这整个4个函数组成了一个STL，很麻烦所以一般不用STL界面 }
可以讨论一下插入排序的排序的时间复杂度：
2+3+4+...+n = O(N^2)
还可以总结出来的一个特点是，如果插入排序的的输入数据预先已经排好序号了，那么内层循环会直接跳出，这样时间复杂度就会被降到O(N).
也就是说，对于输入几乎被排序了的序列来说，插入排序将很快完成。
希尔排序
希尔排序其实相当于插入排序的不同间隔的版本，希尔排序的平均时间复杂度实际很大程度的依赖于增量序列的选择，同样可以证明得知其算法复杂度为O(N^2)的。
template<typename Comparable>
void shellSort(vector<Comparable > & a)
{
for (gap = a.size() / ; gap > ; gap /= )
{
for (int i = gap; i < ａ.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;
}
}
}
应该注意一点的是，shell排序的最坏情形的复杂度为O(N^2)
堆排序
堆排序的算法思想其实很简单，先是建立一个堆，建堆时的时间复杂度实际上是O(N)，可以先按照逆序建堆，然后在一个一个的把堆中最大的元素，放到数组的最后一个位置，这个过程的时间复杂度是logN，后面其实相当于还要建立N次堆。所以总的时间复杂度就是Nlog(N)的。要点就是不停的建立新的堆。
template <typename Comparable>
void heapSort(vector<Comparable> & a)
{
for (int i = a.size() / ; i > ; i--)
percDown(a, i, a.size()); //首先是建堆
for (int j = a.size() - ; j > ; j--)
{ //这一步从堆中删除最大值到vector的末尾，这样完成了排序
swap(a[], a[j]);
percDown(a, , j);
}
} inline int leftChild(int i)
{
return * i + ;
} template<typename Comparable>
void percDown(vector<Comparable> & a, int i, int j)
{
int child;
Comparable tmp; for (tmp = a[i], leftChild(i) < n; i = child)
{
child = leftChild(i);
if (child != n - && a[child] < a[child + ])
child++;
if (tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
归并排序
归并排序主要使用了递归的思想，即分治策略，可以证明其算法时间复杂度为Nlog(N)的。
template<typename Comparable>
void mergeSort(vector<Comparable & a>)
{
vector<Comparable> tmpArray(a.size());
mergeSort(a, tmpArray, , a.size() - );
} template <typename Comparable>
void mergeSort(vector<Comparable> & a, vector<Comparable> & b, int left, int right)
{
if (left < right)
{
int center = (left + right) / ;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + , right);
merge(a, tmpArray, left, center + , right);
}
} template<typename Comparable>
void merge(vector<Comparable> & a, vector<Comparable> tmpArray, int leftPos, int rightPos, int rightEnd)
{ //这个下面实际上有一个错误，看的时候要纠正一下
int leftEnd = rightPos - ;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + ;
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 = ; i < numElements; i++, rightEnd--)//这一步拷贝的方法值得注意
a[rightEnd] = tmpArray[rightEnd];
}
快速排序
其算法复杂度最大不超过O(N^2),平均值为O(Nlog(N))
注意快排枢纽元的选取。
将第一个元素作为枢纽元：
很明显的不太合适，如果待排序内容是随机的，那么这样是没有问题的。但是如果输入是预排序的或者是反序的，那么就很糟糕。对于预排序的，这样可能导致排序时间是二次的，但是实际上没有做什么事情。如果对于反序的，这种枢纽元每次都会产生劣质的分割，应为所有元素不是被分到S1就是都被分到S2.
随机取一个元素作为枢纽元：
这是个不错的做法，这样不会一直产生很坏的分割，但是生成随机数是昂贵的，可能会给算法带来很大的负担。
三数中值分割法：
可以取左侧，中间，右边的值的和的平均值作为枢纽元。这种做法是比较理智的。
template<typename Comparable>
void quickSort(vector<Comparable> & a)
{
quickSort(a, , a.size() - );
}
//首先是枢纽元的选取
template<typename Comparable>
const Comparable & median3(vector<Comparable> & a, int left, int right)
{
int center = (left + right) / ;
if (a[center] < a[left])
swap(a[center], a[left]);
if (a[right] < a[left]) //将最小的元素放到vector的最左边，符合要求
swap(a[left], a[right]);
if (a[right] < a[center]) //将最大的元素放到vector的最右边，这也符合要求
swap(a[center], a[right]); swap(a[center], a[right - ]); //将枢纽元放在最右边左侧一个的位置上，符合要求
return a[right - ];
} template <typename Comparable>
void quickSort(vector<Comparable> & a, int left, int right)
{
if (left + <= right)
{
Comparable pivot = median3(a, left, right);
int i = left; j = right - ;
for (;;)
{
while (a[++i] < pivot){}
while (a[--j] > pivot){}
if (i < j) //如果i，j的前后顺序还没有交换，那么这一轮块排还没有结束
swap(a[i], a[j])
else break;
}
swap(a[i], a[right - ]);
quickSort(a, left, i - );
quickSort(a, i + , right);
}
else
insertionSort(a, left, right);<span style="white-space:pre"> </span>//对于小数组，那么采取插入排序性能较好
}<pre name="code" class="cpp">template<typename Comparable>
void quickSort(vector<Comparable> & a)
{
quickSort(a, , a.size() - );
}
简单介绍一个快排算法的展开：快速选择其代码段如下所示,其实相当于快速选择找一个固定的数的版本
template<typename Comparable>
void quickSort(vector<Comparable> & a)
{
quickSort(a, , a.size() - );
}
//首先是枢纽元的选取
template<typename Comparable>
const Comparable & median3(vector<Comparable> & a, int left, int right)
{
int center = (left + right) / ;
if (a[center] < a[left])
swap(a[center], a[left]);
if (a[right] < a[left]) //将最小的元素放到vector的最左边，符合要求
swap(a[left], a[right]);
if (a[right] < a[center]) //将最大的元素放到vector的最右边，这也符合要求
swap(a[center], a[right]); swap(a[center], a[right - ]); //将枢纽元放在最右边左侧一个的位置上，符合要求
return a[right - ];
}
template <typename Comparable>
void quickSelect(vector<Comparable> & a, int left, int right, int k)
{
if (left + <= right)
{
Comparable pivot = median3(a, left, right);
int i = left; j = right - ;
for (;;)
{
while (a[++i] < pivot){}
while (a[--j] > pivot){}
if (i < j) //如果i，j的前后顺序还没有交换，那么这一轮块排还没有结束
swap(a[i], a[j])
else break;
}
swap(a[i], a[right - ]);
if(k <= i)
quickSelect(a, left, i - , k);
else if(k > i+)
quickSelect(a, i + , right, k);
}
else
insertionSort(a, left, right);
}
6.对于大元素的数组排序，由于不断移动的成本很高，所以一般会使用移动指针的方式代替直接的大元素的移动
//首先应该声明一个指针类，其中应该包含比较方法，在用这个指针类去调用quicksort就行了
template<typename Comparable>
class Pointer
{
private:
Comparable * pointee;
public:
Pointer(Comparable * rhs = NULL) : pointee(rhs){} bool operator<(const Pointer & rhs)cosnt
{
return *pointee < *rhs.pointee;
} operator Comparable*()const<span style="white-space:pre"> </span>//转换符号，使得完成从pointer<Comparable>da使得可以
{<span style="white-space:pre"> </span>//直接使用*pointer,这里已经有着隐含着的Comparator*了
<span style="white-space:pre"> </span>{<span style="white-space:pre"> </span>//定义了这个符号之后就可以完成Pointer与Comparable*之间的双向转换！！
<span style="white-space:pre"> </span>return *pointee;
<span style="white-space:pre"> </span>}
};
template<typename Comparable>
void largeObjectSort(vector<Comparable> & a)
{
vector<Pointer<Comparable>> p(a.size());
int i, j, next; for (i = ; i < a.size(); i++)
p[i] = &a[i]; quickSort(p); //下面再依靠指针指向的情况来将数组重新来排列，其中使用到了滑动算法
for (i = ; i < a.size(); i++)
if (p[i] != a[i])
{
Comparable tmp = a[i];
for (j = i; p[j] != &a[i]; j = nextj)
{
nextj = p[j] - &a[]; //这里使用的滑动算法，可以自己画图演示一下
a[i] = *p[j];
p[j] = &a[j];
}
a[j] = tmp;
p[j] = &a[j];
}
}
//大量元素的排序最好直接使用快排算法，注意不要图省事将第一个元素作为枢纽元
//如果考虑编程的简洁性可以使用希尔排序
//堆排序比希尔排序是要慢的
//插入排序一般只用在小或者是基本上已经排好序的输入数据上
//归并排序较为麻烦而且对于CPU的主存排序性能不一定有快速排序好