基本排序简单介绍（二）

上一篇：基本排序介绍（一）

快速排序

快速排序是一种改良的冒泡排序，其核心思想是分治。每一次在序列中找出一个标记值（通常这个值选取第一位或者最后一位）然后把序列中所有小于这个标记值的数放到前面， 把所有大于这个标记值的数放到后面。
这样经过 一趟 比较后，这个标记数的下标一定是 就位 的（指在有序序列中，该数应该在的下标），并且该下标前面的所有数都 小于 标记数， 后面的所有数都 大于 标记数。
我们实现每一趟比较的方法是：

• 建立两个下标，一个指向线性表尾部(right)， 一个指向线性表头部(left)
• 选取下标为0 所存储的数作为标记数(mark)
• 从后往前遍历，直到发现一个比mark值小的数，此时将它放置到left的位置
• 此时从前往后遍历， 直到发现一个比mark大的数，此时将它放置到right的位置
• 不断重复这个过程，直到左右下标相遇(left == right), 最后将mark放置到他们相遇的位置

完成每一趟遍历的算法后，我们将会得到两段序列:

• mark所在下标之前的数构成的序列
• mark所在下标之后的数构成的序列

此时只需要拿着这两段序列做递归调用即可。（注意递归的结束条件：划分区段长度小于等于1时不需要进行排序）

/**
* @brief 快速排序
* @param array 待排序数组
* @param low 数组位序低位
* @param high 数组位序高位
*/
void quickSort(int array[], int low, int high) {
    if (low >= high) {
        return;
    }

    int right = high;
    int left = low;
    int mark = array[left];

    while (left < right) {
        while (left < right && array[right] >= mark) {
            right--;
        }
        array[left] = array[right];

        while (left < right && array[left] <= mark) {
            left++;
        }
        array[right] = array[left];
    }

    array[left] = mark;
    quickSort(array, low, left - 1);
    quickSort(array, left + 1, high);
}

快速排序是不稳定的排序， 其平均时间复杂度为O(nlogn)，而最坏时间复杂度为O(n²)。

归并排序

归并排序和快速排序一样，基于分治的思想，归并排序也是一种时间效率很优的排序。并且是一种稳定的排序。但相比较快速排序O(1)的空间复杂度，归并排序的空间复杂度为O(n)。
归并排序的思路也是每一次将序列划分为两半。但是和快速排序基于交换不同的是，归并划分完序列后进行的是有序插入或者叫有序合并, 将两段有序的序列合并为新的有序序列， 新的有序序列的长度将是两段序列各自长度之和。
因此我们有了以下代码：

• 用下标模拟序列
• 不断把序列划分为两部分。
• 直到划分序列长度为2时停止，此时再将序列看做两个长度为1的有序序列。
• 对两个长度为1的序列进行有序合并操作，将会得到一个长度为2的有序序列。
• 递归返回上层，再对长度为2的有序序列进行有序合并。
• 重复此过程。

/**
* @brief 归并排序
* @param arr 待排序数组
* @param low 低位下标
* @param high 高位下标
*/
void mergeSort(int arr[], int low, int high) {
    if (low == high) {
        return;
    }

    int mid = ((high - low) / 2) + low;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    orderInsert(arr, low, mid, mid + 1, high);
}

接着进行有序合并的实现：

• 动态创建两个数组，分别将下标虚拟的两个数组拷贝到创建的两个数组中。
• 分别为两个新构建的数组创建遍历用的下标 i，j 将其都指向各自的0号下标
• 遍历，从0号位置开始，比较两个数组元素谁更小。
• 将更小的元素放入待排序序列中，同时更小元素所对应的数组下标后移。
• 后移之后继续重复比较。直到数组尾部。
• 如果i, j任意一个下标到达各自数组尾部，因为两个数组都是有序的序列。所以直接依次放入待排序序列即可。

/**
* @brief 有序插入
* @param arr 待排序数组
* @param left1 有序段1 左下标
* @param right1 有序段1 右下标
* @param left2 有序段2 左下标
* @param right2 有序段2 右下标
*/
void orderInsert(int arr[], int left1, int right1, int left2, int right2) {
    int* lRes = slice(arr, left1, right1 + 1);
    int* rRes = slice(arr, left2, right2 + 1);
    int i = 0, j = 0;
    int length1 = right1 - left1 + 1;
    int length2 = right2 - left2 + 1;

    if (lRes == NULL || rRes == NULL) {
        return;
    }

    while (!(i == length1 && j == length2)) {
        if (i == length1) {
            arr[left1++] = rRes[j++];
        }
        else if (j == length2) {
            arr[left1++] = lRes[i++];
        }
        else {
            arr[left1++] = lRes[i] < rRes[j] ? lRes[i++] : rRes[j++];
        }
    }

    free(lRes);
    free(rRes);
    lRes = NULL;
    rRes = NULL;
}

我在C++中实现slice所犯的低级错误:

for (int i = start; i < endAfter; i++) {
    resArr[i] = arr[i];
}

开始实现的时候，将i赋值为了start，因为要拷贝给一个新的数组，所以应当从0号下标开始，而判断循环的结束条件应该是endAfter - start， 每一次的赋值语句也就应该是resArr[i] = arr[start + i]。

/**
* @brief 截断数组
* @param arr 待排序数组
* @param start 截断的开始位置
* @param endAfter 截断的末尾位置后一位
*/
int* slice(int arr[], int start, int endAfter) {
    int* resArr = (int *)malloc((endAfter - start) * sizeof(int));
    if (resArr == NULL) {
        return NULL;
    }

    try {
        for (int i = 0; i < endAfter - start; i++) {
            resArr[i] = arr[start + i];
        }
    }
    catch (out_of_range error) {
        cout << error.what() << endl;
    }

    return resArr;
}

完整代码：

/**
* @brief 截断数组
* @param arr 待排序数组
* @param start 截断的开始位置
* @param endAfter 截断的末尾位置后一位
*/
int* slice(int arr[], int start, int endAfter) {
    int* resArr = (int *)malloc((endAfter - start) * sizeof(int));
    if (resArr == NULL) {
        return NULL;
    }

    try {
        for (int i = 0; i < endAfter - start; i++) {
            resArr[i] = arr[start + i];
        }
    }
    catch (out_of_range error) {
        cout << error.what() << endl;
    }

    return resArr;
}

/**
* @brief 有序插入
* @param arr 待排序数组
* @param left1 有序段1 左下标
* @param right1 有序段1 右下标
* @param left2 有序段2 左下标
* @param right2 有序段2 右下标
*/
void orderInsert(int arr[], int left1, int right1, int left2, int right2) {
    int* lRes = slice(arr, left1, right1 + 1);
    int* rRes = slice(arr, left2, right2 + 1);
    int i = 0, j = 0;
    int length1 = right1 - left1 + 1;
    int length2 = right2 - left2 + 1;

    if (lRes == NULL || rRes == NULL) {
        return;
    }

    while (!(i == length1 && j == length2)) {
        if (i == length1) {
            arr[left1++] = rRes[j++];
        }
        else if (j == length2) {
            arr[left1++] = lRes[i++];
        }
        else {
            arr[left1++] = lRes[i] < rRes[j] ? lRes[i++] : rRes[j++];
        }
    }

    free(lRes);
    free(rRes);
    lRes = NULL;
    rRes = NULL;
}

/**
* @brief 归并排序
* @param arr 待排序数组
* @param low 低位下标
* @param high 高位下标
*/
void mergeSort(int arr[], int low, int high) {
    if (low == high) {
        return;
    }

    int mid = ((high - low) / 2) + low;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    orderInsert(arr, low, mid, mid + 1, high);
}

上一篇：基本排序介绍（一）