Sắp xếp mảng ngoại trừ một phần tử được chỉ định

Cho một mảng số nguyên n phần tử, n > 0. Sắp xếp mảng tăng dần sao cho phần tử tại vị trí k < n(cho trước) vẫn giữ nguyên vị trí sau khi mảng được sắp xếp.

Các bước làm:

B1: Swap phần tử tại vị trí k với phần tử cuối cùng trong mảng

B2: Sắp xếp mảng từ 0 -> n – 2

B3: Dịch chuyển tất cả các phần tử từ vị trí k sang 1 ô.

B4: Chuyển phần tử cuối cùng về vị trí k

import java.util.Arrays;

public class Main {

    public static void sortArrayExceptOne(int[] arr, int n, int k) {
        // Chuyển phần tử tại vị trí k về cuối mảng
        int tmp = arr[k];
        arr[k] = arr[n - 1];
        arr[n - 1]  = tmp;

        // Sắp xếp mảng từ 0 -> n - 2
        // Hàm sort của thư viện sẽ hiểu thứ tự 1 -> n nên mình truyền là n - 1
        // Mục đích sắp xếp các phần tử từ đầu cho đến phần tử kế cuối
        Arrays.sort(arr, 0, n - 1);

        // Chuyển các phần tử vị trí k sang 1 ô
        for (int i = n - 1;i > k; i--) {
            arr[i] = arr[i - 1];
        }

        // Chuyển phần tử cuối cùng về vị trí k
        arr[k] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {10, 4, 11, 7, 6, 20};
        int k = 2;
        sortArrayExceptOne(arr, arr.length, k);
        for(int e : arr)
            System.out.print(e + " ");
    }
}

Output: 4 6 11 7 10 20

Độ phức tạp: O(nlogn)

Link đề bài: https://www.geeksforgeeks.org/sorting-array-elements-except-one/