网站设计验收商城推广软文范文
目录
一、快速排序的递归实现
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 < r&&a[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, r+1, 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(l<r)a[l++] = a[r];while (l < r && tmp >= a[l]){l++;}if(l<r)a[r--] = a[l];
}a[l] = tmp;Qs2(a, left, l-1 );Qs2(a, l+1 , right);
}3.快速排序（前后指针法）
思想：选择一个数作为参考值（用key表示这个数的下标），一般选择最左边的数为参考值，然后让一个指针pre（下标）等于key，让另一个指针cur（下标）等于key+1，然后让cur指针往后走，如果遇到小于key指向的值的数，那么就和pre+1对应的数交换，依次迭代，直到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 = key+1, pre = key ;while (cur <= right){ //pre+1等于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, key+1, 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 = left+1, pre = left ;int key = left;while (cur <= right){ //pre+1等于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 mid=Quicksort(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.快速排序整体的综合性能和应用场景都比较好，所以才敢叫快速排序