数据结构中关于排序问题的总结
序言：排序算法一直是计算机专业很重要的问题之一。尤其在这样的大数据时代，信息爆炸。根据新摩尔定律，每隔18个月人类信息总量就会翻倍。这时，使用合适高效的排序算法会极大提升程序性能。本人学习几大 排序算法之后，颇有感触，姑且总结如下。
一．排序导论
概念：对于给定的含有n个记录的无规则序列，每个序列含有相应的关键字，通过调整这些记录的先后顺序，使序列按照关键字递增或者递减，这就是排序。
稳定性：既然是排序，就免不了有大小相同的元素，这时又该如何处理其前后顺序呢？ 假设k1等于k2，在原序列中，k1在k2之前，在经过排序之后，k1依旧在k2之前，这是我们称这种排序方法是稳定的，否则就是不稳定的。（稳定排序在多关键字排序中极为重要，这里不加赘述）
内排序：排序数量较少，直接装入内存中排序，不需要访问内存
外排序：排序数量太多，无法一次性装入内存，需要在排序过程中实现内存外存的交换
（此次只研究内部排序）
影响排序算法的几大性能：
1. 时间性能
2. 辅助空间
3. 算法复杂度
本次主要研究排序算法如下
简单算法：冒泡排序，简单选择排序，直接插入排序
复杂算法：希尔排序，堆排序，快速排序，归并排序
几大算法的基本关系如下：
排序可以分成插入，选择，交换，归并四种。交换排序里面又有冒泡和快速排序，所以快速排序可以说是更高端的冒泡。插入排序分为直接插入排序和希尔排序。选择排序可以分为简单选择排序和堆排序。
***为了方便起见，以下所用数组弃用0号单元，下标为i的元素就储存第i个元素
排序算法均为升序。
二．三种不同类型的冒泡排序
简介：冒泡排序是很多编程学习者最先接触的排序算法，原因无他，只是简单，时间性能最低。但作为最简单的排序算法，却有三种形式。以下分别叙述。
思想：bubble sort ,冒泡排序，一种交换类型的排序，两两比较相邻关键字的大小，如果反序就交换，直到有序为止。
1. 冒泡排序初级版
C语言实现：
void BubblesSort(inta[],int n)
{
int i,j;
for(i = 1;i < n;i++)
{
for(j = i+1;j <= n;j++)
{
if(a[i] > a[j])
{
swap(a,i,j);//交换元素
}
}
}
return;
}
特点：这甚至不是标准的冒泡，只是两两交换，也并没有利用已经排好的结果
注意，排序时注意利用已经做好的排序，可以极大简化算法。
2. 正宗冒泡排序
C语言实现：
voidBubblesSort(int a[],int n)
{
int i,j;
for(i = 1;i < n;i++)
{
for(j = n-1;j >= i;j--)
{
if(a[j] > a[j+1])
{
swap(a,j,j+1);//交换元素
}
}
}
return;
}
特点：在这样的排序中，较小的序列就像气泡一样慢慢浮现到序列前面，故称冒泡排序
3. 优化的冒泡排序
试着想一下如何利用已经排序好的序列呢？假设序列为2,1,3,4,5,6,7,8,9 也就是只有前两个记录需要交换。若是利用正常冒泡，当交换了前两个之后，算法不会停止，会依旧比较下去。但后面并没有交换，也就是说，我们做了很多无用功！但是，我们第一次比较后，已经知道后面有序了，能不能这时跳出循环结束算法呢？这就是我们改进算法的渠道了。可以设定一个标志flag来判断：
C语言实现：
voidBubblesSort(int a[],int n)
{
int i,j;
bool flag = true;//用来作为标记
for(i = 1;i < n&&flag;i++)//flag为假则退出循环
{
flag = false;
for(j = n-1;j >= i;j--)
{
if(a[j] > a[j+1])
{
swap(a,j,j+1);//交换元素
flag = true; //有数据交换则为true，否则一直为假。
}
}
}
return;
}
这样改动之后，冒泡算法已经有了很大的提升。避免了很多无意义的判断，这也就是很多算法改进的思想。
冒泡排序的复杂度分析;排序的复杂与已给序列有关，若已给序列已经有序，只要比较既可以，无需交换，则时间复杂度为O(N)，最差情况为序列是逆序，这时比较N(N-1)/2次，总的时间复杂度为O(N*N)，且稳定
二．简单选择排序
主要思想：simple selection sort在一个序列中找到最小的，移到第一位。然后对第一位之后的序列排序，依旧找到最小的然后放到最前面。这是对冒泡的改进，冒泡是只要符合规定就交换，而简单选择排序是找到最合适的才交换。
C语言代码实现：
voidSelectSort(int a[],int n)
{
int i,j;
int min;
for(i = 1;i < n;i++)
{
min = i;
for(j = i+1;j <= n;j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(i != -min)
{
swap(a,i,min);
}
}
return;
}
复杂度分析：简单选择的复杂度依旧为O(N*N),但总体性能比冒泡好一点。但是它并不是一种稳定的排序
三．直接插入排序
主要思想：straight insertion sort，将一个记录插入到已经排序好的序列，这时就需要找到适合其的位置，然后依次移动元素，将待插入元素插入。所以其首先要先查找！
C语言实现：
voidInsertSort(int a[],int n)
{
inti,j;
for(i= 2;i <= n;i++)
{
if(a[i]<a[i-1])
{
a[0] = a[i];//监视哨，用于比较和防止数组越界
for(j= i-1;a[0]<a[j];j--)
a[j+1]= a[j];
a[j+1]= a[0];
}
}
return0;
}
时间复杂度：两个循环相套，时间复杂度依旧为O(N*N),但依旧比冒泡和简单选择排序好一点。这是一种稳定的排序
--------------------------以下开始进入复杂排序---------------------------
四．希尔排序
主要思想：shell sort。在直接插入排序中，如果序列已经基本有序，这时效率将特别高。若是记录数比较少，效率也很高。这两个条件都比较苛刻，一般很难实现，但我们能否想办法构造条件呢？这就使希尔排序诞生了。
将已有大量记录的序列分成若干个子序列进行排序，在子序列内进行直接插入，整个序列就基本有序，这时再对总体进行直接插入。总体效率就很高了。将相距某个增量的子序列排序，然后依次缩小增量，保证最后一次增量为1.（增量为1时是对整个已经基本有序序列进行依次扫描，看是否有漏网之鱼）这就是希尔排序，也叫缩小增量排序。
C语言实现：
voidShellSort(int a[],int n)
{
inti,j;
intincrement = n;//初始化为序列长度
do
{
increment= increment/3+1;
for(i= increment+1;i <= n;i++)
{
if(a[i-increment]> a[i])
{
a[0]= a[i];
for(j= i-increment;j>0&&a[0]<a[j];j = j-increment)
a[j+increment] = a[j];
a[j+increment]= a[0];
}
}
}while(increment > 1);
}
复杂度分析：对于希尔排序来说，增量的选取尤为重要，但迄今也没有好的选取方法。它的大致时间复杂度为O(N^1.5)，请注意，这是一次质变的飞跃，复杂度有了很大改进，终于从P(N*N)进化到O(N^1.5),，这使得代码极大优化，才有了后面更加牛逼算法的出现。但由于这时跳跃式的排序，所以并不稳定。
五．快速排序。
在这之前，我想说，快速排序被称为二十世纪十大算法之一，绝对是程序员必备算法，我们有理由掌握
主要思想：quick sort.希尔排序是对直接插入的升级，而快速排序是对冒泡的升级。它增大的记录比较和移动的距离，将大的直接移动到前面，小的直接移动到后面，从而整体上提升效率。
通过一趟排序将待排序的序列分为两部分，前部分的关键字总比后面部分小，在对这两部分依次排序，总而整体排序。
C语言实现：
voidQuick_Sort(int a[],int low,int high)
{
intpivot;
while(low< high)
{
pivot= Partion(a,low,high);//一分为二
Quick_Sort(a,low,pivot-1);
Quick_Sort(a,pivot+1,high);
}
return;
}
Low和high 分别是最小下标和最大下标。Partion函数就是选取一个关键字，想办法让比它小的在它左边，比它大的在它右边，这样的关键字称为枢轴。一般我们选取第一个关键字为枢轴。
下面看看partion的实现：
intPartion(int a[],int low,int high)
{
intpivotkey;
pivotkey= a[low];
while(low< high)
{
while(low< high&&a[high]>=pivotkey)
high--;
swap(a,high,low);
while(low< high&&a[low]<=pivotkey)
low++;
swap(a,high,low);
}
a[low]= pivotkey;
returnlow;
}
算法分析：可以证明，其时间复杂度为O(N*logN)，这比之前的希尔排序还要高效，而这也是目前排序算法所能达到的最好效率（只要它是基于关键字排序）。在最好情况下，每次均匀分布。最坏情况是每次划分的区间中有一个为空，也就是原序列有序，这时快速排序退化成为冒泡。此算法也会造成空间浪费（有递归），但是，这依旧是一个极佳的算法。