面试算法之排序算法集锦(二)
right = mid - 1;
else
left = mid + 1;
}
exchange = array[i];
j = i;
while (j > left)
{
array[j] = array[j - 1];
--j;
}
array[left] = exchange;
}
}
5.shell排序
shell排序本身是一种插入排序，它是插入排序的一种改进，排序的思想是：开始按照一定的步长d将序列分成d组，每组内部进行直接插入排序，然后逐步减少步长d，直到步长为1，对整个序列进行一次直接插入排序，使序列最终有序。如下图所示是一个步长为3的初始分组图（取自网络）。
shell排序在开始时步长d较大，分组较多，但每组的元素较少，故各组内直接插入较快，后来步长d逐渐缩小，分组数逐渐减少，而各组的元素数目逐渐增多，但由于之前排过序，使序列较接近于有序状态，所以新的一趟排序过程也较快。因此，shell排序在效率上较直接插人排序有较大的改进。
shell排序很关键的一点就是步长序列的选定，步长序列的选定决定着排序的效率。一般的建议是d(1) = [ n / 2 ]，d(i+1) = [ (d(i) - 1) / 3 ]，一般认为d都取奇数且互素为好，但这并没有得到理论上的证明。最后一个步长一定为1，这是必然的。
关于shell排序的时间复杂度据说很难分校，理论上没用具体结论，只是提出大致为O(nlgn)~O(n^2)之间，大概为O(n^1.3)。。。下面是代码：
[cpp]
/**
* Time Complexity:between O(nlgn)~O(n^2), about O(n^1.3)
* Space Complexity:O(1)
*
* sorted data ; array[low...high]
*/
template
void ShellSort(Type array[], int low, int high)
{
int gap, len;
Type exhange;
len = high - low + 1;
gap = len / 2;
while(gap >= 1)
{
for (int i = low; i < low + gap; ++i)
{
for (int j = i + gap; j <= high; j += gap)
{
exhange = array[j];
int k = j;
while (k > i && exhange < array[k - gap])
{
array[k] = array[k - gap];
k -= gap;
}
array[k] = exhange;
}
}
if(gap == 2 || gap == 3)
gap = 1;
else
gap = (gap - 1) / 3;
}
}
6.快速排序
快速排序是一个很牛逼的排序算法，在现实中有很多应用，有很多算法都是借鉴快速排序的思想来实现的。虽然快排的最坏时间复杂度为O(n^2)，但它的平均性能很好，为O(nlgn)。快排的思想是分治法。每次排序都将序列通过一个主元划分成左右两部分，右部分的元素都比主元大，左边的元素都比主元小，然后分别递归进行左右两部分的排序。快排的主程序结构都如下所示：
[cpp]
/**
* sorted data ; array[low...high]
*/
template
void QuickSort(Type array[], int low, int high)
{
if (low >= high)
{
return;
}
int pivot = QuickSort_Partition(array, low, high);
QuickSort(array, low, pivot - 1);
QuickSort(array, pivot + 1, high);
}
对于划分部分partition，有几种不同的算法，下面介绍三种不同的算法。