对接近排序（或K排序）的数组进行排序-yiteyi-C++库

给定一个由n个元素组成的数组，其中每个元素距离其目标位置的距离最多为k，设计一个以O（n logk）时间排序的算法。例如，让我们考虑k为2，排序数组中的索引7中的元素，可以在给定数组中的索引5, 6, 7，8, 9。

null

例如：

Input : arr[] = {6, 5, 3, 2, 8, 10, 9}            k = 3 Output : arr[] = {2, 3, 5, 6, 8, 9, 10}Input : arr[] = {10, 9, 8, 7, 4, 70, 60, 50}         k = 4Output : arr[] = {4, 7, 8, 9, 10, 50, 60, 70}

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们可以 使用插入排序 有效地对元素进行排序。下面是标准插入排序的C代码。

C++

                         /* Function to sort an array using insertion sort*/                       
                         void                                     insertionSort(                                     int                                     A[],                                     int                                     size)                       
                         {                       
                                                 int                                     i, key, j;                       
                                                 for                                     (i = 1; i < size; i++)                       
                                                 {                       
                                                 key = A[i];                       
                                                 j = i - 1;                       
           
                                                 /* Move elements of A[0..i-1], that are                       
                                                 greater than key, to one                       
                                                 position ahead of their current position.                       
                                                 This loop will run at most k times */                       
                                                 while                                     (j >= 0 && A[j] > key)                       
                                                 {                       
                                                 A[j + 1] = A[j];                       
                                                 j = j - 1;                       
                                                 }                       
                                                 A[j + 1] = key;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Shivani                       

C

                         /* Function to sort an array using insertion sort*/                       
                         void                                     insertionSort(                                     int                                     A[],                                     int                                     size)                       
                         {                       
                                                 int                                     i, key, j;                       
                                                 for                                     (i = 1; i < size; i++)                       
                                                 {                       
                                                 key = A[i];                       
                                                 j = i-1;                       
           
                                                 /* Move elements of A[0..i-1], that are                       
                                                 greater than key, to one                       
                                                 position ahead of their current position.                       
                                                 This loop will run at most k times */                       
                                                 while                                     (j >= 0 && A[j] > key)                       
                                                 {                       
                                                 A[j+1] = A[j];                       
                                                 j = j-1;                       
                                                 }                       
                                                 A[j+1] = key;                       
                                                 }                       
                         }                       

JAVA

                         /* Function to sort an array using insertion sort*/                       
                         static                                     void                                     insertionSort(                                     int                                     A[],                                     int                                     size)                       
                         {                       
                                                 int                                     i, key, j;                       
                                                 for                                     (i =                                     1                                     ; i < size; i++)                       
                                                 {                       
                                                 key = A[i];                       
                                                 j = i-                                     1                                     ;                       
           
                                                 /* Move elements of A[0..i-1], that                       
                                                 are greater than key, to one                       
                                                 position ahead of their current position.                       
                                                 This loop will run at most k times */                       
                                                 while                                     (j >=                                     0                                     && A[j] > key)                       
                                                 {                       
                                                 A[j+                                     1                                     ] = A[j];                       
                                                 j = j-                                     1                                     ;                       
                                                 }                       
                                                 A[j+                                     1                                     ] = key;                       
                                                 }                       
                         }                       

Python3

                         # Function to sort an array using                       
                         # insertion sort                       
           
                         def                                     insertionSort(A, size):                       
                                                 i, key, j                                     =                                     0                                     ,                                     0                                     ,                                     0                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 key                                     =                                     A[i]                       
                                                 j                                     =                                     i                                     -                                     1                       
           
                                                 # Move elements of A[0..i-1], that are                       
                                                 # greater than key, to one position                       
                                                 # ahead of their current position.                       
                                                 # This loop will run at most k times                       
                                                 while                                     j >                                     =                                     0                                     and                                     A[j] > key:                       
                                                 A[j                                     +                                     1                                     ]                                     =                                     A[j]                       
                                                 j                                     =                                     j                                     -                                     1                       
                                                 A[j                                     +                                     1                                     ]                                     =                                     key                       

C#

                         /* C# Function to sort an array using insertion sort*/                       
                         static                                     void                                     insertionSort(                                     int                                     A[],                                     int                                     size)                       
                         {                       
                                                 int                                     i, key, j;                       
                                   
                                                 for                                     (i = 1; i < size; i++) {                       
                                                 key = A[i];                       
                                                 j = i - 1;                       
           
                                                 /* Move elements of A[0..i-1], that are greater than                       
                                                 key, to one position ahead of their current                       
                                                 position. This loop will run at most k times */                       
                                                 while                                     (j >= 0 && A[j] > key) {                       
                                                 A[j + 1] = A[j];                       
                                                 j = j - 1;                       
                                                 }                       
                                                 A[j + 1] = key;                       
                                                 }                       
                         }                       

Javascript

                         /* Function to sort an array using insertion sort*/                       
                         function                                     insertionSort(A, size)                       
                         {                       
                                                 var                                     i, key, j;                       
                                                 for                                     (i = 1; i < size; i++)                       
                                                 {                       
                                                 key = A[i];                       
                                                 j = i-1;                       
           
                                                 /* Move elements of A[0..i-1], that are                       
                                                 greater than key, to one                       
                                                 position ahead of their current position.                       
                                                 This loop will run at most k times */                       
                                                 while                                     (j >= 0 && A[j] > key)                       
                                                 {                       
                                                 A[j+1] = A[j];                       
                                                 j = j-1;                       
                                                 }                       
                                                 A[j+1] = key;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by itsok.                       

内部循环最多运行k次。要将每个元素移动到正确的位置，最多需要移动k个元素。所以总的来说 复杂性将是O（nk）

我们可以对这样的数组进行排序 借助堆数据结构，效率更高 下面是使用堆的详细过程。 1）用前k+1个元素创建一个大小为k+1的最小堆。这需要O（k）时间（参见这件事 ) 2）一个接一个地从堆中移除min元素，将其放入结果数组中，并从剩余元素中向堆中添加一个新元素。删除一个元素并向min heap添加一个新元素将花费logk时间。所以总体复杂度将是O（k）+O（（n-k）*log（k））。

C++

                         // A STL based C++ program to sort a nearly sorted array.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Given an array of size n, where every element                       
                         // is k away from its target position, sorts the                       
                         // array in O(n logk) time.                       
                         int                                     sortK(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                   
                                                 // Insert first k+1 items in a priority queue (or min                       
                                                 // heap)                       
                                                 //(A O(k) operation). We assume, k < n.                       
                                                 //if size of array = k i.e k away from its target position                       
                                                 //then                       
                                                 int                                     size;                       
                                                 size=(n==k)?k:k+1;                       
                                                 priority_queue<                                     int                                     , vector<                                     int                                     >, greater<                                     int                                     > > pq(arr, arr +size);                       
           
                                                 // i is index for remaining elements in arr[] and index                       
                                                 // is target index of for current minimum element in                       
                                                 // Min Heap 'pq'.                       
                                                 int                                     index = 0;                       
                                                 for                                     (                                     int                                     i = k + 1; i < n; i++) {                       
                                                 arr[index++] = pq.top();                       
                                                 pq.pop();                       
                                                 pq.push(arr[i]);                       
                                                 }                       
           
                                                 while                                     (pq.empty() ==                                     false                                     ) {                       
                                                 arr[index++] = pq.top();                       
                                                 pq.pop();                       
                                                 }                       
                         }                       
           
                         // A utility function to print array elements                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     size)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < size; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     k = 3;                       
                                                 int                                     arr[] = { 2, 6, 3, 12, 56, 8 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 sortK(arr, n, k);                       
           
                                                 cout <<                                     "Following is sorted array"                                     << endl;                       
                                                 printArray(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // A java program to sort a nearly sorted array                       
                         import                                     java.util.Iterator;                       
                         import                                     java.util.PriorityQueue;                       
           
                         class                                     GFG {                       
                                                 private                                     static                                     void                                     kSort(                                     int                                     [] arr,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 // min heap                       
                                                 PriorityQueue<Integer> priorityQueue                       
                                                 =                                     new                                     PriorityQueue<>();                       
           
                                                 // add first k + 1 items to the min heap                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < k +                                     1                                     ; i++) {                       
                                                 priorityQueue.add(arr[i]);                       
                                                 }                       
           
                                                 int                                     index =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i = k +                                     1                                     ; i < n; i++) {                       
                                                 arr[index++] = priorityQueue.peek();                       
                                                 priorityQueue.poll();                       
                                                 priorityQueue.add(arr[i]);                       
                                                 }                       
           
                                                 Iterator<Integer> itr = priorityQueue.iterator();                       
           
                                                 while                                     (itr.hasNext()) {                       
                                                 arr[index++] = priorityQueue.peek();                       
                                                 priorityQueue.poll();                       
                                                 }                       
                                                 }                       
           
                                                 // A utility function to print the array                       
                                                 private                                     static                                     void                                     printArray(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     k =                                     3                                     ;                       
                                                 int                                     arr[] = {                                     2                                     ,                                     6                                     ,                                     3                                     ,                                     12                                     ,                                     56                                     ,                                     8                                     };                       
                                                 int                                     n = arr.length;                       
                                                 kSort(arr, n, k);                       
                                                 System.out.println(                                     "Following is sorted array"                                     );                       
                                                 printArray(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manpreet Singh(manpreetsngh294)                       

Python3

                         # A Python3 program to sort a                       
                         # nearly sorted array.                       
           
                         from                                     heapq                                     import                                     heappop, heappush, heapify                       
           
           
                         # A utility function to print                       
                         # array elements                       
                         def                                     print_array(arr:                                     list                                     ):                       
                                                 for                                     elem                                     in                                     arr:                       
                                                 print                                     (elem, end                                     =                                     ' '                                     )                       
           
                         # Given an array of size n, where every                       
                         # element is k away from its target                       
                         # position, sorts the array in O(nLogk) time.                       
           
           
                         def                                     sort_k(arr:                                     list                                     , n:                                     int                                     , k:                                     int                                     ):                       
                                                 """                       
                                                 :param arr: input array                       
                                                 :param n: length of the array                       
                                                 :param k: max distance, which every                       
                                                 element is away from its target position.                       
                                                 :return: None                       
                                                 """                       
                                                 # List of first k+1 items                       
                                                 heap                                     =                                     arr[:k                                     +                                     1                                     ]                       
           
                                                 # using heapify to convert list                       
                                                 # into heap(or min heap)                       
                                                 heapify(heap)                       
           
                                                 # "rem_elmnts_index" is index for remaining                       
                                                 # elements in arr and "target_index" is                       
                                                 # target index of for current minimum element                       
                                                 # in Min Heap "heap".                       
                                                 target_index                                     =                                     0                       
                                                 for                                     rem_elmnts_index                                     in                                     range                                     (k                                     +                                     1                                     , n):                       
                                                 arr[target_index]                                     =                                     heappop(heap)                       
                                                 heappush(heap, arr[rem_elmnts_index])                       
                                                 target_index                                     +                                     =                                     1                       
           
                                                 while                                     heap:                       
                                                 arr[target_index]                                     =                                     heappop(heap)                       
                                                 target_index                                     +                                     =                                     1                       
           
           
                         # Driver Code                       
                         k                                     =                                     3                       
                         arr                                     =                                     [                                     2                                     ,                                     6                                     ,                                     3                                     ,                                     12                                     ,                                     56                                     ,                                     8                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         sort_k(arr, n, k)                       
           
                         print                                     (                                     'Following is sorted array'                                     )                       
                         print_array(arr)                       
           
                         # This code is contributed by                       
                         # Veerat Beri(viratberi)                       

C#

                         // A C# program to sort a nearly sorted array                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG {                       
           
                                                 static                                     void                                     kSort(                                     int                                     [] arr,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 // min heap                       
                                                 List<                                     int                                     > priorityQueue =                                     new                                     List<                                     int                                     >();                       
           
                                                 // add first k + 1 items to the min heap                       
                                                 for                                     (                                     int                                     i = 0; i < k + 1; i++) {                       
                                                 priorityQueue.Add(arr[i]);                       
                                                 }                       
           
                                                 priorityQueue.Sort();                       
           
                                                 int                                     index = 0;                       
                                                 for                                     (                                     int                                     i = k + 1; i < n; i++) {                       
                                                 arr[index++] = priorityQueue[0];                       
                                                 priorityQueue.RemoveAt(0);                       
                                                 priorityQueue.Add(arr[i]);                       
                                                 priorityQueue.Sort();                       
                                                 }                       
           
                                                 int                                     queue_size = priorityQueue.Count;                       
           
                                                 for                                     (                                     int                                     i = 0; i < queue_size; i++) {                       
                                                 arr[index++] = priorityQueue[0];                       
                                                 priorityQueue.RemoveAt(0);                       
                                                 }                       
                                                 }                       
           
                                                 // A utility function to print the array                       
                                                 static                                     void                                     printArray(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     k = 3;                       
                                                 int                                     [] arr = { 2, 6, 3, 12, 56, 8 };                       
                                                 int                                     n = arr.Length;                       
                                                 kSort(arr, n, k);                       
                                                 Console.WriteLine(                                     "Following is sorted array"                                     );                       
                                                 printArray(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by divyeshrabadiya07.                       

Javascript

                         <script>                       
                         // A javascript program to sort a nearly sorted array                       
           
                         function                                     kSort(arr,n,k)                       
                         {                       
                                                 let priorityQueue=[];                       
                                                 // add first k + 1 items to the min heap                       
                                                 for                                     (let i = 0; i < k + 1; i++) {                       
                                                 priorityQueue.push(arr[i]);                       
                                                 }                       
                                                 priorityQueue.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                   
                                                 let index = 0;                       
                                                 for                                     (let i = k + 1; i < n; i++) {                       
                                                 arr[index++] = priorityQueue[0];                       
                                                 priorityQueue.shift();                       
                                                 priorityQueue.push(arr[i]);                       
                                                 priorityQueue.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                                 }                       
                                   
                                   
                                   
                                                 while                                     (priorityQueue.length != 0) {                       
                                                 arr[index++] = priorityQueue[0];                       
                                                 priorityQueue.shift();                       
                                                 }                       
                         }                       
           
                         // A utility function to print the array                       
                         function                                     printArray(arr,n)                       
                         {                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                         }                       
           
                         // Driver Code                       
                         let k = 3;                       
                         let arr = [ 2, 6, 3, 12, 56, 8 ];                       
                         let n = arr.length;                       
                         kSort(arr, n, k);                       
                         document.write(                                     "Following is sorted array<br>"                                     );                       
                         printArray(arr, n);                       
           
                         // This code is contributed by unknown2108                       
                         </script>                       

输出：

Following is sorted array2 3 6 8 12 56

基于最小堆的方法需要O（k）+O（（m）*log（k））时间，其中m=n–k并使用O（k）辅助空间。

我们也可以 使用平衡二叉搜索树 而不是堆来存储k+1元素。这个插入和删去平衡BST上的操作也需要O（logk）时间。因此，基于平衡BST的方法也需要O（n logk）时间，但基于堆的方法似乎更有效，因为最小元素始终位于根。此外，Heap不需要为左指针和右指针留出额外的空间。如果您发现上述任何代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章