洛阳哪有做公司网站的,家装网站建设公司,天元建设集团有限公司财务部电话,邯郸网站设计怎么注册1、快速排序的思想
快速排序就是给基准数据找在数组中正确位置的过程#xff0c;一旦基准位置的正确位置找到#xff0c;那基准位置左右两边经过同样的步骤递归也可以有序#xff0c;最终整体数组有序。 整体可以理解为三个步骤#xff1a; 1、先从队尾开始向前扫描且当l …1、快速排序的思想
快速排序就是给基准数据找在数组中正确位置的过程一旦基准位置的正确位置找到那基准位置左右两边经过同样的步骤递归也可以有序最终整体数组有序。 整体可以理解为三个步骤 1、先从队尾开始向前扫描且当l r时如果a[r] temp ,则r – ,如果a[r] temp ,则将r的值赋给l, 即a[l] a[r] ,赋值后必转换扫描方向即从队首向队尾扫描 2、从队首向队尾扫描时且当l r, 如果a[l] temp , 则l , 如果a[l] temp ,则将l的值赋给r, 即a[r] a[l] ,赋值后必转换扫描方向即从队尾想队首扫描 3、不断重复步骤1和2 ,直到l r时,l或r的位置就是该基准数据在数组中的正确索引位置。
#includeiostream
using namespace std;
int partition(int *a,int l,int r)
{int i l1; int j r;//将第一个节点作为分开点int temp a[l];while (1){while (a[i] temp i r)//i游标直到a[i]temp停止且小于该段的末尾{i;}while (a[j] temp)//j游标直到a[j]temp停止{j--;}if (i j)break;//跳出循环swap(a[i], a[j]);//不断的进行i位置和j位置较换条件成立}swap(a[l], a[j]);//将中间节点与j节点交换 return j;
}
void quick(int* a,int l,int r)//分治
{if (l r){int q partition(a, l, r);//进行中间节点选取quick(a, l, q-1);//左半部分quick(a, q1 , r);//右半部分}
}
void main()
{int a[10]{ 2,1,5,3,4,9,6,8,7,0 };quick(a,0,9);for (int i 0; i 10; i){cout a[i];}
}下面是第二中方法只不过是j的位置不同而已原理是一致的
#includeiostream
using namespace std;
int q_step2(int* a, int f, int l)
{int value a[l];//记录中间节点int i f;int j i;for (j; j l; j){if (a[j] value){swap(a[i], a[j]);i;}}swap(a[i], a[l]);return i;
}void q_step1(int* a, int f, int l)
{if (f l)return;int q q_step2(a, f, l);q_step1(a, f, q - 1);q_step1(a, q 1, l);}
void main()
{int a[10]{ 2,1,5,3,4,9,6,8,7,0 };q_step1(a,0,9);for (int i 0; i 10; i){cout a[i];}
}