题解 | #排序#

排序

1、题意重述

给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

换句话说，就是对给定的数组进行排序

2、思路整理

使用快速排序：

Step1:在数组中随机选取一个元素作为分割点。

Step2：参照Step1选取的分割点，将数组中所有小于分割点的元素放在左半部分，大于分割点的元素放在右半部分。

Step3：对左右两个部分重复Step1和Step2，最后得到按照升序排列的数组。

3、代码实现

import java.util.*;
public class Solution {
    public int[] MySort (int[] arr) 
    {
        quickSort(arr , 0 , arr.length-1);
        return arr;
    }
    public void quickSort(int[] list, int l, int r) {
        if (l < r) 
        {
            // 分割数组，找到分割点
            int point = partition(list, l, r);
            // 递归调用，对左子数组进行快速排序
            quickSort(list, l, point - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, point + 1, r);
        }
    }

    public int partition(int[] list, int l, int r) {
        // 用数组的第一个元素作为基准数
        int first = list[l];
        while (l < r) {
            while (l < r && list[r] >= first) {
                r--;
            }

            // 交换
            swap(list, l, r);

            while (l < r && list[l] <= first) {
                l++;
            }

            // 交换
            swap(list, l, r);
        }
        // 返回分割点所在的位置
        return l;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

4、复杂度分析

时间复杂度：快速排序的平均时间复杂度为$O(NlogN)O(NlogN)$，最坏时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：由于递归调用，因此空间复杂度为$O(logN)O(logN)$。