1、冒泡排序
每一次比较相邻元素的大小，所以一趟比较n-1对相邻位置的数,并在每次发现前面的数大于相邻的后面的数时，交换位置，直到某一趟跑完后发现这一趟没有进行任何交换操作，结束。
最好的情况：正序排列，比较n-1次，移动0次，时间复杂度：O(n)
最坏的情况：逆序排列，比较1+2+3+...+(n-1) = n(n-1)/2,移动n(n-1)/2次，时间复杂度：O(n^2)
//a:待排序的数组；n：数组元素个数
void BubbleSort(int a[], int n)
{
bool tag = true;
int tmp = 0;
for(int i=1; i<n&&tag; i++)
{
tag = false;
for(int j=0; j<n-i; j++)
{
if(a[j] > a[j+1])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
tag = true;
}
}
}
}
2、插入排序
2.1直接插入排序
将一个记录插入到已排好序的有序表中.
最好的情况：正序排列，比较n-1次，时间复杂度：O(n)
最坏的情况：逆序排列，比较n(n-1)/2,时间复杂度：O(n^2)
//直接插入排序
void InsertSort(int a[], int n)
{
int tmp = 0;
int i, j;
for(i=1; i<n; i++)
{
tmp = a[i];
for(j=i; j>0&&tmp<a[j-1]; j--)
a[j] = a[j-1];
a[j] = tmp;
}
}
2.2 折半插入
折半插入减少了比较的次数，但是移动次数不变，所以时间复杂度仍为：O(n^2)
//折半查找
int HalfFind(int a[], int low, int high, int value)
{
int index = 0;
while(low <= high)
{
index = (low + high)/2;
if(value == a[index])
break;
else if(value < a[index])
high = index - 1;
else low = index + 1;
}
return index;
}
//折半插入
void HalfInsertSort(int a[], int n)
{
int tmp = 0;
int i, j;
for(i=1; i<n; i++)
{
if(a[i] < a[i-1])
{
tmp = a[i];
int index = HalfFind(a, 0, i-1, tmp);
for(j=i; j>index; j--)
a[j] = a[j-1];
a[index] = tmp;
}
}
}
3、希尔排序
不断把待排序的对象分成若干个小组，对同一小组内的对象采用直接插入法排序，当完成了所有对象都分在一个组内的排序后，排序过程结束。
基本操作：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量” 的记录组成一个子序列。希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得最好的增量序列。增量序列可以有各种方法，但需要注意：应使增量序列中的值没有除1之外的公因子；并且最后一个增量值必须等于1。
时间复杂度：O(nlogn)
//希尔排序
void ShellSort(int a[], int n)
{
int d = n;
while(d > 1)
{
d = (d + 1)/2;
for(int i=0; i<n-d; i++)
{
if(a[i] > a[d + i])
{
int tmp = a[i];
a[i] = a[d + i];
a[d + i] = tmp;
}
}
}
}
4、选择排序
每次从数列中找出一个最小的数放到最前面来，再从剩下的n-1个数中选择一个最小的，不断做下去。
最坏或者平均，均比较n(n-1)/2 所以最坏和平均的时间复杂度为O(n^2)，他没有什么好的情况。
//选择排序
void SelectSort(int a[], int n)
{
int tmp = 0;
int min = 0;
for(int i=0; i<n; i++)
{
min = i;
for(int j=i+1; j<n; j++)
{
if(a[j] < a[min])
min = j;
}
tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
5、归并排序
时间复杂度:最差、最好、平均都是 O(nlogn)
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void Merge(int a[], int low, int mid, int high, int tmp[])
{
int i = low, j = mid + 1;
int m = mid, n = high;
int k = 0;
while(i<=m && j<=n)
{
if(a[i] <= a[j])
tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while(i<=m)
tmp[k++] = a[i++];
while(j<=n)
tmp[k++] = a[j++];
for(i=0; i<k; i++)
a[low + i] = tmp[i];
}
void mergeSort(int a[], int low, int high, int tmp[])
{
if(low < high)
{
int mid = (low + high)/2;
mergeSort(a, low, mid, tmp); //左边有序
mergeSort(a, mid + 1, high, tmp);//右边有序
Merge(a, low, mid, high, tmp); //两个有序序列合并
}
}
//归并排序
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if(p == NULL)
return false;
mergeSort(a, 0, n-1, p);
delete []p;
return true;
}
6、快速排序
最好：O(nlogn)
最坏：O(n^2) 在元素有序的情况下，最坏。
设置两个指针low和high，初值为low和high，枢轴的关键字为key。首先从high所指的位置起向前搜索找到第一个关键字小于key的记录，和枢轴记录相互交换，然后从low所指位置开始向后搜索，找到第一个关键字大于key的记录，和枢轴记录交换，重复这两步，直至low=high为止。
int Partition(int a[], int low, int high)
{
int tmp = a[low];
int key = a[low]; //枢轴
while(low < high)
{
while(low<high && a[high]>=key) high --;
a[low] = a[high];
while(low<high && a[low]<=key) low ++;
a[high] = a[low];
}
a[low] = tmp;
return low;
}
//快速排序
void QSort(int a[], int low, int high)
{
int loc = 0;
if(low < high)
{
loc = Partition(a, low, high);
QSort(a, low, loc - 1);
QSort(a, loc + 1, high);
}
}
快速排序的最坏情况和最快情况。（下面的内容来自精通八大排序算法系列：一、快速排序算法）
最坏情况发生在划分过程产生的俩个区域分别包含n-1个元素和一个0元素的时候，
即假设算法每一次递归调用过程中都出现了，这种划分不对称。那么划分的代价为O（n），
因为对一个大小为0的数组递归调用后，返回T（0）=O（1）。
估算法的运行时间可以递归的表示为：
可以证明为T（n）=O（n^2）。
亦即，快速排序算法的最坏情况并不比插入排序的更好。
而在同样情况下，插入排序的运行时间为O（n）。
//意思是，把一个元素进行插入排序，即把它插入到有序的序列里，花的时间为n。
再来证明，最快情况下，即PARTITION可能做的最平衡的划分中，得到的每个子问题都不能大于n/2.
因为其中一个子问题的大小为|_n/2_|。另一个子问题的大小为|-n/2-|-1.
在这种情况下，快速排序的速度要快得多。为，
T(n)<=2T（n/2）+O（n）.可以证得，T（n）=O（nlgn）。
总的运行时间为O（nlgn）。各结点中示出了子问题的规模。每一层的代价在右边显示。
每一层包含一个常数c。
有关快速排序的文章，参见：
http://blog.chinaunix.net/uid-26432915-id-3023291.html
http://blog.csdn.net/v_JULY_v/article/details/6116297
参考文章：
http://blog.chinaunix.net/uid-26432915-id-3023292.html
http://blog.csdn.net/lixiang040330624/article/details/4647512