比较型排序算法总结

增量排序(shell 排序)：该算法的复杂度要略小于插入排序算法，但是也基本上认为是亚O(N^2)。实现的基本过程如下，选择一个较大的增量gap，一般选择为数组长度的一般作为起始的增量。然后从当前增量作为起始下标开始访问，比较a[i]和a[i-gap],如果a[i] a[0]，这是已经处理过的。如果a[i] >

但是存在一个特殊情况，如果操作的数组只存在两个数据时，这种划分方法就存在一些问题，因为一开始两个下标i,j就指向了相同的位置，这时候如果a[0]大于a[1] ，那么经过上面的操作以后j = 0, i = 1，这时候的pivot应该是放在a[1]处，但是根据上面的条件可知，集合划分至少需要三个元素，但是我们可以比较枢纽元与当前a[j]的值，对于两种情况下都满足交换的条件就是a[j] < pivot,因此只要当这个条件满足是就交换a[j]和a[0]。上述的操作我们称之为集合划分操作。

int Partition(int *a, int left, int right)
{
/*采用第一个元素作为枢纽元*/
int pivot = a[left];
int i = left + 1;
int j = right;

/*只有一个元素，实际上不用进行任何操作，直接返回*/
if(i > j)
return j;

/*实际上存在一个问题就是i== j，这时候数组有两个值*/
while(1)
{
/*跳过所有小于等于pivot的值，同时设置边界条件*/
while(a[i] <= pivot && i < right)
++ i ;
/*跳过所有大于pivot的值，同时设置边界条件*/
while(pivot < a[j] && j > left)
-- j ;
/*******************************************
*如果 i < j，则说明数组之间存在间隔
*上面的条件全部不满足则说明找到S1，S2需要交换的数
*一般当存在相同的数时，会存在i == j，这时实际上
*a[left] = a[j]
*一般都会产生i > j,这种情况发生在i+1=j时的交换操作
*交换操作完成以后i++,j--，使得i < j.
*******************************************/
if(i < j)
swap(&a[i ],&a[j]);
else
break;
}
/******************************************************
根据上面的分析实际上j下标指向的数数都是小于或者等于pivot的
等于pivot时就不需要交换a[left]和a[j],只需要返回枢纽元应该的位置即可，
同时也解决了只有两个数值的数组问题。
*******************************************************/
if(pivot > a[j])
swap(&a[left],&a[j]);
/*返回枢纽元应该存在的位置*/
return j;
}

/*传统的快速排序算法*/
void t_quickSort(int *a, int left, int right)
{
int i = 0;

/*如果left小于right*/
if(left < right)
{
/*找到枢纽元的位置，并划分了两个集合S1,S2*/
i = Partition(a,left,right);
/*S1集合排序*/
t_quickSort(a, left , i - 1);
/*S2集合排序*/
t_quickSort(a, i + 1, right);
}
}

但是这种方法存在一个比较严重的问题，就是如果当数组是一个已经完成排序的情况，采用快速排序的时间复杂度将是灾难性的。此时的时间复杂度为O(N^2),也就是最坏的情况，为了解决这种问题，采用了其他的解决方案，改变枢纽元的选择决策，采用随机选取或者三值的中值作为枢纽元。枢纽元的选择能避免有序数组的快速排序问题。还有就是当数组的长度较小时，采用插入法等常规方法的速度更快，而且如上面分析所示，划分集合的问题至少需要三个元素，虽然上面的方法能够解决只有两个元素的情况，但是如果考虑不周全就很难解决。可以根据长度来选择具体的排序排序方法，也就是当长度小于10时采用插入法排序，而当大于10时就直接采用快速排序，这时候的注意事项就比较少，不用考虑数组长度是否为2等。采用改良型的快速排序算法如下所示。

/*快速排序*/
void insertionSort(int *a, int left, int right)
{
int i = 0, j = 0;
int tmp = 0;
if(left >= right)
return;

for( i = left + 1; i <= right; ++ i)
{
tmp = a[i];
for(j = i; j > left && tmp < a[j - 1]; -- j)
a[j] = a[j - 1];
a[j] = tmp;
}
}

/*数据交换*/
void swap(int *a, int *b)
{
if(a != b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
}

/*选择合适的枢纽元函数*/
int median(int *a, int left, int right)
{
int mid = (right + left) / 2;

if(a[mid] < a[left])
swap(&a[mid], &a[left]);
if(a[right] < a[left])
swap(&a[right], &a[left]);
if(a[right] < a[mid])
swap(&a[right], &a[mid]);

swap(&a[mid],&a[right - 1]);

return a[right - 1];
}

/*实现快速排序的实际函数*/
void quickSort(int *a, int left, int right)
{
int i = left, j = right - 1;
int pivot = 0;
if(left + 10 <= right)
{
/*选择枢纽元*/
pivot = median(a,left,right);

while(1)
{
/*找到大于pivot的下标*/
while(a[++ i] <= pivot){}
/*找到不大于pivot的下标*/
while(a[--j] > pivot){}

if(i < j)
swap(&a[i],&a[j]);
else
break;
}
/*确定枢纽元的位置*/
swap(&a[i],&a[right - 1]);
quickSort(a,left,i - 1);
quickSort(a,i + 1,right);
}
else/*小长度的数组采用插入法排序*/
insertionSort(a, left,right);
}

void QuickSort(int *a, int size)
{
quickSort(a,0,size - 1);
}