Scala&Java如何实现快速排序
这篇文章将为大家详细讲解有关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如何实现快速排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
当前标题:Scala&Java如何实现快速排序
文章位置:http://scyanting.com/article/gsgggg.html