数据结构从入门到精通——快速排序

快速排序

  • 前言
  • 一、快速排序的基本思想
    • 常见方式
    • 通用模块
  • 二、快速排序的特性总结
  • 三、三种快速排序的动画展示
  • 四、hoare版本快速排序的代码展示
    • 普通版本
    • 优化版本
      • 为什么要优化快速排序代码
      • 三数取中法
      • 优化代码
  • 五、挖坑法快速排序的代码展示
  • 六、前后指针快速排序的代码展示
  • 七、非递归实现快速排序的代码展示
    • Stack.h
    • Stack.c
    • 非递归实现快速排序
  • 八、快速排序的完整代码

前言

快速排序是一种高效的排序算法，通过选取一个“基准”元素，将数组分为两部分：比基准小的元素和比基准大的元素，然后递归地对这两部分进行排序，从而实现对整个数组的排序。该算法平均时间复杂度为O(nlogn)，最坏情况下为O(n²)，但由于实际应用中很少出现最坏情况，因此快速排序仍然是一种广泛使用的排序算法。

一、快速排序的基本思想

在这里插入图片描述

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序的基本思想是采用分治策略，通过选取一个“基准”元素，将待排序的数组分为两个子数组，一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后对这两个子数组递归地进行快速排序，从而达到对整个数组排序的目的。

在快速排序的具体实现中，通常选择数组中的一个元素作为基准元素，然后将数组中的其他元素与基准元素进行比较，根据比较结果将元素放到两个子数组中。这个过程可以通过使用双指针技术来实现，一个指针从数组的开头开始向右移动，另一个指针从数组的末尾开始向左移动，当左指针指向的元素小于等于基准元素，且右指针指向的元素大于等于基准元素时，交换这两个元素的位置。当左指针移动到右指针的位置时，整个数组就被划分为了两个子数组。

接下来，对这两个子数组分别进行快速排序。递归地调用快速排序函数，传入子数组的首尾指针作为参数，直到整个数组都被排序完毕。

快速排序的时间复杂度在最坏情况下为O(n²)，即当每次选取的基准元素都是当前数组中的最小或最大元素时，会导致每次划分得到的子数组大小相差很大，从而使得递归树的深度很大，排序效率降低。然而，在实际应用中，由于快速排序的随机性，其平均时间复杂度为O(nlogn)，因此在实际应用中具有很高的效率。

此外，快速排序是一种原地排序算法，只需要常数级别的额外空间，因此在处理大规模数据时具有很大的优势。同时，快速排序也是一种不稳定的排序算法，即相等的元素在排序后可能会改变它们的相对位置。

综上所述，快速排序是一种基于分治策略的排序算法，通过递归地将数组划分为子数组并对其进行排序，实现了对整个数组的排序。虽然在最坏情况下其时间复杂度可能达到O(n²)，但在实际应用中其平均时间复杂度为O(nlogn)，具有很高的效率。同时，快速排序也是一种原地、不稳定的排序算法，适用于处理大规模数据。

常见方式

将区间按照基准值划分为左右两半部分的常见方式有

  1. hoare版本
    在这里插入图片描述

  2. 挖坑法
    在这里插入图片描述

  3. 前后指针版本
    在这里插入图片描述

通用模块

/ 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);
}

二、快速排序的特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
    在这里插入图片描述
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

快速排序是一种高效的排序算法，其最显著的特点是其“分而治之”的策略。它的基本思想是通过一个分割操作，将待排序的序列划分为两个子序列，其中一个子序列的所有元素都比另一个子序列的所有元素要小，然后再对这两个子序列分别进行快速排序，从而达到整个序列有序的目的。

快速排序的高效性主要得益于其内部循环可以在大部分的实际情况下将元素放到最终的位置上，这被称为“原地排序”，因为它只需要常量级的额外空间来存放辅助信息。然而，这也带来了一个潜在的问题，即在最坏情况下，当输入序列已经有序或者逆序时，快速排序的时间复杂度会退化到O(n^2)，这是因为分割操作会导致不平衡的子序列划分。

为了解决这个问题，通常会采用随机化或者“三数取中”等策略来选择分割点，以减少最坏情况发生的概率。此外，还可以采用“堆排序”或者“归并排序”等其他排序算法作为备选方案，在检测到快速排序性能下降时自动切换。

快速排序的另一个重要特性是其不稳定性。这意味着在排序过程中，相等的元素可能会改变它们的相对顺序。这通常不会影响到排序结果的正确性，但在某些特定的应用场景下，如需要保持元素原始顺序的排序，就需要选择其他稳定的排序算法。

综上所述，快速排序是一种强大而灵活的排序工具，其“分而治之”的策略和原地排序的特性使其在许多情况下都成为首选的排序算法。然而，为了充分发挥其性能优势，也需要对其潜在的缺点有所了解，并采取相应的策略进行规避。

三、三种快速排序的动画展示

  1. hoare版本快速排序的动画展示
    Hoare版本快速排序的动画展示揭示了该排序算法的工作原理。在动画中，初始未排序的数组被选取一个基准值（pivot），然后将数组分为两部分：小于基准值的元素和大于基准值的元素。这个过程通过不断调整基准值的位置，使得数组逐渐变得有序。动画清晰展示了分区过程以及递归地对子数组进行相同操作的步骤，直到整个数组完全排序。整个过程直观展示了快速排序算法的高效性和稳定性。

    hoare——快速排序

  2. 挖坑法快速排序的动画展示
    挖坑法快速排序是一种排序算法的可视化展现。它展示了如何通过不断挖坑、填坑的过程，将数组分为两部分，使得左边的元素都比右边的元素小，从而实现快速排序。动画中，可以看到随着排序的进行，数组被逐渐整理成有序状态。

挖坑法——快速排序

  1. 前后指针快速排序的动画展示
    该段话介绍了前后指针快速排序的动画展示。其核心在于，通过动画形式直观地展示了前后指针快速排序的过程。该算法利用两个指针，以找到需要交换的元素对，并进行交换。通过重复此过程，最终实现数组的排序。动画演示使得这一过程更加直观易懂。

前后指针——快速排序

四、hoare版本快速排序的代码展示

普通版本

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left >= right)return;int begin = left, end = right;int keyi = left;while (left < right){// right先走，找小while (left < right && a[right] >= a[keyi]){--right;}// left再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]keyi[keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

这段代码是实现了经典的快速排序（QuickSort）算法，使用了Hoare版本的分区（partitioning）策略。快速排序是一种非常高效的排序算法，平均时间复杂度为O(nlogn)。下面我将对代码进行逐行分析：

  1. void QuickSort(int* a, int left, int right)：定义了一个名为QuickSort的函数，它接受三个参数：一个整数数组的指针a，以及要排序的区间的左右端点left和right。

  2. if (left >= right) return;：如果区间内只有一个元素或者没有元素（即left大于或等于right），那么就没有排序的必要，函数直接返回。

  3. int begin = left, end = right;：定义了两个变量begin和end，分别初始化为区间的左右端点。这两个变量将用于后续的递归调用。

  4. int keyi = left;：定义了一个变量keyi，并初始化为区间的左端点。keyi将作为基准（pivot）值，用于划分数组。

  5. while (left < right)：主循环，当left小于right时继续执行循环体。

  6. 接下来的两个while循环用于调整数组元素的位置，使得比a[keyi]小的元素都在它的左边，比它大的元素都在它的右边。

    • 第一个while循环：从右向左遍历数组，找到第一个小于a[keyi]的元素，right的数值就是此时的下标。
    • 第二个while循环：从左向右遍历数组，找到第一个大于a[keyi]的元素，left的数值就是此时的下标。

  7. Swap(&a[left], &a[right]);：交换a[left]和a[right]两个元素的位置。

  8. Swap(&a[left], &a[keyi]);：将基准值a[keyi]放到正确的位置上，即它左边的所有元素都小于它，右边的所有元素都大于它。此时，left所指向的位置就是keyi的正确位置。

  9. QuickSort(a, begin, keyi - 1);：对基准值左边的子区间进行递归排序。

  10. QuickSort(a, keyi + 1, end);：对基准值右边的子区间进行递归排序。

这段代码实现了快速排序的基本思想：选择一个基准值，通过一趟排序将数组分成两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

优化版本

为什么要优化快速排序代码

优化快速排序代码的目的是提高排序算法的性能，使其更快地完成排序任务。快速排序是一种高效的排序算法，但在某些情况下，原始的快速排序算法可能会比较慢或占用更多的内存。通过对代码进行优化，可以减少不必要的比较和交换操作，以提高算法的效率。

例如，当要排序的数组是有序的时候，你的数组是一个降序数组，但是你要将他变成升序，此时使用快速排序会使代码的时间复杂度变得非常的大，即O(N2)

以下是一些常见的优化快速排序代码的方法：

  1. 选取合适的枢轴元素：枢轴元素的选择对快速排序的性能影响很大。选择一个合适的枢轴元素可以减少比较和交换的次数。常用的选择方法有随机选择、中位数选择和三数取中等。

  2. 使用插入排序：对于小规模的子数组，使用插入排序可能比快速排序更高效。当子数组的规模小于某个阈值时，可以切换到插入排序来提高性能。

  3. 优化递归调用：快速排序是一个递归算法，递归调用会带来一定的性能开销。可以考虑使用尾递归或迭代来替代递归调用，以减少函数调用的开销。

  4. 避免重复比较：在递归过程中，可能会重复比较相同的元素，这是不必要的。可以通过增加判断条件来避免重复比较，以提高性能。

总之，通过优化快速排序代码，可以加快排序算法的执行速度，减少不必要的开销，提高算法的效率。

三数取中法

三数取中法是一种排序算法中的选择方法，用于快速排序等算法中选取基准元素。它选取待排序数组中第一个、中间和最后一个元素中的中值作为基准，以保证基准元素的选择相对均匀，从而提高排序效率。这种方法在处理大量数据时表现优秀，能有效减少比较和交换次数，提高排序速度。

int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else return right;}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}

这段代码是一个函数，函数名为GetMidi，接受一个int类型的数组a和两个整型参数left和right。

函数的作用是找到数组a中的一个索引值，使得该索引值对应的元素值是数组中的"中间值"。"中间值"的定义是当数组a按照升序排列时，它的前半部分元素值都小于它，后半部分元素值都大于它。

函数首先计算mid值，即left和right的中间值。然后通过对比a[left]、a[mid]和a[right]的值，来确定mid值是否满足"中间值"的条件。

具体判断逻辑如下：

  • 首先判断a[left]和a[mid]的大小关系。
    • 若a[left] < a[mid]，则继续判断a[mid]和a[right]的大小关系。
      • 若a[mid] < a[right]，则返回mid。
      • 若a[left] > a[right]，则返回left。
      • 若以上条件均不满足，则返回right。
    • 若a[left] ≥ a[mid]，则继续判断a[mid]和a[right]的大小关系。
      • 若a[mid] > a[right]，则返回mid。
      • 若a[left] < a[right]，则返回left。
      • 若以上条件均不满足，则返回right。

这段代码的时间复杂度是O(1)，因为只是进行有限次的比较和赋值操作，不涉及循环。

优化代码

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left >= right)return;//优化,也可以不加if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);//直接插入排序，也可以换成其他排序return;}else{int begin = left, end = right;//优化，三数取中法int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){// right先走，找小while (left < right && a[right] >= a[keyi]){--right;}// left再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]keyi[keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}}

该代码实现了快速排序算法。

函数Swap用于交换两个指针所指向的值。

函数QuickSort是快速排序的主函数，它接受一个整型数组a、左右边界left和right作为参数。在函数中，首先判断区间的大小，如果区间只有一个值或者不存在，则直接返回。如果区间大小小于10，则使用插入排序进行排序，否则进行快速排序。

在快速排序的过程中，选择一个基准值（这里使用三数取中法选择基准值的索引），并将该基准值与左边界的值进行交换。然后，使用左右两个指针分别从左右两边开始向中间遍历，找到左边大于基准值的元素和右边小于基准值的元素，然后交换这两个元素的位置。最后将基准值与左指针的值进行交换，完成一次划分。

然后，将左边和右边的子数组进行递归调用快速排序，直到区间大小为1或不存在，完成整个排序过程。

总结起来，这段代码实现了一个使用了优化的快速排序算法，其中使用了三数取中法选择基准值和插入排序来优化小区间的排序。

五、挖坑法快速排序的代码展示

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void Quick1Sort(int* a, int left, int right)
{// 区间只有一个值或者不存在就是最小子问题if (left >= right)return;//优化,也可以不加if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);return;}int keyi = left, begin = left, end = right;int tmp = a[keyi];while (left < right){// right先走，找小while (left < right && a[right] >= a[keyi]){--right;}Swap(&a[keyi], &a[right]);keyi = right;// left再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[keyi], &a[left]);keyi = left;}Swap(&a[keyi], &tmp);// [begin, keyi-1]keyi[keyi+1, end]Quick1Sort(a, begin, keyi - 1);Quick1Sort(a, keyi + 1, end);
}

这段代码实现了快速排序的挖坑算法。函数Quick1Sort接收一个整型数组a，以及数组的左右边界left和right。函数的作用是对数组a的[left, right]区间进行快速排序。

快速排序的基本思想是选取一个基准元素，将数组分为两个部分，一部分是小于等于基准元素的元素，另一部分是大于基准元素的元素。然后分别对这两部分递归进行快速排序，直到区间只有一个元素或者为空。

代码的具体实现如下：

  1. 如果left大于等于right，则不需要进行排序，直接返回。
  2. 如果区间的长度小于10，使用插入排序进行排序。这是一个优化，当区间长度较小时，插入排序的效率可能更高。
  3. 初始化两个指针keyi、begin和end。keyi指向基准元素，begin和end分别指向区间的左右边界。
  4. 使用tmp保存基准元素的值。
  5. 通过双指针的方式，找到比基准元素小的元素并交换到右侧，再找到比基准元素大的元素并交换到左侧。直到左指针和右指针相遇。此时左指针的位置就是基准元素的最终位置，将基准元素与tmp交换。
  6. 接下来，递归调用Quick1Sort函数对左右两个区间进行排序，左区间是[begin, keyi-1]，右区间是[keyi+1, end]。

六、前后指针快速排序的代码展示

void Quick2Sort(int* a, int left, int right)
{if (left >= right)return;int prev = left;int cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[key], &a[prev]);key = prev;Quick2Sort(a, left, key - 1);Quick2Sort(a, key + 1, right);
}

这是快速排序的一种常见的排序算法，其基本思想是通过选择一个基准元素，将序列分为两个子序列，其中一个子序列中的元素都小于基准元素，另一个子序列中的元素都大于基准元素，然后对两个子序列递归地进行快速排序。

具体分析代码如下：

  1. 函数定义：void Quick2Sort(int* a, int left, int right)

    • 参数a表示待排序的数组，left和right表示数组的左右边界；
    • 返回类型为void，表示不需要返回排序后的数组。

  2. 判断递归结束条件：if (left >= right) return;

    • 如果左边界大于等于右边界，说明已经排好序或只有一个元素，无需再排序，直接返回。

  3. 初始化变量：

    • int prev = left;：prev表示小于基准元素的最后一个元素的位置，初始化为左边界；
    • int cur = left + 1;：cur表示当前遍历的元素的位置，初始化为左边界加1；
    • int key = left;：key表示基准元素的位置，初始化为左边界。

  4. 遍历数组：

    • while (cur <= right)：循环遍历数组，直到当前元素的位置大于右边界。
    • if (a[cur] < a[key] && ++prev != cur) Swap(&a[cur], &a[prev])：如果当前元素小于基准元素，且prev不等于cur（即有大于基准元素的元素存在），则将当前元素与prev位置上的元素进行交换，并且prev向后移动一位。
    • cur++：将当前元素的位置向后移动一位，继续遍历数组。

  5. 将基准元素放置到正确的位置：

    • Swap(&a[key], &a[prev])：将基准元素与prev位置上的元素进行交换，使得基准元素放置到正确的位置。

  6. 递归调用快速排序：

    • Quick2Sort(a, left, key - 1)：对左边子数组进行快速排序，左边界为left，右边界为key-1；
    • Quick2Sort(a, key + 1, right)：对右边子数组进行快速排序，左边界为key+1，右边界为right。

  7. 整个函数结束。

七、非递归实现快速排序的代码展示

实现栈的非递归需要使用到栈的知识——栈

对栈不理解的可以看我之前写的文章

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空

Stack.c

#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
void STPush(ST* ps,STDatatype x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);if (p == NULL){perror("p malloc : ");return ;}ps->a = p;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
STDatatype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{assert(ps);return ps->top;
}

非递归实现快速排序

void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);// 单趟int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

这段代码实现的是非递归版本的快速排序算法。

首先，这段代码使用了一个栈结构ST来保存待排序子数组的起始和结束索引。

在主循环中，每次从栈中弹出两个索引，分别表示待排序子数组的起始和结束位置。接下来执行单趟排序，即将子数组中的元素按照基准元素的大小进行分区，使得基准元素左边的元素都小于或等于它，右边的元素都大于它。具体的分区过程使用了prev和cur两个指针，prev指向当前已处理的小于基准元素的最右边的位置，cur从prev+1开始遍历。如果a[cur]小于基准元素，则将它与prev+1位置的元素进行交换，并将prev向右移动一位。最后将基准元素放到prev位置，并用keyi保存基准元素的索引。

接下来，根据keyi的位置，将子数组分成左右两个部分。如果keyi+1小于end，说明右边的子数组还有未排序的元素，将右子数组范围的起始和结束索引入栈。如果begin小于keyi-1，说明左边的子数组还有未排序的元素，将左子数组范围的起始和结束索引入栈。

最后，在主循环结束后，销毁栈结构。

总的来说，这段代码通过栈结构实现了快速排序的非递归版本，避免了递归调用带来的额外开销。

八、快速排序的完整代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "Stack.h"
void PrintArray(int* a, int n);
void QuickSort(int* a, int left, int right);//hoare
void Quick1Sort(int* a, int left, int right);//挖坑法
void Quick2Sort(int* a, int left, int right);//前后指针法
void QuickSortNonR(int* a, int left, int right);// 非递归实现
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void TestQuickSort()
{//int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };int a[] = { 6,1,2,7,9,3,4,5,10,8 };//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick1Sort()
{int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] = { 6,1,2,7,9,3,4,5,10,8 };//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));Quick1Sort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick2Sort()
{int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] = { 6,1,2,7,9,3,4,5,10,8 };//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));Quick2Sort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick3Sort()
{int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };//int a[] = { 6,1,2,7,9,3,4,5,10,8 };//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};PrintArray(a, sizeof(a) / sizeof(int));QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else return right;}else{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
void QuickSort(int* a, int left, int right)//hoare
{// 区间只有一个值或者不存在就是最小子问题if (left >= right)return;//优化,也可以不加if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);return;}else{int begin = left, end = right;//优化，三数取中法int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){// right先走，找小while (left < right && a[right] >= a[keyi]){--right;}// left再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]keyi[keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}}
void Quick1Sort(int* a, int left, int right)
{// 区间只有一个值或者不存在就是最小子问题if (left >= right)return;//优化,也可以不加if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);return;}int keyi = left, begin = left, end = right;int tmp = a[keyi];while (left < right){// right先走，找小while (left < right && a[right] >= a[keyi]){--right;}Swap(&a[keyi], &a[right]);keyi = right;// left再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[keyi], &a[left]);keyi = left;}Swap(&a[keyi], &tmp);// [begin, keyi-1]keyi[keyi+1, end]Quick1Sort(a, begin, keyi - 1);Quick1Sort(a, keyi + 1, end);
}
void Quick2Sort(int* a, int left, int right)
{if (left >= right)return;int prev = left;int cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[key], &a[prev]);key = prev;Quick2Sort(a, left, key - 1);Quick2Sort(a, key + 1, right);
}
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);// 单趟int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}
void TestOP()
{srand(time(0));const int N = 1000000;int* a1 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();}int begin1 = clock();QuickSort(a1,0,N- 1);int end1 = clock();printf("QuickSort:%d\n", end1 - begin1);free(a1);
}
void Test1OP()
{srand(time(0));const int N = 1000000;int* a1 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();}int begin1 = clock();Quick1Sort(a1, 0, N - 1);int end1 = clock();printf("Quick1Sort:%d\n", end1 - begin1);free(a1);
}
void Test3OP()
{srand(time(0));const int N = 1000000;int* a1 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();}int begin1 = clock();Quick2Sort(a1, 0, N - 1);int end1 = clock();printf("Quick2Sort:%d\n", end1 - begin1);free(a1);
}
void Test4OP()
{srand(time(0));const int N = 1000000;int* a1 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();}int begin1 = clock();QuickSortNonR(a1, 0, N - 1);int end1 = clock();printf("QuickSortNonR:%d\n", end1 - begin1);free(a1);
}
int main()
{TestQuickSort();TestQuick1Sort();TestQuick2Sort();TestQuick3Sort();TestOP();Test1OP();Test3OP();Test4OP();return 0;
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/283635.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

英特尔生态的深度学习科研环境配置-A770为例

英特尔生态的深度学习科研环境配置-A770为例

之前发过在Intel A770 GPU安装oneAPI的教程&#xff0c;但那个方法是用于WSL上。总所周知&#xff0c;在WSL使用显卡会有性能损失的。而当初买这台机器的时候我不在场&#xff0c;所以我这几天刚好有空把机器给重装成Ubuntu了。本篇不限于安装oneAPI&#xff0c;因为在英特尔的…
阅读更多...
什么是PLC物联网关？PLC物联网关有哪些功能？

什么是PLC物联网关？PLC物联网关有哪些功能？

在数字化浪潮的推动下&#xff0c;工业物联网&#xff08;IIoT&#xff09;正逐步成为推动制造业智能化转型的关键力量。而在这一变革中&#xff0c;PLC物联网关扮演着至关重要的角色。今天&#xff0c;就让我们一起走进PLC物联网关的世界&#xff0c;了解它的定义、功能&#…
阅读更多...
41-Vue-webpack基础

41-Vue-webpack基础

webpack基础 前言什么是webpackwebpack的基本使用指定webpack的entry和output 前言 本篇开始来学习下webpack的使用 什么是webpack webpack: 是前端项目工程化的具体解决方案。 主要功能&#xff1a;它提供了友好的前端模块化开发支持&#xff0c;以及代码压缩混淆、处理浏览…
阅读更多...
机器学习 - 准备数据

机器学习 - 准备数据

“Data” in machine learning can be almost anything you can imagine. A table of big Excel spreadsheet, images, videos, audio files, text and more. 机器学习其实可以分为两部分 将不管是什么data&#xff0c;都转成numbers.挑选或者建立一个模型来学习这些numbers …
阅读更多...
js模版字符串-标签模版

js模版字符串-标签模版

模版字符串 js模版字符串使用来创建模版字符串字面量&#xff0c;例如 const name "yu" console.log(hello ${name})很多人都知道。但是其实我们可以定义标签函数来自定义返回结果。 标签函数 带标签的模板是模板字面量的一种更高级的形式&#xff0c;它允许你使…
阅读更多...
阿里云ecs服务器配置反向代理上传图片

阿里云ecs服务器配置反向代理上传图片

本文所有软件地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/12OSFilS-HNsHeXTOM47iaA 提取码&#xff1a;dqph 为什么要使用阿里云服务器&#xff1f; 项目想让别人通过外网进行访问就需要部署到我们的服务器当中 1.国内知名的服务器介绍 国内比较知名的一些…
阅读更多...
什么是行业垂直类媒体？有哪些？怎么邀约

什么是行业垂直类媒体？有哪些？怎么邀约

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体胡老师。 行业垂直类媒体是聚焦于特定行业或领域的媒体平台。 行业垂直类媒体不同于主流媒体&#xff0c;它们专注于提供与某个特定领域相关的深入内容和服务&#xff0c;例如商业新闻、旅游、数字…
阅读更多...
seleniumUI自动化实例（登录CSDN页面）

seleniumUI自动化实例（登录CSDN页面）

今天分享一个CSDN登录模块的登录场景 1.配置文件 CSDNconf.py&#xff1a; from selenium import webdriver options webdriver.ChromeOptions() options.binary_location r"D:\Program Files\360\360se6\Application\360se.exe" # 360浏览器安装地址 driver w…
阅读更多...
C++ Qt开发：QUdpSocket实现组播通信

C++ Qt开发：QUdpSocket实现组播通信

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QUdpSocket组件实现基于UDP的组播通信…
阅读更多...
MyBatis3源码深度解析(十七)MyBatis缓存(一)一级缓存和二级缓存的实现原理

MyBatis3源码深度解析(十七)MyBatis缓存(一)一级缓存和二级缓存的实现原理

文章目录 前言第六章 MyBatis缓存6.1 MyBatis缓存实现类6.2 MyBatis一级缓存实现原理6.2.1 一级缓存在查询时的使用6.2.2 一级缓存在更新时的清空 6.3 MyBatis二级缓存的实现原理6.3.1 实现的二级缓存的Executor类型6.3.2 二级缓存在查询时使用6.3.3 二级缓存在更新时清空 前言…
阅读更多...
Nginx 的安装、启动和关闭

Nginx 的安装、启动和关闭

文章目录 一、背景说明二、Nginx 的安装2.1、依赖的安装2.2、Nginx 安装2.3、验证安装 三、启动 Nginx3.1、普通启动3.2、如何判断nginx已启动3.3、通过配置启动3.4、设置开机启动 四、关闭 Nginx4.1、优雅地关闭4.2、快速关闭4.3、只关闭主进程4.4、使用nginx关闭服务 五、重启…
阅读更多...
计算机网络：数据交换方式

计算机网络：数据交换方式

计算机网络&#xff1a;数据交换方式 电路交换分组交换报文交换传输对比 本博客介绍计算机之间数据交换的三种方式&#xff0c;分别是电路交换、分组交换以及报文交换。 电路交换 我们首先来看电路交换&#xff0c;在电话问世后不久&#xff0c;人们就发现要让所有的电话机都…
阅读更多...
Springboot-软件授权License

Springboot-软件授权License

无意中看到了一个简单方便的授权方式&#xff0c;只需几步就可集成到boot项目中。 先上地址&#xff1a;smart-license: 保护个人与企业的软件作品权益&#xff0c;降低盗版造成的损失。PS&#xff1a;因个人精力有限&#xff0c;不再提供该项目的咨询答疑服务。 Smart-licen…
阅读更多...
【小米汽车SU7实测】 小米汽车su7到底行不行？小米新能源轿车体验感怎么样？

【小米汽车SU7实测】 小米汽车su7到底行不行？小米新能源轿车体验感怎么样？

小米汽车SU7是小米汽车的首款车型&#xff0c;定位“C级高性能生态科技轿车”&#xff0c;也是小米迈入新能源赛道的首次成果落地。 首先&#xff0c;让我们来谈谈它的性能。试驾过程中&#xff0c;小米SU7展现出了惊人的加速能力&#xff0c;0-100km/h加速仅需2.78秒&#xf…
阅读更多...
pytest全局配置+前后只固件配置

pytest全局配置+前后只固件配置

pytest全局配置前后只固件配置 通过读取pytest.ini配置文件运行通过读取pytest.ini配置文件运行无条件跳过pytest.initest_mashang.pyrun.py 有条件跳过test_mashang.py pytest框架实现的一些前后置&#xff08;固件、夹具&#xff09;处理方法一&#xff08;封装&#xff09;方…
阅读更多...
Kafka总结问题

Kafka总结问题

Kafka Kafka Kafka Kafka的核心概念/ 结构 topoic Topic 被称为主题&#xff0c;在 kafka 中&#xff0c;使用一个类别属性来划分消息的所属类&#xff0c;划分消息的这个类称为 topic。topic 相当于消息的分配标签&#xff0c;是一个逻辑概念。主题好比是数据库的表&#xff0…
阅读更多...
C++进阶之路---C++11相关特性 | 左值引用 | 右值引用 | 完美转发

C++进阶之路---C++11相关特性 | 左值引用 | 右值引用 | 完美转发

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、C11简介 在2003年C标准委员会曾经提交了一份技术勘误表(简称TC1)&#xff0c;使得C03这个名字已经取代了C98称为C11之…
阅读更多...
全球大型语言模型(LLMS)现状与比较

全球大型语言模型(LLMS)现状与比较

我用上个博文的工具将一篇ppt转换成了图片&#xff0c;现分享给各位看官。 第一部分&#xff1a;国外大语言模型介绍 1&#xff0c;openai的Chatgpt 免费使用方法1&#xff1a;choose-carhttps://share.freegpts.org/list 免费使用方法2&#xff1a;Shared Chathttps://share…
阅读更多...
【Java】Map和Set

【Java】Map和Set

文章目录 一、Map和Set的概念二、模型三、Map的说明3.1 Map.Entry<K, V>的说明3.2 Map 的常用方法 四、Set的说明4.1 Set的常用方法 一、Map和Set的概念 Map和set是一种专门用来进行搜索的容器或者数据结构&#xff0c;其搜索的效率与其具体的实例化子类有关&#xff0c…
阅读更多...
redis和rabbitmq实现延时队列

redis和rabbitmq实现延时队列

redis和rabbitmq实现延时队列 延迟队列使用场景Redis中zset实现延时队列Rabbitmq实现延迟队列 延迟队列使用场景 1. 订单超时处理 延迟队列可以用于处理订单超时问题。当用户下单后&#xff0c;将订单信息放入延迟队列&#xff0c;并设置一定的超时时间。如果在超时时间内用户…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023