快速排序.md

快速排序

知识准备

• 荷兰国旗问题

思路

参考荷兰国旗问题思路, 只不过快排中是自己指定一个num

代码

PHP

<?php

class QuickSort
{
    public static function sort(&$arr, $L, $R)
    {
        if ($L < $R) {
            $part = self::partition($arr, $L, $R);
            self::sort($arr, $L, $part[0] - 1);
            self::sort($arr, $part[1] + 1, $R);
        }
    }

    public static function partition(&$arr, $L, $R)
    {
        $less = $L - 1;
        $more = $R + 1;
        $curr = $L;
        // 数组最后一个数作为要比较的数
        $num = $arr[$R];

        while ($curr < $more) {
            if ($arr[$curr] < $num) {
                // 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
                self::swap($arr, $curr++, ++$less);
            } elseif ($arr[$curr] > $num) {
                // 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
                self::swap($arr, $curr, --$more);
            } else {
                // 小于区域不移, 大于区域也不移, curr右移
                $curr++;
            }
        }

        return [$less + 1, $more - 1];
    }

    public static function swap(&$arr, $i, $j)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
QuickSort::sort($arr, 0, count($arr) - 1);
// [2, 3, 4, 6, 7]
var_dump($arr);

JAVA

import java.util.Arrays;

public class QuickSort {
	public static void quickSort(int[] arr, int L, int R) {
		if (L < R) {
			int[] part = partition(arr, L, R);
			quickSort(arr, L, part[0] - 1);
			quickSort(arr, part[1] + 1, R);
		}
	}
	
	public static int[] partition(int[] arr, int L, int R) {
		int less = L - 1;
		int more = R + 1;
		int curr = L;
		// 数组最后一个数作为要比较的数
		int num = arr[R];
		
		while (curr < more) {
			if (arr[curr] < num) {
				// 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
				swap(arr, ++less, curr++);
			} else if (arr[curr] > num) {
				// 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
				swap(arr, --more, curr);
			} else {
				// 小于区域不移, 大于区域也不移, curr右移
				curr++;
			}
		}
		
		return new int[] { less + 1, more - 1 };
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 4, 2, 7};
		// [2, 3, 4, 6, 7]
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
}

随机快排

上述代码是经典快排, 经典快排受样本的影响, 在最坏情况下([1, 2, 3, 4, 5, 6]), 经典快排的时间复杂度是O(N^2)

随机快排不是固定的将数组最后一个数作为要比较的数

代码

<?php

class QuickSort
{
    public static function sort(&$arr, $L, $R)
    {
        if ($L < $R) {
            $part = self::partition($arr, $L, $R);
            self::sort($arr, $L, $part[0] - 1);
            self::sort($arr, $part[1] + 1, $R);
        }
    }

    public static function partition(&$arr, $L, $R)
    {
        $less = $L - 1;
        $more = $R + 1;
        $curr = $L;
        // 随机
        $num = $arr[mt_rand($L, $R)];

        while ($curr < $more) {
            if ($arr[$curr] < $num) {
                // 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
                self::swap($arr, $curr++, ++$less);
            } elseif ($arr[$curr] > $num) {
                // 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
                self::swap($arr, $curr, --$more);
            } else {
                // 小于区域不移, 大于区域也不移, curr右移
                $curr++;
            }
        }

        return [$less + 1, $more - 1];
    }

    public static function swap(&$arr, $i, $j)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
QuickSort::sort($arr, 0, count($arr) - 1);
// [2, 3, 4, 6, 7]
var_dump($arr);

随机快排的时间复杂度是O(NlogN)