这次我们介绍三种排序手写方法：Merge Sort、Quickly Sort 、Shell Sort.
本文排序都使用的字符串组。
Merge Sort
Merge Sort 也称为归并排序，算法如下：
归并排序是将两个已经处理好的上升序列整合在一起成为一个新的上升序列。
算法：将两个序列从左到右依次对比比较，分别设定两个序列的头尾指向，对比此时下标两个序列相对应的数字，小的则放入整合序列中，更新下标，若相等，则任意一个放入整合序列中，若其中一个序列已经放完，则按照顺序将另一个序列全部放入整合序列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void Merge_Sort(string *&s1, int l1, int r1, string *&s2, int l2, int r2, string *&s3)
{
int i1 = l1, i2 = l2;
int len = 0;
while(i1 <= r1 && i2 <= r2)
{
if(s1[i1] >= s2[i2]) s3[++len] = s2[i2++];
else s3[++len] = s1[i1++];
}
for(int i = i1; i <= r1; i++) s3[++len] = s1[i];
for(int i = i2; i <= r2; i++) s3[++len] = s2[i];
}
|
Quickly Sort
Quickly Sort也就是头文件algorithm中的内置sort函数，而且它真的很快！
那么为什么要学习手写呢？因为在一些比赛或考试中不能使用内置函数sort，只能手写。
算法：从数列中取出一个基准数，然后以此为基准，比基准数大的数字都放在它的右边，将比基准数小的数都放在它的左边，然后对左右子区间采用相同的方法，直到每个区间只有一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void Sort(string *&a,int l, int r)
{
string x = a[l];
int i = l, j = r;
if(l >= r) return ;
while(i < j)
{
while(i < j && x <= a[j]) j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] <= x) i++;
if(i < j) a[j--] = a[i];
}
a[i] = x;
Sort(a, l, i - 1);
Sort(a, i + 1, r);
}
|
Shell Sort
Shell Sort又叫希尔排序，是一种排序演化而成的排序方式。
算法：开始时：将序列区分为n/2个间隔，将相同间隔的数进行排序，减小间隔数，按照以上操作继续排序，直到间隔为1停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void Shellsort(int a[], int n)
{
int tmp, i, j;
for(int Increment = n / 2; Increment > 0; Increment /= 2)
{
for(i = Increment; i < n; i++)
{
tmp = a[i];
for(j = i; j >= Increment; j -= Increment)
{
if(tmp < a[j - Increment]) a[j] = a[j - Increment];
else break;
}
a[j] = tmp;
}
}
}
|
