做牛仔裤的视频网站,旅游网站建设怎么做,影视公司需要的许可证,和君设计专业网站建设公司快速排序的原理是交换排序#xff0c;其中qsort函数用的排序原理就是快速排序#xff0c;它是一种效率较高的不稳定函数#xff0c;时间复杂度为O(N*longN)#xff0c;接下来就来学习一下快速排序。
一、快速排序思路
1.整体思路
以升序排序为例#xff1a; (1)、首先随… 快速排序的原理是交换排序其中qsort函数用的排序原理就是快速排序它是一种效率较高的不稳定函数时间复杂度为O(N*longN)接下来就来学习一下快速排序。
一、快速排序思路
1.整体思路
以升序排序为例 (1)、首先随便找一个数(一般取首元素)作为排序对象(记为key)先将这个数排到准确的位置即把小于等于key的全部放在key左边大于key的全部放在key右边。这是排一趟需要做的事。 (2)、排完一趟后被排的那个数key此时它在的位置是准确的接下来只需要用同样的方法分别对它的左数组和右数组排序这就有点类似于二叉树的前序遍历。
如下
void QuickSort(int* arr, int left, int right)
{if (left right)//如果左区间右区间就不用再排直接返回。return;int key_Sort3(arr, left, right);//该函数用来排单趟QuickSort(arr, left, key - 1);QuickSort(arr, key 1, right);
} 至于排单趟的算法一般有三种分别是霍尔法挖坑法前后指针法。在下面会细讲。
2.单趟排序
2.1.霍尔法 把第一个元素当排序对象key(首元素的下标)用L储存左下标R储存右下标。先让R从右往左走找到比key小的元素时停下然后让L从左往右走找到比key大的元素停下。然后把位于L位置和位于R位置的的值进行交换最后重复上面的操作直到LR为止。再把key的位置与L位置的值交换。至此一趟排序就结束了。
代码示例
int _Sort1(int* arr, int begin, int end)//霍尔法
{int key begin;while (begin end){while (begin end arr[end] arr[key])end--;while (begin end arr[begin] arr[key])begin;Swap(arr[begin], arr[end]);}Swap(arr[key], arr[begin]);key begin;return key;
}
2.1.挖坑法 把首元素当做排序对象赋值给key然后把第一个下标L当做坑位让R从右边出发找到比key小的数放在坑位然后R的位置变成坑位让L从左往右找到比key大的数放在坑位L位置变成坑位再次让R走循环往复直到L与R相遇。最后把key放在坑位至此一趟排序结束。 代码示例
int _Sort2(int* arr, int begin, int end)
{int key arr[begin];int kw begin;//坑位下标while (begin end){while (begin end arr[begin] key)begin;arr[kw] arr[begin];kw begin;while (begin end arr[end] key)end--;arr[kw] arr[end];kw end;}arr[kw] key;return kw;
}
2.3.前后指针法 把第一个元素当排序对象key(首元素的下标)prev指向首元素下标cur指向首元素下一个元素下标。 如果cur指向的元素小于key的话prev向右走并且如果prev不等于cur那么把prev与cur互换。最后cur都需要无条件向右走一步。
代码示例
int _Sort3(int* arr, int begin, int end)//前后指针法
{int perv begin, cur begin 1;while (cur end){if (arr[cur] arr[begin] perv ! cur)Swap(arr[perv], arr[cur]);cur;}Swap(arr[perv], arr[begin]);return perv;
}
二、提供效率的方法
1.三数取中(key值的选取) 快速排序的三数取中Median of Three是一种优化技术它相当于选排序对象key。其具体做法如下 (1).选择三个元素从待排序数组中选择三个关键元素通常是第一个元素、中间元素和最后一个元素。 (2).比较并选择中位数将这三个元素进行比较选择值不是最大也不是最小的数。比如如果三个元素分别是arr[left]、arr[mid]、arr[right]则中位数是介于这三个值之间的那个数。 (3).交换为第一个元素将选定的中位数元素与数组的第一个元素交换位置以便在后续的快速排序中使用。 通过使用三数取中的方法可以有效地减少快速排序中最坏情况的发生概率因为选取的主元更有可能接近数组的中值而不是极端值。这样可以更均匀地划分数组减少排序的平均时间复杂度提高算法的整体性能。
2.小区间优化 小区间优化指的是在快速排序算法中针对较小规模的子数组或子问题采用其他排序方法而不是继续使用快速排序本身。这种优化技术的目的是避免在小规模问题上快速排序的递归调用带来的额外开销提高算法的整体效率。 具体来说当快速排序的递归过程划分的子数组规模减小到一定程度时可以选择使用插入排序或其他适合小规模数组的排序方法来处理。这样可以避免递归深度过深减少递归调用和分区操作的开销从而提高整体排序算法的性能。 具体的优化策略包括 (1).设定阈值在实现快速排序时设定一个阈值当子数组的大小小于这个阈值时转而使用插入排序或者直接选择排序等方法进行排序。常见的阈值一般设定在5到10之间具体取决于具体实现和排序数据的特性。 (2).切换到其他排序算法在快速排序的递归过程中当子数组大小小于设定的阈值时停止快速排序的递归转而使用其他排序算法完成剩余的排序工作。 小区间优化技术能有效降低快速排序在小规模数据上的不必要开销提高整体排序算法的效率和性能。
三、非递归实现 把递归该为非递归毋庸置疑首先考虑使用栈结构这里我们需要抓住重点考虑需要用栈结构储存什么数据先从函数参数上看左右区间的参数是一直在变化的那么只需要把区间储存到栈中每次从栈中就可以取到需要排序的区间对这个区间进行一趟排序后再分为两个小区间存入栈中重复以上操作直到栈为空。
四、源码
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includetime.h
#includeStack.h
#define size 100
void Swap(int* a, int* b)
{int c *a;*a *b;*b c;
}
void InsertSort(int* arr, int sz)//插入排序(小区间优化)
{for (int i 0; i sz - 1; i){int j i;int tmp arr[j 1];while (j 0 tmp arr[j]){arr[j 1] arr[j--];}arr[j 1] tmp;}
}
int Sk(int* arr, int left, int right)//三数取中
{int v (left right) / 2;if (arr[left] arr[right]){if (arr[right] arr[v])return right;else{if (arr[left] arr[v])return left;elsereturn v;}}else{if (arr[left] arr[v])return left;else{if (arr[right] arr[v])return right;elsereturn v;}}
}
int _Sort1(int* arr, int begin, int end)//霍尔法
{int key begin;while (begin end){while (begin end arr[end] arr[key])end--;while (begin end arr[begin] arr[key])begin;Swap(arr[begin], arr[end]);}Swap(arr[key], arr[begin]);key begin;return key;
}
int _Sort2(int* arr, int begin, int end)//挖坑法
{int val arr[begin];int kw begin;//坑位while (begin end){while (begin end arr[begin] val)begin;arr[kw] arr[begin];kw begin;while (begin end arr[end] val)end--;arr[kw] arr[end];kw end;}arr[kw] val;return kw;
}
int _Sort3(int* arr, int begin, int end)//前后指针法
{int perv begin, cur begin 1;while (cur end){if (arr[cur] arr[begin] perv ! cur)Swap(arr[perv], arr[cur]);cur;}Swap(arr[perv], arr[begin]);return perv;
}
void QuickSort(int* arr, int left, int right)//快速排序(递归实现)
{if (left right)return;if (right - left 10){InsertSort(arr left, right - left 1);return;}int key_Sort1(arr, left, right);QuickSort(arr, left, key - 1);QuickSort(arr, key 1, right);
}
void QuickSortNoR(int* arr, int left, int right)//快速排序(非递归)
{Stack st;StackInit(st);//关于栈结构的函数实现在这里并未展示已在Stack.h中声明StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){int begin StackTop(st);StackPop(st);int perv begin, cur begin 1;int end StackTop(st);StackPop(st);if (begin end)continue;while (cur end){if (arr[cur] arr[begin] perv ! cur)Swap(arr[cur], arr[perv]);cur;}Swap(arr[begin], arr[perv]);StackPush(st, end), StackPush(st, perv 1);StackPush(st, perv - 1), StackPush(st, begin);}StackDestroy(st);
}
int main()
{int arr[size] { 0 };srand((unsigned int)time(NULL));//随机数种子for (int i 0; i size; i){arr[i] rand() % 1000 1;//生成随机数赋值给arr[i]}QuickSort(arr, 0, size - 1);for (int i 0; i size; i){printf(%-3d , arr[i]);if ((i 1) % 20 0)printf(\n);}return 0;
}
