本文主要回顾排序算法中的冒泡排序与Shell排序，主要有如下内容：
- 一句白话说冒泡排序
- 冒泡排序的具体实现
- 一句白话说shell排序
- Shell排序的具体实现
一句白话说冒泡排序
一句白话说冒泡排序（升序排列）：假设序列长度为n，相邻元素两两比较，大的往后放，第一次完成后，最大的元素就出现在最大索引处；同理，剩下的元素继续这样操作，经过n-1次后排序即可得到一个有序序列。
冒泡排序的具体实现
清单1：冒泡排序具体实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
template<typename T>
void bubbleSort(T arr[], int n)
{
for(int i = 0; i < n - 1; i++)//只需要比较n-1次
{
for(int j = 0; j < n - 1 - i; j++)
{
if(arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]);
}
}
}
return;
}
int main()
{
int a[10] = {10,9,8,7,6,5,3,2,4,1};
bubbleSort(a, 10);
for(int i = 0; i < 10; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
上一篇文章插入排序的插入排序最开始的实现，内层循环也是两两比较，不过他是往前比较，得益于前面的序列是有序的特点，所以插入排序可以提交结束循环。那么在这里的冒泡排序是不是可以优化一下呢，比如已经是有序的情况下就跳出循环：
清单2：优化后的冒泡排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
template<typename T>
void bubbleSort(T arr[], int n)
{
bool notSorted = false;
for(int i = 0; i < n - 1; i++)//只需要比较n-1次
{
for(int j = 0; j < n - 1 - i; j++)
{
if(arr[j] > arr[j+1])
{
notSorted = true;
swap(arr[j], arr[j+1]);
}
}
if(!notSorted)
{
break;
}
}
return;
}
int main()
{
int a[10] = {10,9,8,7,6,5,3,2,4,1};
bubbleSort(a, 10);
for(int i = 0; i < 10; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
一句白话说Shell排序
一句白话说Shell排序（升序排列）：
将整个待排元素序列切割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
PS:可以认为Shell排序是对直接插入排序的一种优化,如果希望能看到比较清楚的图解，可以参考图解排序算法(二)之希尔排序。
由于直接插入排序在元素基本有序的情况下，效率是非常高的，因此希尔排序在时间效率上有较大提高。
Shell排序实现
清单3：头文件shellSort.h1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
void shellSort(T arr[], int n)
{
for(int gap = n / 2; gap > 0; gap /= 2)
{
for(int i = gap; i < n; i++)
{
T e = arr[i];
int j;
for(j = i; j >= gap &&arr[j-gap] > e; j -= gap)
arr[j] = arr[j-gap];
arr[j] = e;
}
}
return;
}
清单4：main函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
int main()
{
int n = 10000;
cout<<"Test for random array,size："<<n<<" range [0, "<<n<<"]."<<endl;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
int *arr1 = SortTestHelper::copyArray(arr, n);
SortTestHelper::testSort("Shell Sort", shellSort, arr, n);
//SortTestHelper::printArray(arr, n);
SortTestHelper::testSort("Insert Sort", insertionSort, arr1, n);
//SortTestHelper::printArray(arr, n);
delete[] arr;
delete[] arr1;
n=100000;
cout<<"Test for random array,size："<<n<<" range [0, "<<n<<"]."<<endl;
arr = SortTestHelper::generateRandomArray(n, 0, n);
arr1 = SortTestHelper::copyArray(arr, n);
SortTestHelper::testSort("Shell Sort", shellSort, arr, n);
//SortTestHelper::printArray(arr, n);
SortTestHelper::testSort("Insert Sort", insertionSort, arr1, n);
delete[] arr;
delete[] arr1;
return 0;
}
注意：SortTestHelper.h和insertionSort.h可参考上一篇文章插入排序，这里就不贴这块代码了。
上面shell排序的实现的步长或者叫增量，选择是从n/2开始，每次再减半，直在结束时1。事实上，它可能有其他更有效的步长选择：
不同的增量将导致不同的效率，除了上述实现的增量选择，还可以选择增量为(1，4,13,40，121，…,3*h+1)，3*h+1 是使用最广泛的增量序列之一,时间复杂度为O( n^3/2 )
下面是其实现:
清单5：shell排序另一种增量选择1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template<typename T>
void shellSort(T arr[], int n)
{
//增量为n/2的一种选择
// for(int gap = n / 2; gap > 0; gap /= 2)
// {
// for(int i = gap; i < n; i++)
// {
// T e = arr[i];
// int j;
// for(j = i; j >= gap &&arr[j-gap] > e; j -= gap)
// arr[j] = arr[j-gap];
// arr[j] = e;
// }
// }
//增量为3*h+1的一种选择
int h = 1;
while(h < n/3)
h = 3 * h + 1;
while(h >= 1)
{
for(int i = h; i < n; i++)
{
T e = arr[i];
int j;
for(j = i; j >=h && arr[j-h] > e; j-=h)
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
return;
}
