编程基础:用LPC语言学排序算法

排序算法

所有排序算法的共同目标都是输出有序列表,但每种算法执行此任务的方式可能有所不同,在使用任何类型的算法时,重要的是知道它运行的速度有多快,以及它运行时需要多大的空间,这些因素被称为算法的时间复杂度和空间复杂度。

高效的排序在优化其它算法(如查找和合并)时非常重要,这些算法需要输入的数据是有序列表(数据结构上就是数组)。

在LPC中有提供排序的外部函数 sort_array() 可以对数组排序,新建一个指令文件 array.c,演示代码如下:

int main(object me, string arg)
{
    int *arr;

    printf("原始数据:%@ d\n", arr = shuffle(allocate(atoi(arg), (: $1 + 1 :))));
    printf("排序数据:%@ d\n", arr = sort_array(arr, 1));

    return 1;
}

因为本文内容是讲解具体算法,我们要做的是不使用系统提供的排序函数,自己了解算法实现相关功能。

排序算法分为比较类排序和非比较类排序,比较类排序是通过比较大小来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。而非比较类排序不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。这里列出10大经典排序算法:

file

如果元素 a 原本在 b 前面,而 a = b 时,排序之后 a 仍然在 b 的前面,这类算法是稳定的,如果排序之后 a 可能会出现在 b 的后面,这类算法是不稳定的。在排序额外内存占用上,分为 in-place 和 out-place,in-place 占用常数内存(通常只需用到O(1)的额外空间),out-place 占用额外内存(和数据规模有关)。下图列出了算法的复杂度和稳定性:

file

在选择排序算法时,你需要考虑要排序的数据量以及实现算法所需的时间。例如,快速排序是一种非常高效的方法,但实现起来相对麻烦,而冒泡排序速度较慢,但实现起来很简单。对于较小的数据集,冒泡排序可能是更好的选择,因为它可以快速实现,而对于较大的数据集,快速排序是更好的选择。

这里只重点讲解常用的比较类排序算法:

  1. 冒泡排序
  2. 快速排序
  3. 插入排序
  4. 选择排序
  5. 归并排序

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。

代码实现

// 交换数组元素
void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 冒泡排序
void bubblesort(int *arr)
{
    int len = sizeof(arr);
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr, j, j + 1);
            }
        }
    }
}

请注意:在LPC中数组传的是地址而不是值,排序后直接改变了原始数组。

快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

int partition(int *arr, int left, int right)
{
    int pivot = left, index = pivot + 1;
    for (int i = index; i <= right; i++)
    {
        if (arr[i] < arr[pivot])
        {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

varargs void quicksort(int *arr, int left, int right)
{
    int len = sizeof(arr), index;

    if (nullp(right))
    {
        right = len - 1;
    }

    if (left < right)
    {
        index = partition(arr, left, right);
        quicksort(arr, left, index - 1);
        quicksort(arr, index + 1, right);
    }
}

插入排序(Insertion Sort)

插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

代码实现

void insertionSort(int *arr)
{
    int len = sizeof(arr), index, current;

    for (int i = 1; i < len; i++)
    {
        index = i - 1;
        current = arr[i];
        while (index >= 0 && arr[index] > current)
        {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = current;
    }
}

选择排序(Selection Sort)

选择排序是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  1. 初始状态:无序区为R[1..n],有序区为空;
  2. 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]R[i..n]。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  3. n-1趟结束,数组有序化了。

代码实现

void selectionSort(int *arr)
{
    int len = sizeof(arr), index;

    for (int i = 0; i < len - 1; i++)
    {
        index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[index])
            {
                index = j;
            }
        }
        swap(arr, i, index);
    }
}

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序;
  3. 将两个排序好的子序列合并成一个最终的排序序列。

代码实现

int *merge(int *left, int *right)
{
    int *result = ({});

    while (sizeof(left) && sizeof(right))
    {
        if (left[0]<=right[0])
        {
            result += ({left[0]});
            left -= ({left[0]});
        }
        else
        {
            result += ({right[0]});
            right -= ({right[0]});
        }
    }
    while (sizeof(left))
    {
        result += ({left[0]});
        left -= ({left[0]});
    }
    while (sizeof(right))
    {
        result += ({right[0]});
        right -= ({right[0]});
    }

    return result;
}

int *mergeSort(int *arr)
{
    int len = sizeof(arr);
    int middle, *left, *right;

    if (len < 2)
    {
        return arr;
    }

    middle = floor(len / 2);
    left = arr[0..middle-1];
    right = arr[middle..];

    return merge(mergeSort(left), mergeSort(right));
}

结束语

排序算法很多,不同算法有不同的时间复杂度和空间复杂度,在编程中选择适合的算法很重要,在教程中已经列出了主流算法的复杂度,我们还可以自己用代码实测直观感受一下,直接写一个测试指令arraysort.c,代码如下:

// 生成乱序数组
int *array(int n)
{
    if (n > 15000)
    {
        n = 15000;
    }

    // return shuffle(allocate(n, (: $1 * secure_random($(n)) :)));
    return shuffle(allocate(n, (: $1 + 1 :)));
}

// 交换数组元素
void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/*
 * 冒泡排序
 */
void bubbleSort(int *arr)
{
    int len = sizeof(arr);
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr, j, j + 1);
            }
        }
    }
}

/*
 * 快速排序
 */
int partition(int *arr, int left, int right)
{
    int pivot = left, index = pivot + 1;
    for (int i = index; i <= right; i++)
    {
        if (arr[i] < arr[pivot])
        {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

varargs void quickSort(int *arr, int left, int right)
{
    int len = sizeof(arr), index;

    if (nullp(right))
    {
        right = len - 1;
    }

    if (left < right)
    {
        index = partition(arr, left, right);
        quickSort(arr, left, index - 1);
        quickSort(arr, index + 1, right);
    }
}

/*
 * 插入排序
 */
void insertionSort(int *arr)
{
    int len = sizeof(arr), index, current;

    for (int i = 1; i < len; i++)
    {
        index = i - 1;
        current = arr[i];
        while (index >= 0 && arr[index] > current)
        {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = current;
    }
}

/*
 * 选择排序
 */
void selectionSort(int *arr)
{
    int len = sizeof(arr), index;

    for (int i = 0; i < len - 1; i++)
    {
        index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[index])
            {
                index = j;
            }
        }
        swap(arr, i, index);
    }
}

/*
 * 归并排序
 */
int *merge(int *left, int *right)
{
    int *result = ({});

    while (sizeof(left) && sizeof(right))
    {
        if (left[0]<=right[0])
        {
            result += ({left[0]});
            left -= ({left[0]});
        }
        else
        {
            result += ({right[0]});
            right -= ({right[0]});
        }
    }
    while (sizeof(left))
    {
        result += ({left[0]});
        left -= ({left[0]});
    }
    while (sizeof(right))
    {
        result += ({right[0]});
        right -= ({right[0]});
    }

    return result;
}

int *mergeSort(int *arr)
{
    int len = sizeof(arr);
    int middle, *left, *right;

    if (len < 2)
    {
        return arr;
    }

    middle = floor(len / 2);
    left = arr[0..middle-1];
    right = arr[middle..];

    return merge(mergeSort(left), mergeSort(right));
}

// 排序测试
int main(object me, string arg)
{
    int n = atoi(arg);
    int *arr = array(n);
    int *arr1 = copy(arr), *arr2 = copy(arr), *arr3 = copy(arr), *arr4 = copy(arr), *arr5 = copy(arr);
    int t, t1, t2, t3, t4, t5;

    if (!n)
    {
        debug("请输入 `arraysort n` 生成数据并测试,n 为待排序数据个数。");
        return 1;
    }
    // 待排序数据
    printf("arr:%@ d\n", arr);
    t = time_expression(arr = sort_array(arr, 1));
    t1 = time_expression(bubbleSort(arr1));
    t2 = time_expression(quickSort(arr2));
    t3 = time_expression(insertionSort(arr3));
    t4 = time_expression(selectionSort(arr4));
    t5 = time_expression(arr5 = mergeSort(arr5));
    // 排序结果
    printf("arr0:%@ d\n", arr);
    printf("arr1:%@ d\n", arr1);
    printf("arr2:%@ d\n", arr2);
    printf("arr3:%@ d\n", arr3);
    printf("arr4:%@ d\n", arr4);
    printf("arr5:%@ d\n", arr5);
    printf("sort_array用时:%d,冒泡排序用时:%d,快速排序用时:%d,插入排序用时:%d,选择排序用时:%d,归并排序用时:%d\n", t, t1, t2, t3, t4, t5);
    return 1;
}

输入指令:arraytest 10|100|1000|10000,测试看看在不同的数据量下不同算法的时间复杂度差距,是不是冒泡排序最慢,快速排序最快?更多排序算法的学习推荐看看这里:https://visualgo.net/zh/sorting

这里补充强调一点:在LPC中数组变量和C语言类似是指针,存的是地址不是值,所以为了测试不同的排序,需要使用copy外部函数把数组复制到其它变量上。

测试可见驱动提供的函数 sort_array 效率最高速度最快的排序,因为驱动提供的外部函数的速度要快于自定义函数,正式的游戏开发中我们也推荐使用sort_array 解决问题,不用自己造轮子。

京ICP备13031296号-4