我想跟蹤一個簡單的c + +排序功能的比較量。保持比較執行排序
void sort(int arr[], int size)
{
int startScan, minIndex, minValue;
for (startScan = 0; startScan < (size - 1); startScan++)
{
minIndex = startScan;
minValue = arr[startScan];
for (int index = startScan + 1; index < size; index++)
{
if (arr[index] < minValue)
{
minValue = arr[index];
minIndex = index;
}
}
arr[minIndex] = arr[startScan];
arr[startScan] = minValue;
}
}
我玩弄我想可能返回進行的比較的數量,並在第一次也許是比較的數量將在startScan
舉行認爲值。當然不是,開始掃描只能保持最大尺寸-1。這絕對不是進行比較的次數。
我想也許它會在變量索引中找到。所以我創建了int temp = index;
,因爲我很懶,不想處理它,但是當我返回temp的值時,它也僅僅是size-1。不知道爲什麼我期望有什麼不同,但我想我會嘗試。
然後我開始考慮這個問題......我甚至知道比較在哪裏發生?
原來我不知道我是否做。我想我所有的比較都發生在第二個循環中,即 for (int index = startScan + 1; index < size; index++)
,甚至還有嵌套在裏面的if
聲明。
無論何時if
語句運行,它都會比較一些內容。 SWEET,我想。所以我在我的函數頂部創建了int temp = 0;
,在if語句中打了一個temp++
,並認爲這肯定會給我一些比較結果。
這次給了我一個鼓舞人心的數字。當對隨機列表中的13個數字進行排序時(我隨機選擇了隨機數字),我的temp返回了18的值。就我所知,對我而言,與我的任何其他數字都沒有線性關係。
所以這是我真正的問題。這是否工作?我的最終代碼是否按照我希望的方式執行,並確實返回進行的比較次數?或者我只是發現了另一個任意數字,我只是比其他測試中得到的其他數字更接近我。我不知道如何手動計算比較次數。我喜歡這個號碼,但是我知道它可能會有所改變。
最終代碼:
int sort(int arr[], int size)
{
int temp = 0;
int startScan, minIndex, minValue;
for (startScan = 0; startScan < (size - 1); startScan++)
{
minIndex = startScan;
minValue = arr[startScan];
for (int index = startScan + 1; index < size; index++)
{
if (arr[index] < minValue)
{
minValue = arr[index];
minIndex = index;
temp++;
}
}
arr[minIndex] = arr[startScan];
arr[startScan] = minValue;
}
return temp;
}
每個循環也有每次迭代時間的比較。 – lcs
所以我想我的第一個循環會運行'大小-1'次,我的第二個循環也會運行'大小-1'次,然後我的if循環運行多次? Addem都起來了嗎? – Podo
那麼,當條件爲真時,'temp'變量現在只會增加。當它是錯誤的時候也會發生比較。 – lcs