快速排序

1、Java 代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        // 打印排序前的数组
        System.out.println(Arrays.toString(nums));

        // 执行快速排序操作
        quickSort(nums,0,nums.length - 1);

        // 打印排序后的数组
        System.out.println(Arrays.toString(nums));

        return null;
    }


    // 函数传入待排序数组 nums
    // 排序区间的左端点 left
    // 排序区间的右端点 right
    private void quickSort(int[] nums,int left, int right){

        // 如果 left 大于等于 right,说明该区间只有 1 个或者没有元素
        if( left >=right ){
            // 无需再递归划分后再排序,直接返回
            return;
        }

        // 调用函数 partition,将 left 和 right 之间的元素划分为左右两部分
        int mid = partition(nums,left,right);

        // 划分之后,再对 mid 左侧的元素进行快速排序
        quickSort(nums,left,mid - 1);

        // 划分之后,再对 mid 右侧的元素进行快速排序
        quickSort(nums,mid + 1,right);


    }

    private int partition(int[] nums, int left ,int right){

        // 经典快速排序的写法
        // 设置当前区间的第一个元素为基准元素
        int pivot = nums[left];

        // left 向右移动,right 向左移动,直到 left 和 right 指向同一元素为止
        while( left < right ){

            // 只有当遇到小于 pivot 的元素时,right 才停止移动
            // 此时,right 指向了一个小于 pivot 的元素,这个元素不在它该在的位置上
            while( left < right && nums[right] >= pivot ){
                // 如果 right 指向的元素是大于 pivot 的,那么
                // right 不断的向左移动
                right--;
            }

            // 将此时的 nums[left] 赋值为 nums[right]
            // 执行完这个操作,比 pivot 小的这个元素被移动到了左侧
            nums[left] = nums[right];


            // 只有当遇到大于 pivot left 才停止移动
            // 此时,left 指向了一个大于 pivot 的元素,这个元素不在它该在的位置上
            while( left < right && nums[left] <= pivot){
                // 如果 left 指向的元素是小于 pivot 的,那么
                // left 不断的向右移动
                left++;
            }

            // 将此时的 nums[right] 赋值为 nums[left]
            // 执行完这个操作,比 pivot 大的这个元素被移动到了右侧
            nums[right] = nums[left];

        }

        // 此时,left 和 right 相遇,那么需要将此时的元素设置为 pivot
        // 这个时候,pivot 的左侧元素都小于它,右侧元素都大于它
        nums[left] = pivot;




        // 返回 left
        return left;

    }
}

2、C++ 代码

3、Python 代码

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)

  • 在下振予 永久会员 2021年11月28日 下午3:42

    分享c++代码如下:
    #include
    #include
    #include
    #include
    const int N = 1000;
    int nums[N] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int partition(int left, int right)
    {
    // 设置当前区间第一个元素为基准
    int pivot = nums[left];

    while(left = pivot){
    // 如果right指向的元素是大于povit的,那么right不断的向左移动
    // 只有当遇到小于pivot的元素时,right才停止移动
    right –;
    }

    // 将此时的nums[left]赋值为nums[right]
    // 执行完这个操作,比pivot小的这个元素被移动到了左侧
    nums[left] = nums[right];

    while(left < right && nums[left] = right)
    return;

    // 调用函数partition, 将left 和right 之间的元索划分为左右两部分
    int mid = partition(left, right);
    // 划分之后,再对mid左侧的元素进行快速排序
    quickSort(left, mid – 1);
    // 划分之后,再对mid右侧的元素进行快速排序
    quickSort(mid + 1, right);

    }
    int main()
    {
    int m;
    scanf(“%d”,&m);
    quickSort(0, m – 1);
    for(int i = 0;i <= m – 1;++i){
    printf("%d ",nums[i]);
    }
    return 0;
    }