在学习排序算法之前，首先把我所掌握的排序方法写到这里
非常暴力的遍历…
void foolSort( int* array , int num )
{
int t , temp , tempv;
//一指针遍历整个数组
for( int h=0 ; h<num ; h++ )
{
//二指针依次比较
for( t=h , temp=h ; t<num ; t++ )
{
if( array[t] < array[temp] )
temp=t;
}
//插入
if( h != temp )
{
tempv = array[h];
array[h] = array[temp];
array[temp] = tempv;
}
}
}
排序算法的稳定性
某序列中两个元素的关键字相同时，若排序后二者次序一定不变，则称该排序方法是稳定的
比如，在某个序列中存在两个 key-value <1,56> <1,27> ，如果排序后 56 一定在 27 前面，则稳定
内部排序
内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程
内部排序根据排序过程中所需的工作量来区分，可以分为三类
- 简单的排序方法 O(n^2)
- 先进的排序方法 O(n*log n)
- 基数排序 O(d*n)
插入排序
直接插入排序
直接插入排序是最简单的排序方法，其基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增为1的有序表
代码实现
void insertSort1( int *array , int num )
{
int temp,j;
// 从 index=1 开始遍历，index之前的序列即为 有序序列
for( int i=1 ; i<num ; i++ )
{
// 如果当前 index 大于有序序列最大值(即最后一个元素) ,直接插入到末尾(即只进行 index++ 的操作)
if( array[i] < array[i-1] )
{
// 否则从有序序列末尾开始比较(并移动)直到找到正确的位置，将其插入
temp=array[i];
array[i]=array[i-1];
for( j=i-1 ; array[j-1]<array[j]&&j>0 ; j-- )
array[j]=array[j-1];
array[j]=temp;
}
}
}
与我原来所掌握的排序方法所比较
直接插入排序和我原来所掌握的最笨的排序方法相比，时间复杂度降低了（虽然渐进复杂度一样）
主要就是判断否可以直接查到有序序列末尾(code 8 行)
时间复杂度 O(n^2)
当 n 很小时，直接插入排序是一种很好的排序方法
折半插入排序
折半插入排序在直接插入排序的基础上进行了改进，
我们知道在插入排序中一直存在一个 有序序列 ，所以在进行依次比较的时候(即 code 14 行)时可以用 折半查找 进行比较来减少比较次数，当然，记录移动次数并没有变
void binaryInsertSort( int *array , int num )
{
int temp,high,low,j;
// 从 index=1 开始遍历，index之前的序列即为 有序序列
for( int i=1 ; i<num ; i++ )
{
// 如果当前 index 大于有序序列最大值(即最后一个元素) ,直接插入到末尾(即只进行 index++ 的操作)
if( array[i] < array[i-1] )
{
// 否则从有序序列末尾开始比较(并移动)直到找到正确的位置，将其插入
temp=array[i];
array[i]=array[i-1];
// for( j=i-1 ; array[j-1]<array[j]&&j>0 ; j-- )
// array[j]=array[j-1];
// 折半寻找位置
low=1 , high=i-1;
while( low<=high )
{
if( array[ (high+low)/2 ]<temp )
low=(high+low)/2 + 1;
else
high=(high+low)/2 - 1;
}
for( j=i-1 ; j>high ; j--)
array[j] = array[j-1];
array[j]=temp;
}
}
}
折半算法的正确性
这里阐述一下折半算法的正确性
while( low<=high )
{
if( array[ (high+low)/2 ]<temp )
low=(high+low)/2 + 1;
else
high=(high+low)/2 - 1;
}
在上述代码中，容易知道，最后一次折半之前的状态：
- low==high
- index == high || high+1（这里的 index 是指正确的将元素插入该有序序列之后该元素在新有序序列中的索引）
如果 index == high ，那么最后一次折半后 high–，low==index
如果 index == high+1 ， 那么最后一次折半后 low++ ， low==index
所以 low == index
2-路插入排序
2-路插入排序是在折半插入排序的基础上再改进之，减少排序过程中移动记录的次数，其实现思路是再创建一个与待排序序列相同大小的数组（看成是循环数组，有头指针和尾指针），将待排序序列中第一个记录放在循环数组第一个位置，并将之看成是排序后序列中中间位置的记录
//2-路插入排序
void two_Sort( int* array , int num )
{
int* newArray = (int*)malloc( sizeof(int)*num );
newArray[0] = array[0];
int first=num, final=0, high , low , temp ,j;
for( int i=1 ; i<num ; i++ )
{
//如果待排序元素大于首元素
if( array[i] > newArray[0] )
{
if( array[i] < newArray[final] && final!=0 )
{
low=1;
high=final;
while( low<=high )
{
if( newArray[(high+low)/2]<array[i] )
low=(high+low)/2 + 1;
else
high=(high+low)/2 - 1;
}
for( j=final+1 ; j>low ; j--)
newArray[j] = newArray[j-1];
newArray[low]=array[i];
}else
newArray[final+1]=array[i];
final++；
}
else
//如果待排序元素小于首元素，从数组为倒序插入
{
if( array[i] > newArray[first] && first!=num )
{
low=first;
high=num-1;
while( low<=high )
{
printf("折半比较\n");
if( newArray[ (high+low)/2 ]<array[i] )
low=(high+low)/2 + 1;
else
high=(high+low)/2 - 1;
}
// 这里非常关键，因为在后段插入并不是将插入点后的元素向后移动，而是将插入点前的元素向前移
low--;
for( j=first-1 ; j<low ; j++ )
newArray[j]=newArray[j+1];
newArray[low]=array[i];
}
else
newArray[first-1]=array[i];
first--;
}
}
for( int i=0 ; i<num ; i++ )
printf("%-5d ",newArray[i]);
printf("\n");
}
表插入排序
希尔排序
希尔排序（Shell’s Sort）又称 缩小增量排序（Diminishing Increment Sort），它也是属于插入排序类的方法，但在时间效率上较前几种排序方法有较大的改进
从对直接插入排序的分析得知，其算法时间复杂度为 n^2 ，但是，若待排记录序列为"正序"时，其时间复杂度可以提高到 n ，从另一方面来看，由于直接插入排序算法简单，则在 n 很小时效率也比较高，希尔排序就是从这两点分析出发对直接插入排序进行改进得到的一种插入排序方法
其基本的思想是，先将整个待排序记录序列分割成为若干子序列（子序列中的记录并非连续，而是按照一定的增量）分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序（可以看成增量为 1）
先上代码，直观理解原理之后再深入理解原理
code
//dk 是增量序列 numofDk 是其长度
void shellSort( int* array , int num , int* dk , int numofDk )
{
for( int t=0 ; t<numofDk ; t++ )
{
int temp , j , gap=dk[t];
for( int i=gap ; i<num ; i++ )
{
if( array[i] < array[i-gap] )
{
temp = array[i];
array[i]=array[i-gap];
for( j=i-gap ; j>0 && temp>array[j] ; j-=gap )
array[j]=array[j-gap];
array[j]=temp;
}
}
}
}
####什么是增量？
希尔排序中很重要的一步就是将待排记录序列分成若干个子序列，但是分割序列并非是直接将几个空间上连续的序列划分在一起，而是按照一个 增量 ，比如
array={ 15 ，84 ，62 ，984 ，156 ，65 ， 11 ，75 ，56 }
如果按照增量为3进行划分，那么子序列分别是
{15，984，11}
{84，156，75}
{62，65，56}
即子序列中相邻记录在原序列中的索引差值为增量值
####在有增量的情况下如何进行插入？
我们回忆一下直接插入排序中的插入code
if( array[i] < array[i-1] )
{
temp=array[i];
array[i]=array[i-1];
for( j=i-1 ; array[j-1]<array[j]&&j>0 ; j-- )
array[j]=array[j-1];
array[j]=temp;
}
仔细观察，我们就会发现，直接插入排序算法中的插入可以看成是 增量为1 时的插入
对上述代码稍作修改，将代码中的 1 改成 增量
if( array[i] < array[i-gap] )
{
temp = array[i];
array[i]=array[i-gap];
for( j=i-gap ; j>0 && temp>array[j] ; j-=gap )
array[j]=array[j-gap];
array[j]=temp;
}
####为什么要考虑增量？
实际上在介绍希尔排序算法的时候就已经说明了
基于插入排序的性质
-
对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。
-
但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。
基于以上，出现了希尔排序
很显然，第一趟希尔排序所划分的子序列中记录数是最少的，最后一趟中的则是最多的，换言之，随着希尔排序的进行，增量逐渐较少直至1，所以希尔排序又叫做 缩小增量排序
增量序列如何考虑？
这涉及一些数学上尚未解决的问题，因此，到目前为止尚未由求得一种最好的增量序列，但大量的研究已经得出一些局部的结论
但是可以确定的是，在取增量序列时，要保证增量序列中的值没有除1以外的公因子(即不能是倍数关系)，并且最后一个增量值必须等于 1
##快速排序
###冒泡排序
接下来，我们来讨论一类借助 交换 进行排序的方法，其中最简单的一种就是人们所熟知的 起泡排序 (Bubble Sort)
起泡排序的过程很简单
首先将第一个记录的关键字和第二个记录的关键字进行比较，如果为逆序，则交换，然后比较第二、第三个记录，依次类推直至比较 第 n 个与第 n-1 个
上述过程称作第一趟起泡排序
然后进行第二趟起泡排序，对前 n-1 个记录进行同样操作
每一趟都会有最小(最大)的记录移动到序列末
code
void buddleSort( int* array , int num )
{
int j , temp , change;
for(int i=1 , change=true ; i<num && change;i++)
{
change=false;
for(j=1;j<num-i+1 ;j++)
{
if( array[j-1] > array[j] )
{
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
change=true;
}
}
}
}
冒泡排序的改进 - 快速排序
快速排序的思路是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
分割需要一个枢轴(pivot key,即分割后的两部分的分界线)，一般选择array[0]
####分割（partition）的算法
- 首先需要两个辅助指针，high low 分别指向序列的尾与首
之后需要一个辅助数据来记录枢轴
int low=0 , high=num-1 , pivotKey=array[0];
-
high 从初始位置一直向前比较，找到第一个比 pivotKey 小的记录，将其与枢轴（此时枢轴就是 array[low] ，因为 low 的初始值是0）交换
-
low 从初始位置一直向后比较，找到第一个比 pivotKey 大的记录，将其与枢轴（此时枢轴就是 array[high] ，因为 在步骤2 中，枢轴已经与 array[high] 交换 ）
-
high 继续向前比较，找到第一个比 pivotKey 小的记录，将其与枢轴（此时枢轴就是 array[low] ，因为 步骤3 中，枢轴已经与 array[low] 交换)交换
-
low 继续向后比较，找到第一个比 pivotKey 小的记录，将其与枢轴（此时枢轴就是 array[high] ，因为 步骤4 中，枢轴已经与 array[high] 交换)交换
-
一直重复 步骤 3-4 ，直到 low==high(实际上 步骤5-6 也是对 步骤3-4 的重复)
思路清晰，我们很容易写出代码
void Partition( int* array , int num )
{
int temp , low=0 , high=num-1 , pivotKey=array[0];
while( low<high )
{
while( low<high && array[high] > pivotKey ) high--;
temp=array[low];
array[low]=array[high];
array[high]=temp;
while( low<high &&array[low] < pivotKey ) low++;
temp=array[low];
array[low]=array[high];
array[high]=temp;
}
}
分割算法的改进
在上文中的分割算法中，每一次记录交换都是三次赋值，但实际上我们可以简化之，因为只当 high==low 的时候 pivotKey 的位置才确定，所以我们可以将上述代码简化成单项复制，这样每次“交换”记录只需赋值一次
void Partition( int* array , int num )
{
int low=0 , high=num-1 , pivotKey=array[0];
while( low<high )
{
while( low<high && array[high] > pivotKey ) high--;
array[low]=array[high];
while( low<high &&array[low] < pivotKey ) low++;
array[high]=array[low];
}
array[high]=pivotKey;
printf("low:%d\nhigh:%d\n",low,high);
}
正确性容易验证，不做赘述
快速排序算法实现
利用上文中的分割算法，我们就可以写出快速排序算法
int partition( int* array , int num )
{
int low=0 , high=num-1 , pivotKey=array[0];
while( low<high )
{
while( low<high && array[high] > pivotKey ) high--;
array[low]=array[high];
while( low<high &&array[low] < pivotKey ) low++;
array[high]=array[low];
}
array[high]=pivotKey;
return low;
}
void quiteSort( int* array , int num )
{
if( num > 1 )
{
int low=partition( array,num );
quiteSort( array , low );
quiteSort( array+low+1 , num-1-low );
}
}
其中对分割函数稍加改进，使其返回分割之后的枢轴索引，以便后续递归
待排序记录序列分割之后形成的两个新序列可以表示为
newArray1 = array ，newNum1=low
newArray2 = array+low+1 ，newNum=num-1-low
快速排序性能分析
快速排序的平均时间为 kn*log(n)，其中 n 为待排序序列中记录的个数，k为某个常数
就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
由于使用了递归，所以快速排序的空间复杂度较高，如果每次排序之后枢轴位置均偏向子序列的一端，则为最坏情况，函数递归栈的最大深度为 n ，如果在一趟排序之后分别比较分割得到的两个子序列并优先处理长度较短的序列，则栈的最大深度可以降为 log(n)
选择排序
选择排序的基本思想是，每一趟在 n-i+1(i=1,2,3,4…n-1)个纪录中选取关键字最小的记录作为有序序列中第 i 个记录
其中最简单且为读者最熟悉的是简单选择排序
简单选择排序
我操，突然发现在没有学习排序算法之前我唯一掌握的排序算法就是简单选择排序！操！操！操！
哎，再贴一边代码
//void foolSort( int* array , int num ) 不好意思，名字打错了
void selectSort( int *arrat , int num )
{
int t , temp , tempv;
//一指针遍历整个数组
for( int h=0 ; h<num ; h++ )
{
//二指针依次比较
for( t=h , temp=h ; t<num ; t++ )
{
if( array[t] < array[temp] )
temp=t;
}
//插入
if( h != temp )
{
tempv = array[h];
array[h] = array[temp];
array[temp] = tempv;
}
}
}
好了，我们又该考虑一下如何改进这个算法了