连接国外网站的app,公司部门架构,wordpress修改地址后网站打不开,wordpress管理导航栏目快速排序的思想与归并排序思想类似#xff0c;都是采用分治法的思想。将一个数组A[l...r]使用快速排序可以分解为三个主要的步骤#xff1a; 通过随机算法获得数组A中的一个下标k#xff0c;将A[k]与A[r]交换。将数组分解成左右两个数组#xff0c;左边数组的值均小于A[r]都是采用分治法的思想。将一个数组A[l...r]使用快速排序可以分解为三个主要的步骤 通过随机算法获得数组A中的一个下标k将A[k]与A[r]交换。将数组分解成左右两个数组左边数组的值均小于A[r]右边数组的值均不小于A[r]。分别对左右两个数组进行排序这两个数组的大小均比A小。 通过上面的步骤我们就可以得到快速排序的一个框架 1 void QuickSortCore(int data[], int start, int end)
2 {
3 if (start end)
4 {
5 int k Partition(data, start, end); //分解成左右两个数组
6 QuickSortCore(data, start, k - 1); //排序左边的数组
7 QuickSortCore(data, k 1, end); //排序右边的数组
8 }
9 } 从上面的代码中可以看出分解A数组为左右两个数组是快速排序算法的关键这个问题本质上为对数组A中的某个值A[k]k为数组的下标将小于A[k]的数存放在数组A的前面将不小于A[k]的数存放在数组A的后面分界线为x。 解决该问题的一种很直观的方法就是先将A[k]与A[r]交换然后用两个下标i、ji表示A[0~i]中的数都小于A[r]j从0~r-1遍历数组A。如果发现A[j]小于A[r]则将A[i 1]与A[j]交换并同时增加i和j之所以可以这样是因为A[i 1]要么不小于A[r]要么与A[j]相同如果A[j]不小于M则只递增j。最后将A[i 1]与A[r]交换i1为左右数组的分界线x。 1 int Partition(int data[], int start, int end)2 {3 int k, i, j;4 5 k GetRandom(start, end); //通过随机函数获得数组下标6 Swap(data k, data end); //将作为分界线的数放到最后7 i start - 1;8 for (j start; j end; j)9 if (data[j] data[end]) //需要交换
10 {
11 i;
12 Swap(data i, data j);
13 }
14 i;
15 Swap(data i, data end);
16 return i;
17 } 解决问题的另一个方法是先将A[k]与A[l]交换并用一个临时变量p保存A[k]也使用两个下标i和j分别初始化为l和r。开始用j从数组右边遍历知道发现A[j] p为止将A[j]赋值给A[i]并让i加1然后用i从数组的左边遍历知道发现A[i] p为止将A[i]赋值给A[j]并让j减1然后重新开始前面的遍历知道i j为止。最后将p赋值给A[i]此时i为左右数组的分界线x。 1 int Partition(int data[], int start, int end)2 {3 int k, i, j, temp;4 5 k GetRandom(start, end);6 Swap(data k, data start); //将基准数放到最前面7 temp data[start]; //保存基准数副本8 i start;9 j end;
10 while (i j)
11 {
12 //从右边开始遍历知道遇到小于temp的
13 while (i j data[j] temp)
14 j--;
15 if (i j)
16 data[i] data[j];
17 //从左边开始遍历知道遇到大于temp的
18 while (i j data[i] temp)
19 i;
20 if (i j)
21 data[j--] data[i];
22 }
23 data[i] temp;
24 return i;
25 } 前面两个方法中第二个方法比第一个方法要好些第二个方法用赋值替代了第一个方法中的交换。 代码中的GetRandom函数是用来随机获得start到end之间的一个值它可以用rand库函数实现。 转载于:https://www.cnblogs.com/chengxuyuancc/p/3546247.html
