C中的選擇排序通常寫成以下代碼的形式，引入一個變數，其中存盤回圈min_pos的特定步驟中陣列的最小編號的索引：for
void selectionsort(int A[], int n)
{
for (int i = 0; i < n - 1; i )
{
int min_pos = i;
for (int j = i 1; j < n; j )
{
if (A[j] < A[min_pos])
{
min_pos = j;
}
if (min_pos != i)
{
int temp;
temp = A[i];
A[i] = A[min_pos];
A[min_pos] = temp;
}
}
}
return;
}
但是，當我們使用下面的代碼可以得到相同的結果時，是否需要引入這個變數？
void selectionsort(int A[], int n)
{
for (int i = 0; i < n - 1; i )
{
for (int j = i 1; j < n; j )
{
if (A[j] < A[i])
{
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
return;
}
uj5u.com熱心網友回復：
這兩個函式都實作了相同的結果，但都不是選擇排序的正確實作。他們實作了一種效率較低的演算法，稱為交換排序。
對于選擇排序，應該對陣列中的每個元素執行一次交換。這可能是min_pos第一個函式中變數的目的。
這是修改后的版本：
void selectionsort(int A[], int n)
{
for (int i = 0; i < n - 1; i )
{
int min_pos = i;
for (int j = i 1; j < n; j )
{
if (A[j] < A[min_pos])
{
min_pos = j;
}
}
if (min_pos != i)
{
int temp = A[i];
A[i] = A[min_pos];
A[min_pos] = temp;
}
}
}
uj5u.com熱心網友回復：
這是一個名為 youtube 頻道的所有者的精彩解釋（未修改）：投資組合課程
哇 - 這是一個很棒的問題！:-) 所以上面的演算法也可以作業，但它只是以不同的方式對陣列進行排序。至于為什么我們可能不這樣做：
這是一個關于選擇排序的視頻，上面的演算法不是選擇排序（即使它很接近）。在選擇排序中，我們在未排序部分中找到最小/最大元素，并將其與最左邊的未排序演算法交換。其他方法也可能有效，但它們不再是選擇排序。上述方法將執行比所需更多的交換。
為了比較，我在這里修改了這段代碼來測驗兩種不同的演算法：https ://github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c 。我修改了代碼以計算所需的交換次數（請參閱下面的修改以了解選擇排序和您所做的這個新演算法）。選擇排序只需要 6 次交換，而上面的代碼需要 31 次交換。
使用選擇排序的原因之一是當執行交換的時間成本很高時它很有幫助：https ://en.wikipedia.org/wiki/Sorting_algorithm#Selection_sort 。我知道它是 Wikipedia，但請參閱這句話：“它只進行 n 次交換，因此在交換非常昂貴的情況下很有用。”
選擇排序：
int num_swaps = 0;
for (int i = 0; i < length - 1; i )
{
// find the position of the minimum element in the unsorted portion of
// the array
int min_pos = i;
for (int j = i 1; j < length; j )
if (a[j] > a[min_pos]) min_pos = j;
// if that element is NOT the element at index i, then swap that element
// with the element at index i
if (min_pos != i)
{
int temp = a[i];
a[i] = a[min_pos];
a[min_pos] = temp;
num_swaps ;
}
}
新演算法：
int num_swaps = 0;
for (int i=0; i<length-1; i )
{
for (int j=i 1; j<length; j )
{
if(a[i]>a[j])
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
num_swaps ;
}
}
}
uj5u.com熱心網友回復：
我認為這兩種演算法都不是特別有效，更有效的撰寫方法如下：
void selectionsort(int A[], int n)
{
for (int i = 0; i < n - 1; i )
{
int min_pos = i;
for (int j = i 1; j < n; j )
{
if (A[j] < A[min_pos])
{
min_pos = j;
}
}
if (min_pos != i)
{
int temp;
temp = A[i];
A[i] = A[min_pos];
A[min_pos] = temp;
}
}
return;
}
請注意 min_pos 變數如何用作交換位置的臨時存盤。這是有益的，因為交換需要三個操作，而使用 min_pos 只需要一個操作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/430186.html
上一篇：如何區分C中的0和NULL
下一篇：如何將此資料幀提取到csv檔案？