直接選擇排序和直接插入排序類似,都將數據分為有序區和無序區,所不同的是直接播放排序是將無序區的第一個元素直接插入到有序區以形成一個更大的有序區,而直接選擇排序是從無序區選一個最小的元素直接放到有序區的最後。
設數組為a[0…n-1]。
1. 初始時,數組全為無序區為a[0..n-1]。令i=0
2. 在無序區a[i…n-1]中選取一個最小的元素,將其與a[i]交換。交換之後a[0…i]就形成了一個有序區。
3. i++並重復第二步直到i==n-1。排序完成。
直接選擇排序無疑是最容易實現的,下面給出代碼:
void Selectsort(int a[], int n)
{
int i, j, nMinIndex;
for (i = 0; i < n; i++)
{
nMinIndex = i; //找最小元素的位置
for (j = i + 1; j < n; j++)
if (a[j] < a[nMinIndex])
nMinIndex = j;
Swap(a[i], a[nMinIndex]); //將這個元素放到無序區的開頭
}
}
在這裡,要特別提醒各位注意下Swap()的實現,建議用:
inline void Swap(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
筆試面試時考不用中間數據交換二個數,很多人給出了
inline void Swap1(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}
在網上搜索下,也可以找到許多這樣的寫法。不過這樣寫存在一個隱患,如果a, b指向的是同一個數,那麼調用Swap1()函數會使這個數為0。如:
int i = 6;
Swap1(i, i);
printf("%d\n", i);
當然誰都不會在程序中這樣的寫代碼,但回到我們的Selectsort(),如果a[0]就是最小的數,那麼在交換時,將會出現將a[0]置0的情況,這種錯誤相信調試起來也很難發現吧,因此建議大家將交換二數的函數寫成:
inline void Swap(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
或者在Swap1()中加個判斷,如果二個數據相等就不用交換了:
inline void Swap1(int &a, int &b)
{
if (a != b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
PHP 冒泡排序法 http://www.linuxidc.com/Linux/2014-08/105971.htm
經典排序之冒泡排序 http://www.linuxidc.com/Linux/2014-07/104762.htm
Python實現冒泡排序法 http://www.linuxidc.com/Linux/2014-06/103897.htm
Go語言實現冒泡排序 http://www.linuxidc.com/Linux/2014-06/103844.htm
C++ 使用模板實現冒泡排序 http://www.linuxidc.com/Linux/2014-02/96914.htm
Java簡單排序之冒泡排序代碼 http://www.linuxidc.com/Linux/2013-11/92782.htm
冒泡排序優化版,性能近乎翻倍 http://www.linuxidc.com/Linux/2013-09/90710.htm