文章摘要
该文章介绍了Quicksort算法的实现,展示了如何通过递归的方法对整数列表进行排序。文章详细描述了Quicksort的主要步骤:首先处理边界情况,当列表长度小于等于1时直接返回;然后选择第一个元素作为基准值,将列表划分为三个部分(小于基准值的集合、等于基准值的集合和大于基准值的集合);接着对小于和大于基准值的部分分别递归排序;最后将排序后的三个部分合并,得到最终的有序列表。文章还提供了主函数代码,对一个具体的整数数组进行了排序并输出结果。
void main() {
List<int> quickSort(List<int> arr) {
// 处理边界问题
if (arr.length <=1) {
return arr;
}
// 取出第一个值作为参考
int splitData=arr[0];
// 小于参考值的集合
List<int> low=[];
// 大于参考值的集合
List<int> hight=[];
// 与参考相等的集合
List<int> mid=[];
// 初次把参考值添加到mid中
mid.add(splitData);
for (int i=1; i < arr.length; i++) {
if (arr[i] < splitData) {
// 小于
low.add(arr[i]);
} else if (arr[i] > splitData) {
// 大于
hight.add(arr[i]);
} else {
// 等于
mid.add(arr[i]);
}
}
// 二分数据后,再继续递归整理
low=quickSort(low);
hight=quickSort(hight);
// 最后合并
return […low, …mid, …hight];
}
const List<int> ary=[4, 5, 1, 3, 6, 2, 5, 6, 7, 2, 4];
print(quickSort(ary));
}
List<int> quickSort(List<int> arr) {
// 处理边界问题
if (arr.length <=1) {
return arr;
}
// 取出第一个值作为参考
int splitData=arr[0];
// 小于参考值的集合
List<int> low=[];
// 大于参考值的集合
List<int> hight=[];
// 与参考相等的集合
List<int> mid=[];
// 初次把参考值添加到mid中
mid.add(splitData);
for (int i=1; i < arr.length; i++) {
if (arr[i] < splitData) {
// 小于
low.add(arr[i]);
} else if (arr[i] > splitData) {
// 大于
hight.add(arr[i]);
} else {
// 等于
mid.add(arr[i]);
}
}
// 二分数据后,再继续递归整理
low=quickSort(low);
hight=quickSort(hight);
// 最后合并
return […low, …mid, …hight];
}
const List<int> ary=[4, 5, 1, 3, 6, 2, 5, 6, 7, 2, 4];
print(quickSort(ary));
}
© 版权声明
文章版权归作者所有,未经允许请勿转载。