快速排序（Quick Sort）是對(duì)冒泡排序的一種改進(jìn)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)序列分成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)都要小，然后按此方法對(duì)兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程遞歸進(jìn)行，最終使整個(gè)數(shù)據(jù)序列變成有序的數(shù)據(jù)序列。

快速排序算法的原理
快速排序算法的原理是：選擇一個(gè)關(guān)鍵值作為基準(zhǔn)值（一般選擇第1個(gè)元素為基準(zhǔn)元素），將比基準(zhǔn)值大的都放在右邊的序列中，將比基準(zhǔn)值小的都放在左邊的序列中。具體的循環(huán)過程如下。
（1）從后向前比較，用基準(zhǔn)值和最后一個(gè)值進(jìn)行比較。如果比基準(zhǔn)值小，則交換位置；如果比基準(zhǔn)值大，則繼續(xù)比較下一個(gè)值，直到找到第1個(gè)比基準(zhǔn)值小的值才交換位置。
（2）在從后向前找到第1個(gè)比基準(zhǔn)值小的值并交換位置后，從前向后開始比較。如果有比基準(zhǔn)值大的，則交換位置；如果沒有，則繼續(xù)比較下一個(gè)，直到找到第1個(gè)比基準(zhǔn)值大的值才交換位置。
（3）重復(fù)執(zhí)行以上過程，直到從前向后比較的索引大于等于從后向前比較的索引，則結(jié)束一次循環(huán)。這時(shí)對(duì)于基準(zhǔn)值來說，左右兩邊都是有序的數(shù)據(jù)序列。
（4）重復(fù)循環(huán)以上過程，分別比較左右兩邊的序列，直到整個(gè)數(shù)據(jù)序列有序。

如下圖所示是對(duì)數(shù)組[6,9,5,7,8]進(jìn)行快速排序。

先以第1個(gè)元素6為基準(zhǔn)值，從數(shù)組的最后一位從后向前比較（比較順序?yàn)?#xff1a;8>6、7>6、5<6），找到第1個(gè)比6小的數(shù)據(jù)5，然后進(jìn)行第1次位置交換，即將數(shù)據(jù)6（索引為0）和數(shù)據(jù)5（索引為2）交換位置，之后基準(zhǔn)值6位于索引2處；接著從前向后比較（比較順序?yàn)?#xff1a;5<6、9>6），找到第1個(gè)比6大的數(shù)據(jù)9，然后進(jìn)行第2次位置交換，即將數(shù)據(jù)6（索引為2）和數(shù)據(jù)9（索引為1）交換位置，交換后6位于索引1處；這時(shí)高位和低位都在6處，第一次遞歸完成。在第一次遞歸完成后，基準(zhǔn)值6前面的數(shù)據(jù)都比6小，基準(zhǔn)值6后面的數(shù)據(jù)都比6大。重復(fù)執(zhí)行上述過程，直到整個(gè)數(shù)組有序。

快速排序的java實(shí)現(xiàn)

import java.util.*;public class Solution {/*** 快速排序* @param arr 數(shù)組* @param low 最低位* @param high 最高位* @return 排序好的數(shù)組*/public static int[] quickSort(int[] arr, int low, int high) {int left = low; //從前向后比較的索引int right = high; //從后向前比較的索引int key = arr[low]; //基準(zhǔn)值while (left < right) {//從后向前比較while (left < right && arr[right] >= key) {right--;}//如果沒有比基準(zhǔn)值小的，則比較下一個(gè)，直到有比基準(zhǔn)值小的，則交換位置，然后又從前向后比較if (arr[right] <= key) {int temp = arr[right];arr[right] = arr[left];arr[left] = temp;}//從前向后比較while (left < right && arr[left] <= key) {left++;}//如果沒有比基準(zhǔn)值大的，則比較下一個(gè)，直到有比基準(zhǔn)值大的，則交換位置if (arr[left] >= key) {int temp = arr[left];arr[left] = arr[right];arr[right] = temp;}}//此時(shí)第一次循環(huán)比較結(jié)束，基準(zhǔn)值的位置已經(jīng)確定。左邊的值都比關(guān)鍵值小，右邊的值都比關(guān)鍵值大，但是兩邊的順序還有可能不一樣，接著進(jìn)行下面的遞歸調(diào)用//遞歸左邊序列：從第一個(gè)索引位置到“關(guān)鍵值索引-1”if (left > low) {quickSort(arr,low,left-1);}//遞歸右邊序列：從“關(guān)鍵值索引+1”到最后一個(gè)位置if (right < high) {quickSort(arr,right+1,high);}return arr;}public static void main(String[] args) {int[] arr = {8,7,9,5,6,4,3,2};int[] nums = quickSort(arr,0, arr.length-1);System.out.println(Arrays.toString(nums));} }

以上代碼定義了名為quickSort()的快速排序方法，在該方法中定義了3個(gè)變量start、end和key，分別表示從前向后比較的索引、從后向前比較的索引和基準(zhǔn)值。具體過程為：①通過while循環(huán)從后向前比較，找到比基準(zhǔn)值小的，則交換位置；②通過while循環(huán)從前向后比較，找到比基準(zhǔn)值大的，則交換位置；③根據(jù)從前向后比較的索引和從后向前比較的索引的大小不斷遞歸調(diào)用，直到遞歸完成，返回排序后的結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的java实现快速排序以及快速排序的原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。