网站之家,动画制作网页,黄页网络的推广网站有哪些类型,网上营销推广目录
一、快速排序的递归实现
1.快速排序#xff08;Hoare法#xff09;又名左右指针法
2.快速排序#xff08;挖坑法#xff09;
3.快速排序#xff08;前后指针法#xff09;
二、快速排序的非递归实现
三、快速排序的特性总结 一、快速排序的递归实现
1.快速排…目录
一、快速排序的递归实现
1.快速排序Hoare法又名左右指针法
2.快速排序挖坑法
3.快速排序前后指针法
二、快速排序的非递归实现
三、快速排序的特性总结 一、快速排序的递归实现
1.快速排序Hoare法又名左右指针法 其思想 先选出一个数作为key参考对象一般选最左边作为key然后先从最右边开始走如果选最右边作为key则先从左边开始走否则将会交换乱序遇到小于key指向的值的数就停下来再从左边走遇到大于key指向的值的数就停下来最后交换左右指针下标对应的值依次迭代直到左右指针相遇才停下来然后把key指向的值和此时左右指针 指向的值交换就完成了第一次排序此时左边都是小于key指向的值右边都是大于key指向的值。 最后从左右指针相等的位置开始把序列分为左右子序列此时左边都小于key指向的值的数右边都大于key指向的值的数再让左右子序列重复上述过程。 注key表示下标 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void Quicksort(int* a,int left ,int right)//左右指针法
{if (left right)return;int l left, r right;int key left;while (l r){while (l ra[r]a[key])//注意这里需要相等如果不相等{ //左右指针同时遇到等于key的数将会发生死循环r--;}while (l r a[l] a[key])//这里也一样{l;}Swap(a[l], a[r]);}Swap(a[l], a[key]);Quicksort(a, left, l-1);Quicksort( a, r1, right);}
2.快速排序挖坑法 思想顾名思义先选择一个数做为参考值将这个数用一个变量 tmp 保存此时相当于这个数的位置就空下来了坑位一般选择最左边的数作为参考值先从右边开始走如果选择的是最右边的数则先从左边开始走当遇到小于tmp的值就停下来再把该值填到空出来的位置上然后从左边走当遇到大于tmp的值就停下来再把该值填到空出来的位置上依次迭代。 直到它们相遇的时候停下来然后把tmp放到相遇的位置上。 最后从tmp位置开始把整个序列分为左右子序列此时左边都是小于tmp的值右边都是大于tmp的值再让左右子序列重复上述过程。 void Quicksort(int* a, int left, int right)//挖坑法
{if (left right)return;int l left, r right;int tmp a[left];while (l r){while (l r tmp a[r]){r--;}if(lr)a[l] a[r];while (l r tmp a[l]){l;}if(lr)a[r--] a[l];
}a[l] tmp;Qs2(a, left, l-1 );Qs2(a, l1 , right);
}
3.快速排序前后指针法 思想选择一个数作为参考值用key表示这个数的下标一般选择最左边的数为参考值然后让一个指针pre下标等于key让另一个指针cur下标等于key1然后让cur指针往后走如果遇到小于key指向的值的数那么就和pre1对应的数交换依次迭代直到cur指针大于最右边的边界然后退出循环把key指向的值和此时pre指向的值交换再把pre的值赋给key。 最后从key位置开始将整个序列分为左右子序列此时左边都是小于key指向的值右边都是大于key指向的值再让左右子序列重复上述过程。 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void Quicksort(int* a, int left, int right)//前后指针法
{if (left right)return ;int key left;int cur key1, pre key ;while (cur right){ //pre1等于cur时就不交换因为没必要if (a[cur] a[key] pre ! cur){Swap(a[cur], a[pre]);}cur;}Swap(a[key], a[pre]);key pre;Quicksort(a, left, key-1);Quicksort(a, key1, right);
}
二、快速排序的非递归实现 思路快速排序就如同二叉树的前序遍历先将整个序列排序为左边都是小于key指向的数 右边都是大于key指向的数再从key位置开始将整个序列分为左右子序列然后依次对左右子序列进行上述排序。用递归的思想很容就实现了但用非递归那怎么实现呢。 根据递归的思想可以想到先排好了左子序列最后才排右子序列。那么此时就可以借助数据结构中的栈来完成非递归的实现了。 先把最右边的下标入栈然后把左边的下标入栈依次取两个元素对这两个元素对应的区间进行排序排好后把该区间分为左右两个子区间然后先入右区间的两个下标再入左区间的两个下标因为要先排左区间依次迭代直到栈中的元素为空即为排好了。 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}int Quicksort(int* a, int left, int right)//前后指针法
{if (left right)return ;int cur left1, pre left ;int key left;while (cur right){ //pre1等于cur时就不交换因为没必要if (a[cur] a[key] pre ! cur){Swap(a[cur], a[pre]);}cur;}Swap(a[key], a[pre]);key pre;return key;
}void QsortNonR(int* a, int left, int right)
{ST st;StackInit(st);StackPush(st, right);StackPush(st, left);while (!STEmpty(st)){int L StackTOP(st);StackPop(st);int r StackTOP(st);StackPop(st);int midQuicksort(a, L, r);if (mid 1 r){StackPush(st, r);StackPush(st, mid 1);}if (L mid - 1){StackPush(st, mid);StackPush(st, L);}}}
三、快速排序的特性总结 假设序列中有n个数由上图可知每个数大概都需要遍历 logN次所以时间度为 N*logN每次递归都要建立栈帧由上图可见最大递归深度为logN所以空间复杂度为 logN 1.时间复杂度O(N*logN) 2.空间复杂度O(logN) 3.稳定性不稳定 4.快速排序整体的综合性能和应用场景都比较好所以才敢叫快速排序
