快速排序详解（递归实现与非递归实现） |
您所在的位置：网站首页 › 快速排序递归算法与非递归算法优点和缺点分析 › 快速排序详解（递归实现与非递归实现） |
快速排序详解（递归实现与非递归实现）
|
目录 一、快速排序的基本思想 二、将序列划分成左右区间的常见方法 2.1hoare版本（动图+解释+代码实现） 2.2挖坑法 2.3前后指针法 三、快速排序的初步实现 四、快速排序的优化实现 4.1快排的特殊情况 4.2对区间划分代码的优化 4.3小区间优化 五、快速排序的非递归实现 六、总结 一、快速排序的基本思想快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 // 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left = a[keyi]) { right--; } //找大 while (left < right && a[left] = key) { right--; } a[hole] = a[right]; hole = right; //找大 while (left < right && a[left] a[cur]找小，但如果a[keyi] > a[cur]一直成立， //++prev 会一直== cur不会拉开差距。只有a[keyi] = right)//区间只有一个值或区间不存在时就返回 return; int keyi = PartSort1(a, left, right); //这里用PartSort1/PartSort2/PartSort3都可以，时间效率都是一样的 QuickSort(a, left, keyi-1); QuickSort(a, keyi+1, right); //不断递归左区间和右区间 } 四、快速排序的优化实现 4.1快排的特殊情况上面的写法面对绝大多数情况的排序已经可以实现时间复杂度接近
但如果是下面这种情况keyi一直位于最左侧，就会使时间复杂度为 所以为了防止这种特殊情况的出现，可以对划分区间的代码进行一点优化。 4.2对区间划分代码的优化我们还是可以取最左边的数作为key，只是要将最左边的数换成一个在序列中不是那么大也不是那么小的数，在此我们引进了一段三数取中代码。 int getMid(int* a, int left,int right) { int mid = (left + right) / 2; if (a[left] > a[right]) { if (a[mid] > a[left]) { return left; } else if (a[mid] > a[right]) { return mid; } else { return right; } } else { if (a[mid] > a[right]) return right; else if (a[mid] > a[left]) return mid; else return left; } }这段代码负责找到序列中最左边，最右边，中间三个数中第二大的那个数。区间划分代码加入三数取中后，就可以规避掉刚才所说的那种特殊情况了。 int PartSort1(int* a, int left, int right) { int mid = getMid(a, left, right); Swap(&a[left], &a[mid]); int keyi = left;//取最左边的数为基准值 while (left < right) { //找小 while (left < right && a[right] >= a[keyi]) { right--; } //找大 while (left < right && a[left] = right) return; //小区间优化 if ((right - left + 1) > 10)//当区间长度大于10时 { int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi-1); QuickSort(a, keyi+1, right); } else//区间长度小于10时 { InsertSort(a + left, right - left + 1); } } 五、快速排序的非递归实现快排使用到了递归的思想和方法，但是递归如果递归太深的话就会有爆栈的风险，所以在这里也介绍一下快速排序的非递归实现方法。因为快排是先处理左边的序列再处理右边的序列，这里就需要用到数据结构中的栈了，先入右再入左，进行排序。（栈的结构在之前的博客中已经实现过了，在这里同样不赘述） void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); StackPush(&st, right); StackPush(&st, left); while (StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); int keyi = PartSort1(a, begin, end); //不断把大区间化成小区间处理 if (keyi + 1 < end) { StackPush(&st, end); StackPush(&st, keyi+1); } if (begin < keyi - 1) { StackPush(&st, keyi-1); StackPush(&st, begin); } } StackDestroy(&st); } 六、总结 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(logN) 4. 稳定性：不稳定 |
【本文地址】
今日新闻 |
推荐新闻 |