這篇文章將為大家詳細講解有關(guān)Scala&Java如何實現(xiàn)快速排序，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

創(chuàng)新互聯(lián)建站作為成都網(wǎng)站建設(shè)公司，專注網(wǎng)站建設(shè)公司、網(wǎng)站設(shè)計，有關(guān)成都定制網(wǎng)頁設(shè)計方案、改版、費用等問題，行業(yè)涉及塔吊租賃等多個領(lǐng)域，已為上千家企業(yè)服務(wù)，得到了客戶的尊重與認可。

算法思想:

1. 在 arr[left..right] 中任選一個元素作為基準( pivot ), 下面代碼都以 arr 的第一個元素為基準, 以此基準將當前 arr 劃分為左、右兩個子區(qū)間 arr[left..pivotpos-1] 和 arr[pivotpos+1..right], 并使左子區(qū)間中所有元素均小于等于基準元素 pivot, 右子區(qū)間中所有元素均大于等于 pivot, 而基準元素pivot 則位于正確的位置( pivotpos )上，它無須參加后續(xù)的排序

2. 分別對左子區(qū)間 arr[left..pivotpos-1] 和右子區(qū)間 arr[pivotpos+1..right] 遞歸調(diào)用快速排序

Scala 代碼:

1. 以 arr 第一個元素為基準( pivot )

def quickSort(arr: List[Int]): List[Int] = {
    if (arr.length < 2) arr    // 當前集合只有一個元素,則無需排序,直接返回
    else quickSort(arr.filter(_ < arr.head))  // 對左子區(qū)間遞歸調(diào)用快速排序
         ++ (arr.filter(_ == arr.head))    // 與基準元素相等, 無須參加后續(xù)的排序
         ++ quickSort(arr.filter(_ > arr.head))   // 對右子區(qū)間遞歸調(diào)用快速排序
}

2. 以 arr 中間那個元素為基準( pivot )    優(yōu)化

def quickSort(arr: List[Int]): List[Int] = {
	if(arr.length < 2) a    // 當前集合只有一個元素,則無需排序,直接返回
	else {
		val pivot = arr(arr.length / 2)    // 以中間元素為基準( pivot )
		quickSort(arr.filter(_ < pivot))    // 對左子區(qū)間遞歸調(diào)用快速排序
		++ arr.filter(_ == pivot)    // 與基準元素相等, 無須參加后續(xù)的排序
		++ quickSort(arr.filter(_ > pivot))    // 對右子區(qū)間遞歸調(diào)用快速排序
	}
}

Scala 中:

List 集合的 filter( )方法: def filter(p: (A) => Boolean): List[A]

Scala 版的快速排序算法, 將快速排序的算法思想展示得淋漓盡致, 當然在確定基準元素位置上有一點點出入

Java 代碼:

private void quickSort(int left, int right) {
  if (left >= right) {    // 當前數(shù)組只有一個元素,則無需排序,直接返回
   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, 此時左子區(qū)間都小于基準元素, 右子區(qū)間都大于基準元素
  arr[left] = arr[i];
  arr[i] = temp;
  quickSort(left, i - 1);    // 對左子區(qū)間遞歸調(diào)用快速排序
  quickSort(i + 1, right);    // 對右子區(qū)間遞歸調(diào)用快速排序
}

關(guān)于Scala&Java如何實現(xiàn)快速排序就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

本文題目：Scala&Java如何實現(xiàn)快速排序
本文網(wǎng)址：http://chinadenli.net/article16/gsgggg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、做網(wǎng)站、全網(wǎng)營銷推廣、網(wǎng)站收錄、服務(wù)器托管、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)