在嘗試排序時，我想出了一種似乎類似于某種插入排序的排序。
不同之處在于，在交換時，我不必比較從元素索引到索引 0 的元素（最壞情況）。
它也類似于分而治之的排序演算法，因為它模擬同一陣列中的已排序扇區和未排序扇區。
我的看法是，最初我會將當前元素指定為第一個元素。然后我會將當前元素與下一個元素進行比較。如果電流更大，我交換元素。然后我遞減以保持當前索引不變。
否則，我增加以推進當前索引。
這意味著我的當前將始終是最新的參考值。被比較的其他值總是較小的并已排序。
請參考代碼：
#include<stdio.h>
void printArray(int *a, int l)
{
int i = 1;
printf("[%d", a[0]);
while(i < l)
{
printf(", %d", a[i]);
i;
}
printf("]\n");
}
void whatSort(int *a, int l)
{
int i = 0;
int temp;
while(i < (l - 1))
{
if(*(a i) > *(a i 1))
{
temp = *(a i);
*(a i) = *(a i 1);
*(a i 1) = temp;
--i;
}
else
{
i;
}
}
}
int main(void)
{
//int array[] = {42, 18, 74, 2, 35, 92, 37, 25};
int array[] = {6, 5, 3, 1, 8, 7, 2, 4};
printArray(array, 8);
whatSort(array, 8);
printArray(array, 8);
return 0;
}
我很確定這種（雙關語）已經存在，但我無法找到名字。很高興知道它叫什么。盡管如此，我還是需要幫助計算此類代碼的運行時復雜度。這是我想出的。任何幫助將非常感激。
對于這種特殊情況，假設每個操作需要 1 個時間單位。
Declaration
Assignment
Declaration
Loop condition will run l - 1 times:
Comparison
Subtraction
Loop inside code will run l - 2 times:
IF statement:
Dereference
Addition
Comparison
Dereference
Addition
Addition
Assignment
Dereference
Addition
Dereference
Addition
Assignment
Dereference
Addition
Addition
Dereference
Addition
Addition
Assignment
Decrement
OR
ELSE statement:
Increment
最終，我想出了 O(n) 其中：
Worst case = 3 [2 * (l - 1)] [6 * (l - 2)] [14 * (l - 2)]
O(22n - 39)
O(n)
Best case = 3 [2 * (l - 1)] [6 * (l - 2)] (l - 2)
O(9n - 13)
O(n)
uj5u.com熱心網友回復：
抱歉，沒有比 O(n log n) 更好的排序演算法，除非您對輸入設定了一些限制。
目前此代碼不起作用。
例如，如果第一個元素大于第二個元素（在您的示例中就是這種情況），則i遞減。最初i=0如此，現在如此i=-1。回圈重新啟動，您嘗試訪問a[-1]，并且出現分段錯誤。錯誤是
然后我遞減以保持當前索引不變。
這不是發生的事情，正如您所說，索引遞減，因此不保留該值。
這是輸出
編輯：
即使這種情況得到糾正，以下情況也不是真的
代碼內部回圈將運行 l - 2 次：
該演算法總是試圖讓第 (i 1) 個元素到達正確的位置，最壞的情況是將它帶到第一個位置。
當 時index == 0，您最多進行一次交換。當 時index == 1，您最多進行兩次交換。當 時index == 2，您最多進行 3 次交換。
這種情況會發生，直到您到達陣列的末尾。所以，1x2x3x...x(n-1)，即 O(n2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/384814.html