How to implement Quick sort by Scala&Java

This article will explain in detail how to achieve quick sorting in Scala&Java. The content of the article is of high quality, so the editor will share it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Algorithm idea:

Select any element in arr [left..right] as the pivot, the following code takes the first element of arr as the benchmark, divides the current arr into two left and right subintervals arr [left.dattpos-1] and arr [pivotpos+1..right] so that all elements in the left subinterval are less than or equal to the benchmark element pivot, and all elements in the right subinterval are greater than or equal to pivot While the base element pivot is in the correct position (pivotpos) It does not need to participate in subsequent sorting.

Quick sort is called recursively on the left subinterval arr [left.. pivotpos+1..right TPOs-1] and the right subinterval arr [pivotpos+1..right] respectively.

Scala Code:

1. Based on the first element of 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) / / A pair of right subinterval recursive calls to quick sort}

two。 Pivot optimization based on the element in the middle of arr

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) / / A pair of right subinterval recursive calls to quick sort}}

In Scala:

The filter () method of the List collection: def filter (p: (a) = > Boolean): List [A]

The Scala version of the fast sorting algorithm shows the algorithm idea of quick sorting incisively and vividly, of course, there is a slight difference in determining the position of the benchmark elements.

Java Code:

Private void quickSort (int left, int right) {if (left > = right) {/ / the current array has only one element, then return;} int temp = arr [left] is returned without sorting; / / int I = left; int j = right; while (I) based on the first element

< j) { while (arr[j] >

= temp & & I < j) {/ / traverse from back to front to find the subscript Jmurmuri;} while (arr [I]) that is smaller than the base element