C++程序对除一个之外的所有数组元素进行排序

给定一个数组和一个正整数k，按升序对数组进行排序，使得未排序数组中索引K处的元素保持不变，而所有其它元素均被排序。

举例:

Input : arr[] = {10, 4, 11, 7, 6, 20}
k = 2;
Output : arr[] = {4, 6, 11, 7, 10, 20}

Input : arr[] = {30, 20, 10}
k = 0
Output : arr[] = {30, 10, 20}

一种 简单的解决方案 是将给定数组中除k-th以外的所有元素复制到另一个数组中，然后使用排序算法对另一个数组进行排序。最后将排序后的数组再次复制到原始数组中。在复制时跳过k-th元素。

// C++ code for the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort an array in ascending order
// except for the element at index k
void sortExceptK(int arr[], int n, int k) {
    int temp[n - 1], index = 0;
    // Copy all elements except k-th to temp array
    for (int i = 0; i < n; i++) {
        if (i != k) {
            temp[index++] = arr[i];
        }
    }
 
    // Sort the temp array
    sort(temp, temp + n - 1);
 
    // Copy the sorted array back to original array
    index = 0;
    for (int i = 0; i < n; i++) {
        if (i != k) {
            arr[i] = temp[index++];
        }
    }
}
 
// Driver code
int main() {
    int arr[] = { 10, 4, 11, 7, 6, 20 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    // Function Call
    sortExceptK(arr, n, k);
 
    // Print final array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
}

输出

4 6 11 7 10 20

时间复杂度： 排序需要n*log 2 n时间，因此时间复杂度为O(n*log 2 n)。

空间复杂度： 创建了temp数组，因此空间复杂度为O(n)。

下面是一种 高效的解决方案 。

将k-th元素与最后一个元素交换。
对最后一个元素之外的所有元素进行排序。
对于从(k+1)-th到最后的每个元素，将它们向前移动一个位置。
将k-th元素复制回k位置。

// CPP program to sort all elements except
// element at index k.
#include <bits/stdc++.h>
using namespace std;
 
int sortExceptK(int arr[], int k, int n)
{
    // Move k-th element to end
    swap(arr[k], arr[n-1]);
 
    // Sort all elements except last
    sort(arr, arr + n - 1);
 
    // Store last element (originally k-th)
    int last = arr[n-1];
 
    // Move all elements from k-th to one
    // position ahead.
    for (int i=n-1; i>k; i--)
       arr[i] = arr[i-1];
 
    // Restore k-th element
    arr[k] = last;
}
 
// Driver code
int main()
{
    int a[] = {10, 4, 11, 7, 6, 20 };
    int k = 2;
    int n = sizeof(a) / sizeof(a[0]);
    sortExceptK(a, k, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
}