网站换空间多少钱,重庆seo推广渠道,wordpress 重定向函数,小说网站建设方案书ppt模板排序算法-快速排序法#xff08;QuickSort#xff09;
1、说明
快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法#xff0c;是目前公认的最佳排序法#xff0c;也是使用分而治之#xff08;Divide and Conquer#xff09;的方式#xff0c;会先在数… 排序算法-快速排序法QuickSort
1、说明
快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法是目前公认的最佳排序法也是使用分而治之Divide and Conquer的方式会先在数据中找到一个虚拟的中间值并按此中间值将所有打算排序的数据分为两部分。其中小于中间值的数据放在左边而大于中间值的数据放在右边再以同样的方式分别处理左右两边的数据直到排序完为止。操作与分割步骤如下
假设有n项记录其键值为。
先假设K的值为第一个键值。从左向右找出键值使得。从左向右找出键值使得。如果那么与互换并回到步骤2。如果那么将与互相并以为基准点分割成左、右两部分然后针对左、右两边执行步骤1~5直到左边键值等于右边键值为止。 2、算法分析
在最好情况和平均情况下时间复杂度为。在最坏情况下就是每次挑中的中间值不是最大就是最小的其时间复杂度为。快速排序法不是稳定排序法。在最坏情况下空间复杂度为而在最好情况下空间复杂度为。快速排序法是平均运行时间最快的排序法。 3、C代码
#includeiostream
using namespace std;void Print(int tempData[], int tempSize) {for (int i 0; i tempSize; i) {cout tempData[i] ;}cout endl;
}void Quick(int tempData[], int tempLeft, int tempRight) {int temp;int leftIndex;int rightIndex;int t;if (tempLeft tempRight) {leftIndex tempLeft 1;rightIndex tempRight;while (true) {for (int i tempLeft 1; i tempRight; i) {if (tempData[i] tempData[tempLeft]) {leftIndex i;break;}leftIndex;}for (int j tempRight; j tempLeft 1; j--) {if (tempData[j] tempData[tempLeft]) {rightIndex j;break;}rightIndex--;}if (leftIndex rightIndex) {temp tempData[leftIndex];tempData[leftIndex] tempData[rightIndex];tempData[rightIndex] temp;}else {break;}}if (leftIndex rightIndex) {temp tempData[tempLeft];tempData[tempLeft] tempData[rightIndex];tempData[rightIndex] temp;Quick(tempData, tempLeft, rightIndex - 1);Quick(tempData, rightIndex 1, tempRight);}}
}int main() {const int size 10;int data[100] { 32,5,24,55,40,81,17,48,25,71 };//32 5 24 55 40 81 17 48 25 71//32 5 24 25 40 81 17 48 55 71//32 5 24 25 17 81 40 48 55 71//17 5 24 25 32 81 40 48 55 71//5 17 24 25 32 81 40 48 55 71//5 17 25 24 32 81 40 48 55 71//5 17 25 24 32 71 40 48 55 81//5 17 25 24 32 55 40 48 71 81//5 17 25 24 32 48 40 55 71 81//5 17 25 24 32 40 48 55 71 81Print(data, size);Quick(data, 0, size - 1);Print(data, size);return 0;
}
输出结果
