/** 與最右邊的數(shù)比較,* 小于的放在左邊* 大于的放在右邊* 等于的放在中間*/public static int[] netherlandsFlag(int[] arr, int L, int R){if(L>R){return new int[]{-1,-1};}if(L == R){return new int[]{L,R};}int less = L-1;int more = R;int index = L;while(index<more){if(arr[index] == arr[R]){index++;}else if(arr[index] < arr[R]){swap(arr,++less,index++);}else if(arr[index] > arr[R]){swap(arr,--more,index);}}swap(arr,R,more);return new int[]{less+1,more};}

?

?引出快速排序

public class QuickSortTest {public static void main(String[] args) {int[] arr = {5,3,7,2,0,3,4,1,5};quicksort(arr,0,arr.length-1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}public static void quicksort(int[] arr, int L, int R){if(L >= R){return;}swap(arr, L+(int)Math.random()*(R-L+1),R); // 隨機(jī)選擇一個(gè)數(shù),和最后一個(gè)數(shù)交換int[] nether = netherlandsFlag(arr,L,R);quicksort(arr,L,nether[0]-1);quicksort(arr,nether[1]+1,R);}private static void swap(int[] arr, int h, int t){int temp = arr[h];arr[h] = arr[t];arr[t] = temp;}/** 與最右邊的數(shù)比較,* 小于的放在左邊* 大于的放在右邊* 等于的放在中間*/public static int[] netherlandsFlag(int[] arr, int L, int R){if(L>R){return new int[]{-1,-1};}if(L == R){return new int[]{L,R};}int less = L-1;int more = R;int index = L;while(index<more){if(arr[index] == arr[R]){index++;}else if(arr[index] < arr[R]){swap(arr,++less,index++);}else if(arr[index] > arr[R]){swap(arr,--more,index);}}swap(arr,R,more);return new int[]{less+1,more}; // 等于區(qū)域的范圍} }

?

總結(jié)

以上是生活随笔為你收集整理的数据结构-荷兰国旗问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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