四种简单的排序算法C++(2)

选择排序的思路是：对于第一趟，搜索整个数组，寻找出最小的，然后放置在数组的0号位置；对于第二趟，搜索数组的n-1个记录，寻找出最小的（对于整个数组来说则是次小的），然后放置到数组的第1号位置。在第i趟时，搜索数组的n-i+1个记录，寻找最小的记录（对于整个数组来说则是第i小的），然后放在数组i-1的位置（注意数组以0起始）。可以看出，选择排序显著的减少了交换的次数。

需要注意的地方是：在第i趟时，内层循环并不需要递减到1的位置，只要循环到与i相同就可以了，因为之前的位置一定都比它小（也就是第i小）。另外里层循环是j>i，而不是j>=i，这是因为i在进入循环之后就被立即保存到了lowestIndex中。

算法实现(C#) public static void SelectionSort<T, C>(T[] array, C comparer) where C : IComparer<T>

{

int length = array.Length;

for (int i = 0; i <= length - 2; i++) {

Console.Write("{0}: ", i+1);

int lowestIndex = i; // 最小记录的数组索引

for (int j = length - 1; j > i; j--) {

if (pare(array[j], array[lowestIndex]) < 0) lowestIndex = j;

}

swap(ref array[i], ref array[lowestIndex]);

AlgorithmHelper.PrintArray(array);

}

}

输出演示(C#)

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15};

AlgorithmHelper.PrintArray(array);

SortAlgorithm.SelectionSort

(array, ComparerFactory.GetIntComparer());

}

算法实现(C++) // 选择排序

template <class T, class C>

void SelectionSort(T a[], int length) {

for(int i = 0; i <= length-2; i++){ int lowestIndex = i;

for(int j = length-1; j>i; j--){

if(C::Smaller(a[j], a[lowestIndex]))

lowestIndex = j;

}

swap(a[i], a[lowestIndex]);

}

}

4.希尔排序

希尔排序利用了插入排序的一个特点来优化排序算法，插入排序的这个特点就是：当数组基本有序的时候，插入排序的效率比较高。比如对于下面这样一个数组：

int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };

插入排序的输出如下：

可以看到，尽管比较的趟数没有减少，但是交换的次数却明显很少。希尔排序的总体想法就是先让数组基本有序，最后再应用插入排序。具体过程如下：假设有数组int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我们设其长度为length。

第一趟时，步长step = length/2 = 4，将数组分为4组，每组2个记录，则下标分别为(0,4)(1,5)(2,6)(3,7)；转换为数值，则为{42,28}, {20,14}, {17,23}, {13,15}。然后对每个分组进行插入排序，之后分组数值为{28,42}, {14,20}, {17,23}, {13,15}，而实际的原数组的值就变成了{28,14,17,13,42,20,23,15}。这里要注意的是分组中记录在原数组中的位置，以第2个分组{14,20}来说，它的下标是(1,5)，所以这两个记录在原数组的下标分别为

a[1]=14;a[5]=20。

第二趟时，步长 step = step/2 = 2，将数组分为2组，每组4个记录，则下标分别为(0,2,4,6)(1,3,5,7)；转换为数值，则为{28,17,42,23}, {14,13,20,15}，然后对每个分组进行插入排序，得到{17,23,28,42}{13,14,15,20}。此时数组就成了{17,13,23,14,28,15,42,20}，已经基本有序。

第三趟时，步长 step=step/2 = 1，此时相当进行一次完整的插入排序，得到最终结果{13,14,15,17,20,23,28,42}。

算法实现(C#) // 希尔排序

public static void ShellSort<T, C>(T[] array, C comparer)

where C : IComparer<T>

{

for (int i = array.Length / 2; i >= 1; i = i / 2) {

Console.Write("{0}: ", i);

for (int j = 0; j < i; j++) {

InsertSort(array, j, i, comparer);

}

Console.WriteLine();

AlgorithmHelper.PrintArray(array);

}

}

// 用于希尔排序的插入排序

private static void InsertSort<T, C>

(T[] array, int startIndex, int step, C comparer)

where C : IComparer<T>

{

for (int i = startIndex + step; i <= array.Length - 1; i += step) {

int j = i;

while(j>= step && pare(array[j], array[j - step]) <0 ){

swap(ref array[j], ref array[j - step]);

j -= step;

}

}

}

注意这里插入排序InsertSort()方法的参数，startIndex是分组的起始索引，step是步长，可以看出，前面的插入排序只是此处step=1,startindex=0的一个特例。

输出演示(C#)

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15};

AlgorithmHelper.PrintArray(array);

SortAlgorithm.ShellSort

(array, ComparerFactory.GetIntComparer());

}

算法实现(C++) // 希尔排序

template<class T, class C>

void ShellSort(T a[], int length){

for(int i = length/2; i >= 1; i = i/2 ){

for(int j = 0; j<i; j++){

InsertSort<T, C>(&a[j], length-1, i);

}

}

}

// 用于希尔排序的插入排序

template<class T, class C>

void InsertSort(T a[], int length, int step){

for(int i = step; i<length; i+= step){

int j = i;

while(j>=step && C::Smaller(a[j], a[j-step])){

swap(a[j], a[j-step]);

j-=step;

}

}

}

对于上面三种算法的代价，插入排序、冒泡排序、选择排序，都是Θ(n2)，而希尔排序略好一些，是Θ（n1.5），关于算法分析，大家感兴趣可以参考相关书籍。这里推荐《数据结构与算法分析(C++版)第二版》和《算法I~IV（C++实现）——基础、数据结构、排序和搜索》，都很不错，我主要也是参考这两本书。

感谢阅读，希望这篇文章可以给你带来帮助。