这篇文章将为大家详细讲解有关Scala&Java如何实现快速排序，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
创新互联建站作为成都网站建设公司，专注网站建设公司、网站设计，有关成都定制网页设计方案、改版、费用等问题，行业涉及塔吊租赁等多个领域，已为上千家企业服务，得到了客户的尊重与认可。
算法思想:
在 arr[left..right] 中任选一个元素作为基准( pivot ), 下面代码都以 arr 的第一个元素为基准, 以此基准将当前 arr 划分为左、右两个子区间 arr[left..pivotpos-1] 和 arr[pivotpos+1..right], 并使左子区间中所有元素均小于等于基准元素 pivot, 右子区间中所有元素均大于等于 pivot, 而基准元素pivot 则位于正确的位置( pivotpos )上，它无须参加后续的排序
分别对左子区间 arr[left..pivotpos-1] 和右子区间 arr[pivotpos+1..right] 递归调用快速排序
Scala 代码:
1. 以 arr 第一个元素为基准( pivot )
def quickSort(arr: List[Int]): List[Int] = {
if (arr.length < 2) arr // 当前集合只有一个元素,则无需排序,直接返回
else quickSort(arr.filter(_ < arr.head)) // 对左子区间递归调用快速排序
++ (arr.filter(_ == arr.head)) // 与基准元素相等, 无须参加后续的排序
++ quickSort(arr.filter(_ > arr.head)) // 对右子区间递归调用快速排序
}2. 以 arr 中间那个元素为基准( pivot ) 优化
def quickSort(arr: List[Int]): List[Int] = {
if(arr.length < 2) a // 当前集合只有一个元素,则无需排序,直接返回
else {
val pivot = arr(arr.length / 2) // 以中间元素为基准( pivot )
quickSort(arr.filter(_ < pivot)) // 对左子区间递归调用快速排序
++ arr.filter(_ == pivot) // 与基准元素相等, 无须参加后续的排序
++ quickSort(arr.filter(_ > pivot)) // 对右子区间递归调用快速排序
}
}Scala 中:
List 集合的 filter( )方法: def filter(p: (A) => Boolean): List[A]
Scala 版的快速排序算法, 将快速排序的算法思想展示得淋漓尽致, 当然在确定基准元素位置上有一点点出入
Java 代码:
private void quickSort(int left, int right) {
if (left >= right) { // 当前数组只有一个元素,则无需排序,直接返回
return;
}
int temp = arr[left]; // 以第一个元素为基准( pivot )
int i = left;
int j = right;
while (i < j) {
while (arr[j] >= temp && i < j) { // 从后往前遍历, 找出小于基准元素的下标
j--;
}
while (arr[i] <= temp && i < j) { // 从前往后遍历, 找出大于基准元素的下标
i++;
}
// 交换前面两个下标的元素
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 将基准元素arr[left]置于基准位置i, 此时左子区间都小于基准元素, 右子区间都大于基准元素
arr[left] = arr[i];
arr[i] = temp;
quickSort(left, i - 1); // 对左子区间递归调用快速排序
quickSort(i + 1, right); // 对右子区间递归调用快速排序
}关于Scala&Java如何实现快速排序就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
