java資料結構 第7章--排序算法06-快速排序

文章目錄

• • 7.9 快速排序
  • • 7.9.1快速排序法介紹:
    • 7.9.2快速排序法示意圖:
    • 7.9.3快速排序法應用執行個體:
    • • 1) 如果取消左右遞歸，結果是-9 -567 0 23 78 70
      • 2) 如果取消右遞歸,結果是-567 -9 0 23 78 70
      • 3) 如果取消左遞歸,結果是-9 -567 0 23 70 78
      • 4) 代碼實作
      • 5) 測試80w（1s）
      • 【學習筆記】
      • 【學習資料】

7.9 快速排序

7.9.1快速排序法介紹:

快速排序（Quicksort）是對冒泡排序的一種改進。基本思想是：通過一趟排序将要排序的資料分割成獨立的兩

部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排

序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列

7.9.2快速排序法示意圖:

7.9.3快速排序法應用執行個體:

要求: 對[-9,78,0,23,-567,70] 進行從小到大的排序，要求使用快速排序法。

說明[驗證分析]:

1) 如果取消左右遞歸，結果是-9 -567 0 23 78 70

2) 如果取消右遞歸,結果是-567 -9 0 23 78 70

3) 如果取消左遞歸,結果是-9 -567 0 23 70 78

4) 代碼實作

package sort;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;


public class QuickSort {
    public static void main(String[] args) {
        //int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};
        //測試快排的執行速度
        // 建立要給80000 個的随機的數組
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數
        }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的時間是=" + date1Str);
        quickSort(arr, 0, arr.length-1);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的時間是=" + date2Str);
        //System.out.println("arr=" + Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中軸值
        int pivot = arr[(left + right) / 2];
        int temp = 0; //臨時變量，作為交換時使用
        //while 循環的目的是讓比pivot 值小放到左邊
        //比pivot 值大放到右邊
        while( l < r) {
            //在pivot 的左邊一直找,找到大于等于pivot 值,才退出
            while( arr[l] < pivot) {
                l += 1;
            }
            //在pivot 的右邊一直找,找到小于等于pivot 值,才退出
            while(arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r 說明pivot 的左右兩的值，已經按照左邊全部是
            //小于等于pivot 值，右邊全部是大于等于pivot 值
            if( l >= r) {
                break;
            }
            //交換
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交換完後，發現這個arr[l] == pivot 值相等r--， 前移
            if(arr[l] == pivot) {
                r -= 1;
            }
            //如果交換完後，發現這個arr[r] == pivot 值相等l++， 後移
            if(arr[r] == pivot) {
                l += 1;
            }
        }
        // 如果l == r, 必須l++, r--, 否則為出現棧溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左遞歸
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右遞歸
        if(right > l) {
            quickSort(arr, l, right);
        }
    }
}
arr=[-9, 78, 0, 23, -567, 70, -1, 900, 4561]

Process finished with exit code 0
           

5) 測試80w（1s）

排序前的時間是=2021-04-11 23:04:12
排序前的時間是=2021-04-11 23:04:13

Process finished with exit code 0
           

【學習筆記】

java資料結構 第1章-内容架構介紹

java資料結構 第2章-資料結構和算法概述

java資料結構 第3章-稀疏數組和隊列

java資料結構 第4章-連結清單（單連結清單）

java資料結構 第4章-連結清單（雙向連結清單）

java資料結構 第5章–棧

java資料結構 第6章–遞歸

java資料結構 第7章–排序算法01

java資料結構 第7章–排序算法02-冒泡排序

java資料結構 第7章–排序算法03-選擇排序

java資料結構 第7章–排序算法04-插入排序

java資料結構 第7章–排序算法05-希爾排序

java資料結構 第7章–排序算法06-快速排序

java資料結構 第7章–排序算法07-歸并排序

java資料結構 第7章–排序算法08-基數排序

java資料結構 第7章–排序算法09-常用排序算法總結和對比！

持續更新

【學習資料】

• 視訊：尚矽谷Java資料結構與java算法（Java資料結構與算法）
• github：點選跳轉