快速排序

平均时间复杂度为O(nlogn)，不是稳定排序

递归实现

// 快速排序
// 算法思想：通过交换元素找到一个 基准 使得左边所有元素小于这个基准，右边所有元素大于这个基准
//之后左右两边循环执行这样的操作
func QuickSort(arr []int) {
    quickSort(arr, 0, len(arr)-1)
}

// 从0-len(arr)-1
func quickSort(arr []int, start, end int) {
    if start < end{
        // 找到基准 下标
        pivot := partition(arr, start, end)
        // 左边
        quickSort(arr, start, pivot - 1)
        // 右边
        quickSort(arr, pivot + 1, end)
    }
}

// 找到基准
// 直接先选择第一个元素
// 从后往前遍历，大于则移动；从前往后遍历，小于则移动。目的就是使得左边小于基准，右边大于基准，移动完之后交换左右元素
// 最后交换左指针和基准位置的值，左指针的位置即是基准的下标
func partition(arr []int, start, end int) int {
    p := arr[start]
    left, right := start, end
    for left < right {
        // 直到 右边元素小于第一个元素（基准）
        for left < right && arr[right] > p {	
            right --
        }
        // 直到 左边元素大于第一个元素（基准）
        for left<right && arr[left] <= p {
            left ++
        }
        // 交换这两个元素 使得小的在前面 大的在后面
        arr[left], arr[right] = arr[right], arr[left]
    }
    //将基准元素 移动到合适的位置 这个位置左边小于它，右边大于它
    arr[left], arr[start] = arr[start], arr[left]
    return left
}

非递归实现

// 快速排序 非递归实现
// 算法思想：用一个栈来保存开始和结束点，形成分区就会入栈，之后出栈寻找基准就是排序的过程
func sortArray(nums []int) []int {
    // 快速排序 非递归
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, start, end int) {
    // 使用栈保存下标
    stack := make([]int, 0)
    if start < end {
        // 入栈 先右后左
        stack = append(stack, end)
        stack = append(stack, start)
        for len(stack) != 0 {
            // 出栈来排序
            l := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            r := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 找到 基准
            pivot := partition(nums, l, r)
            // 是否左边形成分区
            if pivot - 1 > l {	
                stack = append(stack, pivot - 1)
                stack = append(stack, l)
            }
            // 右边是否形成分区
            if pivot + 1 < r {
                stack = append(stack, r)
                stack = append(stack, pivot + 1)
            } 
        }
    }   
}

// 寻找基准
func partition(nums []int, start, end int) int {
    p := nums[start]
    i, j := start, end
    for i<j {
        for i<j && nums[j] > p {
            j--
        }
        for i<j && nums[i] <= p {
            i++
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    nums[i], nums[start] = nums[start], nums[i]
    return i
}

CPP 实现

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 快速排序
        // 思路：先找到一个基准，使小于基准的放到左边，大于的放到右边，按照同样的方式排序左右
        if(nums.size() == 0) return nums;
        // 快排
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return ;

        int p = nums[left + right >> 1], i = left, j = right;
		// i < j 也可以
        while (i <= j) {
            // 直到 左边元素小大于中间基准元素
            while(nums[i] < p) i ++;
            // 直到 右边元素小于中间基准元素	
            while(nums[j] > p) j --;
            // 这里之后 i ++, j -- 是因为 交换后的顺序肯定是正确的
            // 之所以要判断，是因为 可能一个指针到基准位置了  (4, 6, 5, 3)
            // 之所以是 i <= j 而不是 i < j 是因为当他们相等的时候，都需要移动指针，不然就一直指在这了
            if (i <= j) swap(nums[i ++], nums[j --]);
        }
		// 最后变成两段，从 [l, j] 是小于等于 x的
        // 从 [i, r] 是大于等于x的
        quickSort(nums, left, j);
        quickSort(nums, i, right);
    }
};