> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/sort.md).

# Sort

## 经典题目

[*41 First Missing Positive* ](https://leetcode.com/problems/first-missing-positive/description/)

Put each number in its right place. (a\[0] = 0 + 1, a\[1] = 1 + 1, etc.) For example, if a\[2] = 1, then swap(2, 0)

```java
public int firstMissingPositive(int[] nums) {
    if (nums == null || nums.length == 0) return 1;
    for (int i = 0; i < nums.length; i++) {
        int index = i;
        int value = nums[i];
        while (nums[i] <= nums.length && nums[i] >= 1 && nums[i] - 1 != i && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] - 1 != i) {
            return i + 1;
        }
    }
    return nums.length + 1;
}
```

[*215 Kth Largest Element in an Array*](https://leetcode.com/problems/kth-largest-element-in-an-array/description/)

暴 力解，直接sort，然后返回。其次，我们可以用heap求解。最优解，用quickSort思想。

{% tabs %}
{% tab title="Method 1" %}

```
// Sort the array: O(nlogn)
// Get nums[length - k]: O(1)
// T/O(nlogn)

```

{% endtab %}

{% tab title="Method 2" %}

```
// PriorityQueue (minHeap), keep size of k: O(nlogk)
// Get the min: O(logk)
// T/O(nlogk + logk)

```

{% endtab %}

{% tab title="Method 3" %}

```
// PriorityQueue (maxHeap), keep size of n - k + 1: ((n - k + 1)log(n - k + 1))
// Get the max: O(log(n - k + 1))
// T/O(nlog(n - k + 1))

```

{% endtab %}

{% tab title="Method 4" %}

```
// Quicksort idea, find the pivot of position n - k, so that all numbers to the left of the pivot <= pivot
// all numbers to the right of the pivot >= pivot
// T:O(n)/O(n^2)

```

{% endtab %}

{% tab title="Method 5" %}

```java
// Shuffle the input array
// Quick sort
// T/O(n)
 public int findKthLargest(int[] nums, int k) {
    shuffle(nums);
    k = nums.length - k;
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) {
            return nums[k];
        } else if (pivotIndex < k) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
    return -1;
}

private void shuffle(int[] nums) {
    Random random = new Random();
    for (int i = nums.length - 1; i >= 0; i--) {
        int j = random.nextInt(i + 1);
        swap(nums, i, j);
    }
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int lo = left;
    int hi = right - 1;
    while (lo <= hi) {
        if (nums[lo] < pivot) {
            lo += 1;
        } else if (nums[hi] >= pivot) {
            hi -= 1;
        } else {
            swap(nums, lo, hi);
        }
    }
    swap(nums, lo, right);
    return lo;
}

```

{% endtab %}
{% endtabs %}