数据结构从入门到精通

2024-07-10 16:45| 来源: 网络整理| 查看: 265

快速排序前言

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

一、快速排序的基本思想

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

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

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

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

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

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

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

常见方式

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

hoare版本

挖坑法

前后指针版本

通用模块代码语言：javascript复制/ 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - 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] = right) return;：如果区间内只有一个元素或者没有元素（即left大于或等于right），那么就没有排序的必要，函数直接返回。 int begin = left, end = right;：定义了两个变量begin和end，分别初始化为区间的左右端点。这两个变量将用于后续的递归调用。 int keyi = left;：定义了一个变量keyi，并初始化为区间的左端点。keyi将作为基准（pivot）值，用于划分数组。 while (left < right)：主循环，当left小于right时继续执行循环体。接下来的两个while循环用于调整数组元素的位置，使得比a[keyi]小的元素都在它的左边，比它大的元素都在它的右边。第一个while循环：从右向左遍历数组，找到第一个小于a[keyi]的元素，right的数值就是此时的下标。第二个while循环：从左向右遍历数组，找到第一个大于a[keyi]的元素，left的数值就是此时的下标。 Swap(&a[left], &a[right]);：交换a[left]和a[right]两个元素的位置。 Swap(&a[left], &a[keyi]);：将基准值a[keyi]放到正确的位置上，即它左边的所有元素都小于它，右边的所有元素都大于它。此时，left所指向的位置就是keyi的正确位置。 QuickSort(a, begin, keyi - 1);：对基准值左边的子区间进行递归排序。 QuickSort(a, keyi + 1, end);：对基准值右边的子区间进行递归排序。

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

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

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

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

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

选取合适的枢轴元素：枢轴元素的选择对快速排序的性能影响很大。选择一个合适的枢轴元素可以减少比较和交换的次数。常用的选择方法有随机选择、中位数选择和三数取中等。使用插入排序：对于小规模的子数组，使用插入排序可能比快速排序更高效。当子数组的规模小于某个阈值时，可以切换到插入排序来提高性能。优化递归调用：快速排序是一个递归算法，递归调用会带来一定的性能开销。可以考虑使用尾递归或迭代来替代递归调用，以减少函数调用的开销。避免重复比较：在递归过程中，可能会重复比较相同的元素，这是不必要的。可以通过增加判断条件来避免重复比较，以提高性能。

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

三数取中法

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

代码语言：javascript复制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)，因为只是进行有限次的比较和赋值操作，不涉及循环。

优化代码代码语言：javascript复制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] = 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] = right)return; int prev = left; int cur = left + 1; int key = left; while (cur = right) return; 如果左边界大于等于右边界，说明已经排好序或只有一个元素，无需再排序，直接返回。初始化变量： int prev = left;：prev表示小于基准元素的最后一个元素的位置，初始化为左边界；int cur = left + 1;：cur表示当前遍历的元素的位置，初始化为左边界加1；int key = left;：key表示基准元素的位置，初始化为左边界。遍历数组： while (cur 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; }非递归实现快速排序代码语言：javascript复制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 = 0) { if (tmp < a[end]) { a[end + 1] = a[end]; end--; } else break; } 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] = 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] = right)return; int prev = left; int cur = left + 1; int key = left; while (cur

【本文地址】

数据结构从入门到精通

数据结构从入门到精通

今日新闻

推荐新闻