算法 - 内部排序

Algorithm - Sort

ZingLix March 3, 2017

概述

排序分为内部排序和外部排序两种,本文讨论内部排序,即将数据存放于内存中进行排序的算法,分别为冒泡排序、插入排序、归并排序和快速排序。关于外部排序,在这进行了讨论,本文不再赘述。

冒泡排序

冒泡排序应该是所以接触算法的人所第一个了解的排序算法,之所以如此正因为其易懂。

整体思路就是两两比较,将较大的数据往后移动,所以每一次循环,最后一个必定是最大的,即已经完成排序,如下图所示。

bubble_sort.gif

由于冒泡排序效率太低,实际应用不广泛,在此不做太多讨论,代码如下:

1
2
3
4
5
6
7
void bubble_sort(int dat[], int n) {
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (dat[j] > dat[j + 1]) swap(&dat[j], &dat[j + 1]);
        }
    }
}

插入排序

插入排序其思路与打牌时理牌的思路相同,即将每个元素与之前的元素交换,直至小于前一个元素。

insert_sort.gif

由于交换次数过多,而每次调用swap函数会导致额外的时间花销,所以这里采用用tmp先记录要要排序的那个元素,然后每次交换时只将后一个元素赋值前一个元素,直到找到正确的位置,将tmp赋值给它,从而避免使用swap。代码如下:

1
2
3
4
5
6
7
8
9
10
void insert_sort(int dat[], int n) {
    int tmp,j;
    for (int p = 1; p < n; p++) {
        tmp = dat[p];
        for (j = p; j > 0 && dat[j-1] > tmp; j--) {
            dat[j] = dat[j-1];
        }
        dat[j ] = tmp;
    }
}

归并排序

归并排序思路主要为将数组分成数个小数组,然后对其排序,之后再将每两个小数组合并,从而完成对整个数组的排序。该算法是经典的利用分治思想的算法。

merge_sort.gif

所以分为以下三个部分:

1
2
3
4
5
6
//入口函数,负责创建临时数组
void merge_sort(int dat[], int n);
//利用递归对小数组进行排序
void Msort(int dat[],int tmp[], int left, int right);
//将两个小数组合并
void Merge(int dat[],int tmp[], int leftStart, int rightStart, int rightEnd);

其中最为重要的就在于Merge函数,思路主要是先不断比较小数组前面的元素,直到将其中一个小数组全部拷贝至tmp中。

再将另一个数组剩下的元素拷贝至tmp中,最后把tmp复制到原数组中。

具体代码如下:

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
void merge_sort(int dat[], int n) {
    int * tmp = new int[n];
    Msort(dat, tmp, 0, n-1);
    delete  tmp;
}

void Msort(int dat[],int tmp[], int left, int right) {
    int center = (left + right) / 2;
    if (left < right) {
        Msort(dat, tmp, left, center);
        Msort(dat, tmp, center + 1, right);
        Merge(dat, tmp, left, center + 1, right);
    }
}

void Merge(int dat[],int tmp[], int leftStart, int rightStart, int rightEnd) {
    int *Aptr = &dat[leftStart], *Bptr = &dat[rightStart],*ptr=&tmp[leftStart];
    int leftEnd = rightStart - 1;
    //拷贝其中一个数组
    while (Aptr <= &dat[leftEnd] && Bptr <= &dat[rightEnd]) {
        if (*Aptr < *Bptr) {
            *ptr++ = *Aptr++;
        }
        else {
            *ptr++ = *Bptr++;
        }
    }
    //拷贝剩余数组内所有元素
    while (Aptr <= &dat[leftEnd])
        *ptr++ = *Aptr++;
    while (Bptr <= &dat[rightEnd])
        *ptr++ = *Bptr++;
        //拷贝回原数组
    for (int i = leftStart; i <= rightEnd; i++)
        dat[i] = tmp[i];
}

快速排序

快速排序主要思想为先选取枢纽元,然后将比其小的放至其左侧,比其大的放至右侧,然后再分别以递归的方式对左右两侧元素处理。

quick_sort.gif

图中黄色为枢纽元,绿色为比枢纽元小的部分,紫色为比其大的部分。

图中采用第一个元素为枢纽元,下面代码中采用随机元素作为枢纽元,比起前一个方法较为安全,还有一个做法是使用中值进行分割,会在之后进行讨论。具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quick_sort(int dat[], int n) {
    Qsort(dat, 0, n - 1);
}

void Qsort(int dat[], int left,int right) {
    if (right - left < 1) return;
    int pivot = rand() % (right - left) + left;
    swap(&dat[left], &dat[pivot]);
    int j = left + 1;
    for (int i = left + 1; i <= right; i++) {
        if (dat[i] < dat[left]) swap(&dat[i], &dat[j++]);
    }
    swap(&dat[left], &dat[--j]);

    Qsort(dat,left, j-1);
    Qsort(dat, j+1,right);
}

总结

在这里我们所讨论的所有算法均以比较作为基础,所以都被称为比较排序。关于非比较排序在此进行了讨论。在所有内部排序方法中,快速排序可以说是内部排序中最好的方法,当待排数据随机时所需平均时间最短。

图片和gif根据 visualgo.net 制作