快速排序

對冒泡排序的一種改進
思路:
一趟排序后,選取一個中間值,數組被分為比中間值小的部分,比中間值大的部分;再對左右兩部分分別遞歸排序
代碼實現

import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr = {-9, 78, 0, 23, -567, 70};System.out.println("排序前---");System.out.println(Arrays.toString(arr));quickSort(arr, 0, arr.length - 1);System.out.println("排序后---");System.out.println(Arrays.toString(arr));}public static void quickSort(int[] arr, int start, int end) {//結束左右遞歸if (start < end) {
//找到基準數,中間值,標準數//把數組中第0個數字作為標準數//start從開始取標準數int stard = arr[start];//記錄需要排序的下標,從開始到結尾int low = start;int high = end;//循環地去找比標準數大與小的數,結束條件為low==highwhile (low < high) {//先找高的這邊//如果高的比標準數小則交換,如果大則下標往前走while (low < high && stard <= arr[high]) {high--;}//結束循環時,就已經找到了要交換的數字下標//右邊的數字換到左邊arr[low] = arr[high];while (low < high && stard >= arr[low]) {low++;}//左邊的數字換到右邊arr[high] = arr[low];}//當low與high重合時,標準數就要放入合適的位置//或arr[high]都可以arr[low] = stard;//遞歸處理左右兩邊的排序//左邊 開始位置 --> 到低的位置quickSort(arr, start, low);
//右邊 從低的位置加1 -->結束位置//或++lowquickSort(arr, low + 1, end);}}}

無注釋版

import java.util.Arrays;public class TestQuickSort {public static void main(String[] args) {int[] arr = {-9, 78, 0, 23, -567, 70};System.out.println("排序前---");System.out.println(Arrays.toString(arr));Sort(arr, 0, arr.length - 1);System.out.println("排序后---");System.out.println(Arrays.toString(arr));}private static void Sort(int[] arr, int start, int end) {if (start < end) {int middle = arr[start];int left = start;int right = end;while (left < right) {while (left < right && middle <= arr[right]) {right--;}arr[left] = arr[right];while (left < right && middle >= arr[left]) {left++;}arr[right] = arr[left];}arr[left] = middle;Sort(arr, start, left);Sort(arr, left + 1, end);}}
}

參考騰訊課堂