# 對幾乎排序（或 K 排序）的數組進行排序 > 原文： [https://www.geeksforgeeks.org/nearly-sorted-algorithm/](https://www.geeksforgeeks.org/nearly-sorted-algorithm/) 給定 n 個元素的數組，其中每個元素距離其目標位置最多 k 個，設計一種算法，以 O（n log k）時間排序。 例如，讓我們考慮 k 為 2，在排序數組中索引 7 處的元素可以在給定數組中索引 5、6、7、8、9 處。 **示例**： ``` 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 = 4 Output : 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; ???} } ```