數據結構基礎(1) --Swap & Bubble-Sort & Select-Sort
來源：程序員人生 發布時間：2015-01-05 08:12:39 閱讀次數：3221次
Swap的簡單實現
//C語言方式(by-pointer):
template <typename Type>
bool swapByPointer(Type *pointer1, Type *pointer2)
{
//確保兩個指針不會指向同1個對象
if (pointer1 == NULL || pointer2 == NULL)
{
return false;
}
if (pointer1 != pointer2)
{
Type tmp = *pointer1;
*pointer1 = *pointer2;
*pointer2 = tmp;
}
return true;
}
//C++特有方式(by-reference):
template <typename Type>
void swapByReference(Type &value1, Type &value2)
{
if (value2 != value1)
{
Type tmp = value1;
value1 = value2;
value2 = tmp;
}
}
小結:
雖然我們自己實現了swap,但我們還是比較推薦使用C++ STL已實現好的std::swap()函數,其存在于命名空間std中,使用實例以下面的<冒泡排序>.
冒泡排序(Bubble-Sort)
算法思想:
從左到右掃描數據,找出最大的元素,將其放到數組右側;
進程:
循環比較相鄰的兩個數,如果左側的數比右側的大,則交換兩個數;
//實現:注意代碼中的3個注意點(x):
template <typename Type>
void bubbleSort(Type *begin, Type *end)
{
if ((begin == end) || (begin == NULL) || (end == NULL))
return ;
int length = end - begin;
//注意點(1):保證1旦數組有序, 則會直接停止排序, 不會在繼續進行無用的循環
bool isOrder = false;
//外層循環控制掃描次數(length⑴)
//注意點(2):N個元素其實只需N⑴次掃描
for (int i = 0; !isOrder && i < length⑴; ++i)
{
//首先假定這次數組已有序
isOrder = true;
//注意點(3):確保能夠從0掃描到最后1個未排序的元素
for (Type *iter = begin; iter < end-i⑴; ++iter)
{
//如果前面的左側的元素>右側的元素
if (*iter > *(iter+1))
{
//交換
std::swap(*iter, *(iter+1));
isOrder = false;
}
}
}
}
template <typename Type>
void bubbleSort(Type *array, int length)
{
return bubbleSort(array, array+length);
}
選擇排序(Select-Sort)
思想:
從當前還沒有排序的序列當選擇1個最小的元素, 將之放到已排序的序列的隊列的末尾;
要點:
1.注意3個指針(inner, outer, miner)所代表的含義;
2.同時注意是從未排序的序列中進行查找最小元素!
//實現
template <typename Type>
void selectSort(Type *begin, Type *end)
{
if ((begin == end) || (begin == NULL) || (end == NULL))
return ;
//只要循環到最后1個元素的前1個就好了,由于剩下的那個肯定是最大的
for (Type *outer = begin; outer < end⑴; ++outer)
{
//注意:是從還沒有排序的序列中查找(miner = outer, inner = outer+1)
Type *miner = outer;
//從miner+1開始遍歷數組, 尋覓1個元素值小于*miner的
for (Type *inner = outer+1; inner < end; ++inner)
{
if (*inner < *miner)
miner = inner;
}
if (miner != outer)
std::swap(*miner, *outer);
}
}
//為了能夠讓STL的標準容器如vector使用
template <typename Iterator>
void selectSort(Iterator iter1, Iterator iter2)
{
return selectSort(&(*iter1), &(*iter2));
}
template <typename Type>
void selectSort(Type *array, int length)
{
return selectSort(array, array+length);
}
小結:
雖然我們自己實現了Bubble-Sort和Select-Sort,但我們在實際軟件開發中1般是不會用到的,由于的它的效力為O(N^2),效力太慢^_^, 因此我們還是推薦使用C++ STL中已實現了的std::sort(), 其內部原理使用了快速排序, 效力為O(logN)速度非常快.
附-測試程序
int main()
{
srand(time(NULL));
vector<double> dVec;
int count = 10;
while (count --)
{
dVec.push_back((rand()%1000)/100.0);
}
selectSort(dVec.begin(), dVec.end());
for (vector<double>::iterator iter = dVec.begin(); iter < dVec.end(); ++iter)
{
cout << *iter << endl;
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
