search

bitmori / neonmori.github.io

このノートに書き下ろし、星空で巡ってく
1 stars 0 forks source link

快速排序 #35

Open bitmori opened 4 years ago

bitmori commented 4 years ago

partition函數的思路：

注意slice，不是整個array

  1. 選擇一個pivot，然後移動到slice的末尾
  2. 開始從頭遍歷當前slice，比pivot小的就和最左邊的未確定元素交換，用一個變量儲存這個位置left
  3. 將pivot與slice[left]交換，left就是pivot的最終位置

quicksort就是二分調用partition: 隨意選出一個pivot，然後調用一次partition，獲得這個pivot的最終位置，順便還將左右的數值分好了 然後對左右兩半遞歸調用quicksort