软考数据库知识点小分队2

今天想讲一讲排序算法。

常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

一、冒泡排序

冒泡排序的算法步骤是：从左到右，相邻元素进行比较。

每次比较一轮，就会找到序列中最大的一个或最小的一个。

这个数就会从序列的最右边冒出来。

举一个例子，例如左边这幅图用冒泡排序从小到大排列。

    第一轮，先将3和5进行比较，3<5不换位置，接着5和4比较，5>4两者换位置，以此类推，第一轮结束后得到的排序为：34526；   第二轮，先将3和4比较，3<4不换位置，4和5比较，4<5不换位置，5和2比较，5>2换位置，5和6比较，5<6不换位置，第二轮结束后得到的排序为：34256；由此下去，第三轮结束后得到的排序为：32456；   第四轮结束后得到的排序为：23456。

下面是C 的冒泡排序代码：

#include 
void bubble_sort(int arr[], int len) {
        int i, j, temp;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
}
int main() {
        int arr[] = { 18, 32, 13, 36, 75, 55, 37, 50, 83, 25, 64, 5, 19, 7 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        int i;
        for (i = 0; i < len; i++)
                printf("%d ", arr[i]);
        return 0;
}

 

二、选择排序

选择排序的算法步骤是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

再看刚才的例子还是从小到大排序，第一轮，在这些未排序的元素里面找到最小的数2，将它和最前面的3互换位置，现在序列为25463；第二轮，在还未排序的元素里面(5463)找最小的数3，放在2的后面，此时的序列为23546；第三轮得到的序列为23456，第四轮还是23456。

下面是C的选择排序代码：

void swap(int *a,int *b) //交换两个数
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i,j;

        for (i = 0 ; i < len - 1 ; i++)
    {
                int min = i;
                for (j = i + 1; j < len; j++)     //遍历未排序的元素
                        if (arr[j] < arr[min])    //找到目前最小值
                                min = j;    //记录最小值
                swap(&arr[min], &arr[i]);    //将两者进行交换
        }
}

三、插入排序

插入排序的算法步骤为：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

）

同样是刚才的例子，第一轮开始，将3看作有序序列，将5插入有序序列的适当位置(我感觉像把5和有序序列里面的元素一个一个进行比较)，现在序列为35462；    第二轮开始，将35看作有序序列，将4插入有序序列适当位置(4和35比较)，得到序列34562；    第三轮开始，将345看作有序序列，将6插入有序序列的适当位置(6和345比较)，得到序列34562；     第四轮开始，将3456看作有序序列，将2插入有序序列的适当位置(2和3456比较)，得到序列23456；

下面是C的插入排序代码：

void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i=0) && (arr[j]>key)) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
        }
}

 

四、希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

(2021考过！！)

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

希尔排序的算法步骤为：将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

还是这个例子，一般取这个序列的长度的一半作为增量分组(这个例子我选择3)，第一轮，3和6比较，5和2比较，结束后得到的序列为32465；第二轮，增量分组继续缩小，此时我设定增量为2(因为这个例子里面，上一个增量为3，3的一半1.5，用2就好)，3和4比较，2和6比较，4和5比较，结束后得到的序列为32465；第三轮，增量为1，3和2比较，3和4比较，4和6比较，6和5比较，最后得到的序列为23456。

(这个例子元素比较少，可以多举几个例子自己推一下加深理解)

 下面是C的希尔排序代码：

void shell_sort(int arr[], int len) {
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
                for (i = gap; i < len; i++) {
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                arr[j + gap] = arr[j];
                        arr[j + gap] = temp;
                }
}

 

五、归并排序

归并排序：自上而下的递归；自下而上的迭代；

归并排序的算法步骤为：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤 3 直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。
   

   
   

来看这个例子依旧是从小到大排序，将3和6拿出来比较，5和7拿出来比较，比较结束后为3657 2184，将3657拿出来比较放入合并空间(此时合并空间顺序为3567)，再比较2和1，8和4并排序，比较结束后为3567 1248，再将1248拿出来比较放入合并空间(此时合并空间顺序为1248)，最后将两个合并空间合并进行比较，得出序列为12345678。

下面是C的归并排序代码：

//迭代
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

//递归
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

今天先熟悉这5个算法，下次说剩下的算法。

参考：1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)