简单的设计网站,做哪个网站好,网站设计制作合同,网站链接交易快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法#xff0c;其基本思想是#xff1a;任取待排序序列中的某元素作为基准值#xff0c;按照该基准值将待排序集合分割成两个子序列#xff0c;左子序列中所有元素均小于基准值#xff0c;右子序列中所有元素均大于…快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法其基本思想是任取待排序序列中的某元素作为基准值按照该基准值将待排序集合分割成两个子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后左右子序列递归该过程直到所有元素都排列在相应的位置上为止。
排序对象数组、链表时间复杂度空间复杂度是否稳定否
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}
上述为快速排序算法递归实现的主框架与二叉树前序遍历的规则类似。
快速排序算法可以由多种实现方法如霍尔法、挖坑法、前后指针法目前最优的算法是前后指针法其基本思路是
选择数组中的一个元素作为枢轴一般是第一个元素其元素为关键值key而key值最好是数组的中位数仅在前中后三个元素中取中位数将数组划分为两个子数组左子数组的元素都小于等于枢轴元素右子数组的元素都大于等于枢轴元素对这两个子数组分别递归调用快速排序算法继续进行划分和排序递归的结束条件是子数组的长度为1或0即已经有序或为空数组不需要再进行排序通过不断划分和排序最终实现整体的排序在划分过程中通过比价元素与枢轴元素的大小关系将元素划分到对应的区域 // 数组开始、中间、结尾三个元素找到中位数将其作为key值并返回下标
int MidIndex(int* arr, int l, int m, int r)
{if (arr[l] arr[r]){if (arr[m] arr[l])return l;else if (arr[m] arr[r])return r;elsereturn m;}else{if (arr[m] arr[l])return l;else if (arr[m] arr[r])return r;elsereturn m;}
}// 前后指针法快慢指针法
// 快排每一次递归的核心就是PtrPtr算法返回新的关键字key的下标
// 每一次PtrPtr算法就是为了将小于key的数移到key的左边将大于key的数移到key的右边
// 当多次进行递归后数组的有序度已经很高了所以此时也可以不再递归而是采用直接插入排序
int PtrPtr(int* arr, int begin, int end)
{if (begin end)return;int slow begin;int fast slow 1;while (fast end){if (arr[fast] arr[begin] slow ! fast)Swap(arr[slow], arr[fast]);fast;}Swap(arr[begin], arr[slow]);return slow; // 返回新的key值下标
}void QuickSort(int* arr, int begin, int end)
{if (begin end)return;int mid (begin end) / 2;int iKey MidIndex(arr, begin, mid, end);Swap(arr[begin], arr[iKey]);iKey PtrPtr(arr, begin, end);QuickSort(arr, begin, iKey - 1);QuickSort(arr, iKey 1, end);
}
