尧图网站建设 )
目录1.快速排序的思想2.基准值的选取2.1三数取中2.2随机选数2.3基准值选取代码3.单趟排序的三种方法3.1hoare法3.1.1hoare法单趟图解3.1.2hoare法单趟代码3.2挖坑法3.2.1挖坑法单趟图解3.2.2挖坑法单趟代码3.3前后指针法3.3.1前后指针法单趟图解3.3.2前后指针法单趟代码4.快速排序排序图解及完整代码5.快速排序的时间复杂度与空间复杂度以升序为例1.快速排序的思想以升序为例单趟排序时选取一个基准值并将其放在数组中的正确位置即让左边的数小于等于基准值右边的数大于等于基准值然后以该基准值所在位置为界将数组分割为左右两个部分(均不包含基准值位置)并分别对这两个部分重复进行选取基准值并放到正确位置的操作直到区间不存在时停止此时数组有序2.基准值的选取固定选取当前数组的首元素或尾元素作为基准值可能会因递归层次太深(后续讲解)导致效率低下(O(N^2))甚至栈溢出一般使用三数取中或随机选数来确定基准值然后将其与首或尾位置元素进行交换2.1三数取中int GetMidi(int* a, int left, int right){ int midi left (right - left) / 2; if (a[left] a[midi]){ if (a[midi] a[right]) return midi; else if (a[left] a[right]) return right; else return left; } else//a[left] a[midi]{ if (a[left] a[right]) return left; else if (a[midi] a[right]) return right; else return midi; } }三数取中就是说在数组的首元素、中间位置元素和最后一个元素当中选择中位数这里我们返回该元素的下标便于后续交换int midi (left right) / 2可能会导致溢出int midi left (right - left) / 2;中间偏左int midi left (right - left 1) / 2;中间偏右中间偏左与标准库一致减少维护成本。除非有明确证据表明中间偏右在特定场景下性能显著更优否则应默认使用中间偏左的计算方式2.2随机选数srand((unsigned int)time(NULL)); int midi left rand() % (right - left 1);left 是 当前区间的首元素的下标通过rand函数产生随机值以随机选择基准值随机选数的方法可能会因分区不平衡导致效率降低三数取中能够保持平均性能降低极端分区不平衡的风险所以我们一般使用三数取中来选取基准值2.3基准值选取代码int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]);3.单趟排序的三种方法我们选好了基准值就需要将其放置在正确的位置上此时有hoare法、挖坑法、前后指针法实现该操作3.1hoare法3.1.1hoare法单趟图解未作三数取中处理以升序为例hoare版本的思想就是(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)(1)选定的基准值Key是首元素就让right先向左移动找到比Key小的元素再让left向右移动找到比Key大的元素找到之后交换两元素的位置再继续让right先走找小left后走找大直到left\right相遇为止此时交换Ke和相遇位置的元素的位置(1)选定的基准值Key是尾元素就让left先向右走找大right后走找小......首元素是基准值时必须让right先走才能使相遇位置的元素小于等于基准值(1)right找到小left找不到大left碰right直接相遇交换位置可满足正确位置的定义(2)right找不到小直接与left位置即基准值相遇自己与自己交换不影响(3)right找到小left找到大交换之后再发生上面两种情况而已如果left先走1个位置就可能发生right找不到小而直接与left相遇的情况此时基准值本应自己与自己交换变为了与下一个位置交换不符合正确位置的定义如果让left先走找大也可能出现找不到大而直接与right相遇的情况交换后不符合正确位置的定义3.1.2hoare法单趟代码int PartSort1(int* a, int left, int right) { //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int keyi left; //将基准值放置到正确位置 while (left right) { //基准值在左边右边先走找小 //相遇就停下相等继续走 while (left right a[right] a[keyi]) --right; //左边找大 //相遇就停下相等继续走 while (left right a[left] a[keyi]) left; //交换大、小元素的位置 Swap(a[left], a[right]); } //基准值与相遇位置的元素发生交换 Swap(a[keyi], a[right]); //返回相遇位置的下标便于后续分区间递归 keyi right; return keyi; }(1)在找大、小的过程中要时刻注意left、right不要越界(2)等于Key的数组元素既可以在正确位置的左边也可以在右边所以while (left right a[right] a[keyi])这里面需要用、如果不加等于当数组中间有与Key相等的两个值时就会出现死循环的现象3.2挖坑法3.2.1挖坑法单趟图解基准值未作三数取中处理以升序为例挖坑法的思想就是(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)(1)创建变量Key存储基准值(1)选定的基准值Key是首元素就让right先向左移动找到比Key小的元素找到就填充坑位坑位转移到右边再让left向右移动找到比Key大的元素找到就填充坑位坑位转移到左边再继续让right先走找小填充坑位并转移坑位left后走找大填充坑位并转移坑位.....直到left\right相遇为止此时用Key填充坑位(1)选定的基准值Key是尾元素就让left先向右走找大right后走找小......首元素是基准值时必须让right先走才能使相遇位置成为正确的坑位(1)right找到小填充坑位并正确转移之后left找不到大left碰right相遇位置满足正确位置的定义(2)right找不到小直接与left位置即基准值相遇原位置填充不影响(3)right找到小left找到大交换之后再发生上面两种情况而已如果left先走1个位置就可能发生right找不到小而直接与left相遇的情况此时基准值本应填充原位置变为了填充下一个位置不符合正确位置的定义如果让left先走找大也可能出现找不到大而直接与right相遇的情况填充坑位并正确转移之后最终坑位不符合正确位置的定义3.2.2挖坑法单趟代码int PartSort2(int* a, int left, int right){ //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int key a[left]; //初始坑位在首元素位置 int hole left; //将基准值放置到正确位置 while (left right){ //基准值在左边右边先走找小 //相遇就停下相等继续走 while (left right a[right] key) --right; //找到就填充就算找不到也是在相遇位置 a[hole] a[right]; //转移坑位 hole right; //左边找大 //找到就填充相遇就停下相等继续走 while (left right a[left] key) left; a[hole] a[left]; hole left; } a[hole] key; return hole; }3.3前后指针法3.3.1前后指针法单趟图解基准值未作三数取中处理以升序为例选定的基准值Key是首元素时前后指针的思想就是prev 是小于Key的最后一个元素的位置后续用于与首元素进行交换(1)prev、cur初始值分别是当前区间首元素的下标、第二个元素的下标(也可以是指针)如果cur位置的值小于Keyprev然后交换cur位置与prev位置的值再cur如果cur位置的值大于等于Keycur这样之后prev要么紧邻cur要么与cur之间间隔着比Key大的值反复进行上面操作之后比Key大的值就会向后移动比Key小的值就会向前移动prev所在位置的元素小于等于Keyprev最终所在位置就是正确位置3.3.2前后指针法单趟代码int PartSort3(int* a, int left, int right) { //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int keyi left; int prev left; int cur left 1; //cur位置的值小于基准值就与prev位置的值进行交换cur // 大于 cur while (cur right) { if (a[cur] a[left] prev ! cur) Swap(a[cur], a[prev]); cur; } //基准值与prev位置的值交换 //prev位置的值始终是小于等于基准值的 Swap(a[keyi], a[prev]); keyi prev; return keyi; }if (a[cur] a[left] prev ! cur) Swap(a[cur], a[prev]);这段代码巧妙地运用了运算符短路求值及前置先再返回的特点来减少自己与自己交换的冗余操作4.快速排序排序图解及完整代码单趟排序将选取的基准值放置到正确位置之后数组被分割为左右两部分左右两部分再重复进行选值放值分割的操作直到区间只有一个元素或不存在为止例如当数组只有 0、1两个元素时hoare法返回的keyi是0区间就会被分割为[0, -1](不存在)、[1, 1](只有一个元素)整个排序类似于二叉树的前序遍历void QuickSort(int* a, int left, int right) { if (left right) return; int keyi PartSort1(a, left, right); //[left, keyi - 1] keyi [keyi 1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }小规模(小于16)数组使用递归会冗余这点数量的数组选择直接插入的方法进行优化更好void QuickSort(int* a, int left, int right) { if (left right) return; if (right - left 1 10){ InsertSort(a left, right - left 1); } else{ int keyi PartSort1(a, left, right); //[left, keyi - 1] keyi [keyi 1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } }5.快速排序的时间复杂度与空间复杂度递归实现快速排序时(1)固定选取当前数组的首元素或尾元素作为基准值而不采用三数取中、随机选数调参时当数组有序会导致每次划分只能减少一个元素即每次递归调用处理的子数组长度仅减少 1导致递归层次太深遍历次数变为(N 1) * N) / 2时间复杂度退化为O(N^2)(1)调参之后前面说了递归调用相当于时二叉树的前序遍历此时就约有logN层而每一层的个数还是在N这个量级(尽管有减少)记住结论就行所以时间复杂度可被优化为O(N*logN)(1)快速排序的空间复杂度主要由递归调用栈的深度决定此外还包括划分过程中的临时变量开销可忽略所以时间复杂度最好为O(logN)最差为O(N) 数据结构 之 【排序】(递归实现快速排序)
目录1.快速排序的思想2.基准值的选取2.1三数取中2.2随机选数2.3基准值选取代码3.单趟排序的三种方法3.1hoare法3.1.1hoare法单趟图解3.1.2hoare法单趟代码3.2挖坑法3.2.1挖坑法单趟图解3.2.2挖坑法单趟代码3.3前后指针法3.3.1前后指针法单趟图解3.3.2前后指针法单趟代码4.快速排序排序图解及完整代码5.快速排序的时间复杂度与空间复杂度以升序为例1.快速排序的思想以升序为例单趟排序时选取一个基准值并将其放在数组中的正确位置即让左边的数小于等于基准值右边的数大于等于基准值然后以该基准值所在位置为界将数组分割为左右两个部分(均不包含基准值位置)并分别对这两个部分重复进行选取基准值并放到正确位置的操作直到区间不存在时停止此时数组有序2.基准值的选取固定选取当前数组的首元素或尾元素作为基准值可能会因递归层次太深(后续讲解)导致效率低下(O(N^2))甚至栈溢出一般使用三数取中或随机选数来确定基准值然后将其与首或尾位置元素进行交换2.1三数取中int GetMidi(int* a, int left, int right){ int midi left (right - left) / 2; if (a[left] a[midi]){ if (a[midi] a[right]) return midi; else if (a[left] a[right]) return right; else return left; } else//a[left] a[midi]{ if (a[left] a[right]) return left; else if (a[midi] a[right]) return right; else return midi; } }三数取中就是说在数组的首元素、中间位置元素和最后一个元素当中选择中位数这里我们返回该元素的下标便于后续交换int midi (left right) / 2可能会导致溢出int midi left (right - left) / 2;中间偏左int midi left (right - left 1) / 2;中间偏右中间偏左与标准库一致减少维护成本。除非有明确证据表明中间偏右在特定场景下性能显著更优否则应默认使用中间偏左的计算方式2.2随机选数srand((unsigned int)time(NULL)); int midi left rand() % (right - left 1);left 是 当前区间的首元素的下标通过rand函数产生随机值以随机选择基准值随机选数的方法可能会因分区不平衡导致效率降低三数取中能够保持平均性能降低极端分区不平衡的风险所以我们一般使用三数取中来选取基准值2.3基准值选取代码int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]);3.单趟排序的三种方法我们选好了基准值就需要将其放置在正确的位置上此时有hoare法、挖坑法、前后指针法实现该操作3.1hoare法3.1.1hoare法单趟图解未作三数取中处理以升序为例hoare版本的思想就是(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)(1)选定的基准值Key是首元素就让right先向左移动找到比Key小的元素再让left向右移动找到比Key大的元素找到之后交换两元素的位置再继续让right先走找小left后走找大直到left\right相遇为止此时交换Ke和相遇位置的元素的位置(1)选定的基准值Key是尾元素就让left先向右走找大right后走找小......首元素是基准值时必须让right先走才能使相遇位置的元素小于等于基准值(1)right找到小left找不到大left碰right直接相遇交换位置可满足正确位置的定义(2)right找不到小直接与left位置即基准值相遇自己与自己交换不影响(3)right找到小left找到大交换之后再发生上面两种情况而已如果left先走1个位置就可能发生right找不到小而直接与left相遇的情况此时基准值本应自己与自己交换变为了与下一个位置交换不符合正确位置的定义如果让left先走找大也可能出现找不到大而直接与right相遇的情况交换后不符合正确位置的定义3.1.2hoare法单趟代码int PartSort1(int* a, int left, int right) { //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int keyi left; //将基准值放置到正确位置 while (left right) { //基准值在左边右边先走找小 //相遇就停下相等继续走 while (left right a[right] a[keyi]) --right; //左边找大 //相遇就停下相等继续走 while (left right a[left] a[keyi]) left; //交换大、小元素的位置 Swap(a[left], a[right]); } //基准值与相遇位置的元素发生交换 Swap(a[keyi], a[right]); //返回相遇位置的下标便于后续分区间递归 keyi right; return keyi; }(1)在找大、小的过程中要时刻注意left、right不要越界(2)等于Key的数组元素既可以在正确位置的左边也可以在右边所以while (left right a[right] a[keyi])这里面需要用、如果不加等于当数组中间有与Key相等的两个值时就会出现死循环的现象3.2挖坑法3.2.1挖坑法单趟图解基准值未作三数取中处理以升序为例挖坑法的思想就是(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)(1)创建变量Key存储基准值(1)选定的基准值Key是首元素就让right先向左移动找到比Key小的元素找到就填充坑位坑位转移到右边再让left向右移动找到比Key大的元素找到就填充坑位坑位转移到左边再继续让right先走找小填充坑位并转移坑位left后走找大填充坑位并转移坑位.....直到left\right相遇为止此时用Key填充坑位(1)选定的基准值Key是尾元素就让left先向右走找大right后走找小......首元素是基准值时必须让right先走才能使相遇位置成为正确的坑位(1)right找到小填充坑位并正确转移之后left找不到大left碰right相遇位置满足正确位置的定义(2)right找不到小直接与left位置即基准值相遇原位置填充不影响(3)right找到小left找到大交换之后再发生上面两种情况而已如果left先走1个位置就可能发生right找不到小而直接与left相遇的情况此时基准值本应填充原位置变为了填充下一个位置不符合正确位置的定义如果让left先走找大也可能出现找不到大而直接与right相遇的情况填充坑位并正确转移之后最终坑位不符合正确位置的定义3.2.2挖坑法单趟代码int PartSort2(int* a, int left, int right){ //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int key a[left]; //初始坑位在首元素位置 int hole left; //将基准值放置到正确位置 while (left right){ //基准值在左边右边先走找小 //相遇就停下相等继续走 while (left right a[right] key) --right; //找到就填充就算找不到也是在相遇位置 a[hole] a[right]; //转移坑位 hole right; //左边找大 //找到就填充相遇就停下相等继续走 while (left right a[left] key) left; a[hole] a[left]; hole left; } a[hole] key; return hole; }3.3前后指针法3.3.1前后指针法单趟图解基准值未作三数取中处理以升序为例选定的基准值Key是首元素时前后指针的思想就是prev 是小于Key的最后一个元素的位置后续用于与首元素进行交换(1)prev、cur初始值分别是当前区间首元素的下标、第二个元素的下标(也可以是指针)如果cur位置的值小于Keyprev然后交换cur位置与prev位置的值再cur如果cur位置的值大于等于Keycur这样之后prev要么紧邻cur要么与cur之间间隔着比Key大的值反复进行上面操作之后比Key大的值就会向后移动比Key小的值就会向前移动prev所在位置的元素小于等于Keyprev最终所在位置就是正确位置3.3.2前后指针法单趟代码int PartSort3(int* a, int left, int right) { //三数取中获取基准值 int midi GetMidi(a, left, right); if (midi ! left) Swap(a[left], a[midi]); int keyi left; int prev left; int cur left 1; //cur位置的值小于基准值就与prev位置的值进行交换cur // 大于 cur while (cur right) { if (a[cur] a[left] prev ! cur) Swap(a[cur], a[prev]); cur; } //基准值与prev位置的值交换 //prev位置的值始终是小于等于基准值的 Swap(a[keyi], a[prev]); keyi prev; return keyi; }if (a[cur] a[left] prev ! cur) Swap(a[cur], a[prev]);这段代码巧妙地运用了运算符短路求值及前置先再返回的特点来减少自己与自己交换的冗余操作4.快速排序排序图解及完整代码单趟排序将选取的基准值放置到正确位置之后数组被分割为左右两部分左右两部分再重复进行选值放值分割的操作直到区间只有一个元素或不存在为止例如当数组只有 0、1两个元素时hoare法返回的keyi是0区间就会被分割为[0, -1](不存在)、[1, 1](只有一个元素)整个排序类似于二叉树的前序遍历void QuickSort(int* a, int left, int right) { if (left right) return; int keyi PartSort1(a, left, right); //[left, keyi - 1] keyi [keyi 1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }小规模(小于16)数组使用递归会冗余这点数量的数组选择直接插入的方法进行优化更好void QuickSort(int* a, int left, int right) { if (left right) return; if (right - left 1 10){ InsertSort(a left, right - left 1); } else{ int keyi PartSort1(a, left, right); //[left, keyi - 1] keyi [keyi 1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } }5.快速排序的时间复杂度与空间复杂度递归实现快速排序时(1)固定选取当前数组的首元素或尾元素作为基准值而不采用三数取中、随机选数调参时当数组有序会导致每次划分只能减少一个元素即每次递归调用处理的子数组长度仅减少 1导致递归层次太深遍历次数变为(N 1) * N) / 2时间复杂度退化为O(N^2)(1)调参之后前面说了递归调用相当于时二叉树的前序遍历此时就约有logN层而每一层的个数还是在N这个量级(尽管有减少)记住结论就行所以时间复杂度可被优化为O(N*logN)(1)快速排序的空间复杂度主要由递归调用栈的深度决定此外还包括划分过程中的临时变量开销可忽略所以时间复杂度最好为O(logN)最差为O(N)