Skip to content

Commit 662b915

Browse files
dairongpengdairongpeng
committed
quick sort
1 parent ebb070c commit 662b915

File tree

1 file changed

+90
-172
lines changed

1 file changed

+90
-172
lines changed

‎03-归并排序、随机快排.md

Lines changed: 90 additions & 172 deletions
Original file line numberDiff line numberDiff line change
@@ -325,195 +325,113 @@ T(N) = T((1/3)N) + T((2/3)N) + O(N)
325325
326326
> 空间复杂度：O(logN)。空间复杂度产生于每次递归partion之后，我们需要申请额外的空间变量保存相等区域的左右两侧的位置。那么每次partion需要申请两个变量，多少次partion？实质是该递归树被分了多少层，树的高度，有好有坏，最好logN,最差N。随机选择num之后，期望仍然是概率累加，收敛于O(logN)。
327327
328-
```Java
329-
package class03;
330-
331-
public class Code03_PartitionAndQuickSort {
332-
333-
public static void swap(int[] arr, int i, int j) {
334-
int tmp = arr[i];
335-
arr[i] = arr[j];
336-
arr[j] = tmp;
337-
}
338-
339-
// partion问题
340-
public static int partition(int[] arr, int L, int R) {
341-
if (L > R) {
342-
return -1;
343-
}
344-
if (L == R) {
345-
return L;
346-
}
347-
int lessEqual = L - 1;
348-
int index = L;
349-
while (index < R) {
350-
if (arr[index] <= arr[R]) {
351-
swap(arr, index, ++lessEqual);
352-
}
353-
index++;
354-
}
355-
swap(arr, ++lessEqual, R);
356-
return lessEqual;
357-
}
358-
359-
// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
360-
// 小于arr[R]放左侧 等于arr[R]放中间 大于arr[R]放右边
361-
// 返回中间区域的左右边界
362-
public static int[] netherlandsFlag(int[] arr, int L, int R) {
363-
// 不存在荷兰国旗问题
364-
if (L > R) {
365-
return new int[] { -1, -1 };
366-
}
367-
// 已经都是等于区域，由于用R做划分返回R位置
368-
if (L == R) {
369-
return new int[] { L, R };
370-
}
371-
int less = L - 1; // < 区 右边界
372-
int more = R; // > 区 左边界
373-
int index = L;
374-
while (index < more) {
375-
// 当前值等于右边界，不做处理，index++
376-
if (arr[index] == arr[R]) {
377-
index++;
378-
// 小于交换当前值和左边界的值
379-
} else if (arr[index] < arr[R]) {
380-
swap(arr, index++, ++less);
381-
// 大于右边界的值
382-
} else {
383-
swap(arr, index, --more);
384-
}
385-
}
386-
// 比较完之后，把R位置的数，调整到等于区域的右边，至此大于区域才是真正意义上的大于区域
387-
swap(arr, more, R);
388-
return new int[] { less + 1, more };
389-
}
390-
391-
public static void quickSort1(int[] arr) {
392-
if (arr == null || arr.length < 2) {
393-
return;
394-
}
395-
process1(arr, 0, arr.length - 1);
396-
}
397-
398-
public static void process1(int[] arr, int L, int R) {
399-
if (L >= R) {
400-
return;
401-
}
402-
// L..R上partition 标记位为arr[R] 数组被分成 [ <=arr[R] arr[R] >arr[R] ]，M为partion之后标记位处在的位置
403-
int M = partition(arr, L, R);
404-
process1(arr, L, M - 1);
405-
process1(arr, M + 1, R);
406-
}
328+
```Go
329+
package main
407330

408-
public static void quickSort2(int[] arr) {
409-
if (arr == null || arr.length < 2) {
410-
return;
411-
}
412-
process2(arr, 0, arr.length - 1);
413-
}
331+
// swap 交换数组中的两个位置的数
332+
func swap(arr []int, i, j int) {
333+
tmp := arr[i]
334+
arr[i] = arr[j]
335+
arr[j] = tmp
336+
}
414337

415-
public static void process2(int[] arr, int L, int R) {
416-
if (L >= R) {
417-
return;
338+
// partition 对数组进行partition处理
339+
func partition(arr []int, L, R int) int {
340+
if L > R {
341+
return -1
342+
}
343+
if L == R {
344+
return L
345+
}
346+
// 选定左边界的左边一个位置作为小于区域的起点
347+
lessEqual := L - 1
348+
index := L
349+
// 每次搞定一个位置
350+
for index < R {
351+
if arr[index] <= arr[R] {
352+
lessEqual++
353+
swap(arr, index, lessEqual)
418354
}
419-
// 每次partion返回等于区域的范围
420-
int[] equalArea = netherlandsFlag(arr, L, R);
421-
// 对等于区域左边的小于区域递归，partion
422-
process2(arr, L, equalArea[0] - 1);
423-
// 对等于区域右边的大于区域递归，partion
424-
process2(arr, equalArea[1] + 1, R);
355+
index++
425356
}
357+
lessEqual++
358+
swap(arr, lessEqual, R)
359+
return lessEqual
360+
}
426361

427-
public static void quickSort3(int[] arr) {
428-
if (arr == null || arr.length < 2) {
429-
return;
362+
// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
363+
// 小于arr[R]放左侧 等于arr[R]放中间 大于arr[R]放右边
364+
// 返回中间区域的左右边界
365+
func netherlandsFlag(arr []int, L, R int) []int {
366+
// 不存在荷兰国旗问题
367+
if L > R {
368+
return []int{-1, -1}
369+
}
370+
371+
// 已经都是等于区域，由于用R做划分返回R位置
372+
if L == R {
373+
return []int{L, R}
374+
}
375+
376+
// < 区 右边界
377+
less := L - 1
378+
// > 区 左边界
379+
more := R
380+
index := L
381+
for index < more {
382+
// 当前值等于右边界，不做处理，index++
383+
if arr[index] == arr[R] {
384+
index++
385+
} else if arr[index] < arr[R] { // 小于交换当前值和左边界的值
386+
less++
387+
swap(arr, index, less)
388+
index++
389+
} else { // 大于右边界的值
390+
more--
391+
swap(arr, index, more)
430392
}
431-
process3(arr, 0, arr.length - 1);
432393
}
394+
// 比较完之后，把R位置的数，调整到等于区域的右边，至此大于区域才是真正意义上的大于区域
395+
swap(arr, more, R)
396+
return []int{less + 1, more}
397+
}
433398

434-
public static void process3(int[] arr, int L, int R) {
435-
if (L >= R) {
436-
return;
437-
}
438-
// 随机选择位置，与arr[R]上的数做交换
439-
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
440-
int[] equalArea = netherlandsFlag(arr, L, R);
441-
process3(arr, L, equalArea[0] - 1);
442-
process3(arr, equalArea[1] + 1, R);
399+
func QuickSort1(arr []int) {
400+
if len(arr) < 2 {
401+
return
443402
}
444403

445-
// for test
446-
public static int[] generateRandomArray(int maxSize, int maxValue) {
447-
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
448-
for (int i = 0; i < arr.length; i++) {
449-
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
450-
}
451-
return arr;
452-
}
404+
sortByPartition(arr, 0, len(arr)-1)
405+
}
453406

454-
// for test
455-
public static int[] copyArray(int[] arr) {
456-
if (arr == null) {
457-
return null;
458-
}
459-
int[] res = new int[arr.length];
460-
for (int i = 0; i < arr.length; i++) {
461-
res[i] = arr[i];
462-
}
463-
return res;
407+
func sortByPartition(arr []int, L int, R int) {
408+
if L >= R {
409+
return
464410
}
465411

466-
// for test
467-
public static boolean isEqual(int[] arr1, int[] arr2) {
468-
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
469-
return false;
470-
}
471-
if (arr1 == null && arr2 == null) {
472-
return true;
473-
}
474-
if (arr1.length != arr2.length) {
475-
return false;
476-
}
477-
for (int i = 0; i < arr1.length; i++) {
478-
if (arr1[i] != arr2[i]) {
479-
return false;
480-
}
481-
}
482-
return true;
483-
}
412+
// L到R上进行partition 标记位为arr[R] 数组被分成 [ <=arr[R] arr[R] >arr[R] ]，M为partition之后标记位处在的位置
413+
M := partition(arr, L, R)
414+
sortByPartition(arr, L, M-1)
415+
sortByPartition(arr, M+1, R)
416+
}
484417

485-
// for test
486-
public static void printArray(int[] arr) {
487-
if (arr == null) {
488-
return;
489-
}
490-
for (int i = 0; i < arr.length; i++) {
491-
System.out.print(arr[i] + " ");
492-
}
493-
System.out.println();
418+
func QuickSort2(arr []int) {
419+
if len(arr) < 2 {
420+
return
494421
}
422+
sortByNetherlandsFlag(arr, 0, len(arr)-1)
423+
}
495424

496-
// for test
497-
public static void main(String[] args) {
498-
int testTime = 500000;
499-
int maxSize = 100;
500-
int maxValue = 100;
501-
boolean succeed = true;
502-
for (int i = 0; i < testTime; i++) {
503-
int[] arr1 = generateRandomArray(maxSize, maxValue);
504-
int[] arr2 = copyArray(arr1);
505-
int[] arr3 = copyArray(arr1);
506-
quickSort1(arr1);
507-
quickSort2(arr2);
508-
quickSort3(arr3);
509-
if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
510-
succeed = false;
511-
break;
512-
}
513-
}
514-
System.out.println(succeed ? "Nice!" : "Oops!");
515-
425+
func sortByNetherlandsFlag(arr []int, L int, R int) {
426+
if L >= R {
427+
return
516428
}
517429

430+
// 每次partition返回等于区域的范围,荷兰国旗问题
431+
equalArea := netherlandsFlag(arr, L, R)
432+
// 对等于区域左边的小于区域递归，partition
433+
sortByNetherlandsFlag(arr, L, equalArea[0]-1)
434+
// 对等于区域右边的大于区域递归，partition
435+
sortByNetherlandsFlag(arr, equalArea[1]+1, R)
518436
}
519437
```

0 commit comments

Comments
 (0)