旅游网站建设的课题研究的主要内容,wordpress 判断文章,长沙学校网站建设,wordpress转成hexo上期我们实现了快速排序的递归实现#xff0c;但是我们知道如果递归深度太深#xff0c;栈就会溢出#xff0c;所以我们本期将为大家讲述快速排序的非递归实现#xff0c;我们需要用到栈的数据结构#xff0c;我们知道栈中的数据全是在堆区开辟的空间#xff0c;堆的空间… 上期我们实现了快速排序的递归实现但是我们知道如果递归深度太深栈就会溢出所以我们本期将为大家讲述快速排序的非递归实现我们需要用到栈的数据结构我们知道栈中的数据全是在堆区开辟的空间堆的空间大小是比栈的大小要大的这便是我们为什么要采用非递归的方法实现快排的原因。 快速排序非递归实现 在学习非递归之前我们先回顾一下使用递归方法实现排序的方法我们依旧采用第一种单趟排序的方法。这种方法单趟排序的目的就是最终找一个key如果是排升序最终k位置左边的所有元素都比key位置上的元素小右边的所有元素都比key位置上的元素大。也就意味着最终找到了一个key位置这个位置上的元素已经排好了序。 当我们进行完单趟排序之后找到了一个key值因为这个位置的元素已经排好了序所以我们只需要对这个key位置左边和右边的所有元素进行快速排序即可这就是我们实现快速排序的递归方法。单趟排序一次只能排好一个元素。 那么如何进行非递归呢? 非递归的实现其实是在递归的方法上进行改进的就是将递归中的操作改成用循环来实现。因为单趟排序一次可以排好一个元素那么n个元素总共就需要n-1次单趟排序然后我们就可以利用循环来进行所有的单趟排序每一次单趟排序都会返回一个key我们要根据key的位置确定下一次单趟排序的元素的下标范围。假如我们现在已经确定了一个key那么此时我们要么开始对右边进行单趟排序要么对左边的元素进行单趟排序但是一旦我们选择了左边那么就必须将左边的所有元素排好序之后才能去排右边的元素所以我们如果先排了左边那么就需要将右边的元素的下标范围存储起来以便于最后将左边元素排好之后返回来进行右边的排序。怎么样保存这便就用到了栈的数据结构。如果先对左边的所有元素进行单趟排序后对右边的所有元素进行单趟排序根据栈先进后出的性质那么就得先将右边元素的下标入栈再将左边的元素的下标入栈。因为当数组中只有一个元素时是没有必要进行单趟排序的所以要进行单趟排序必须保证数组中至少有两个元素这就是我们是否继续进行单趟排序的条件。 以上便是非递归的思路总的来说有些复杂大家仔细阅读几遍。 图示如下 非递归整体代码如下
void QuickSortNR(int* a, int left, int right)
{ST Stack;StackInit(Stack);StackPush(Stack, right);StackPush(Stack, left);while (!StackEmpty(Stack)){int begin StackTop(Stack);StackPop(Stack);int end StackTop(Stack);StackPop(Stack);int key PartSort1(a, begin, end);if (begin key - 1){StackPush(Stack, key - 1);StackPush(Stack, begin);}if (key 1 end){StackPush(Stack, end);StackPush(Stack, key 1);}}StackDestroy(Stack);
} 注意我们使用非递归实现快速排序时最重要的还是要保证栈中元素的变化只有当栈中存在元素时我们才进行循环栈中存放的就是我们每次进行单趟排序的区间。 到此快速排序的所有知识点我们已经学习完总而言之在我们多次的优化下快速排序已经是一个非常优秀的排序了。
本期内容到此结束^_^
