【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱:feixiaoxing @163.com】
選擇排序是和冒泡排序差不多的一種排序。和冒泡排序交換相連數據不一樣的是,選擇排序只有在確定了最小的數據之後,才會發生交換。怎麼交換呢?我們可以以下面一組數據作為測試:
2,1,5,4,9
第一次排序:1,2,5,4,9
第二次排序:1,2,5,4,9
第三次排序:1,2,4,5,9
第四次排序:1,2,4,5,9
a)算法步驟
那麼從上面的排序步驟可以看到,選擇排序應該是這樣的:
(1)每次排序的時候都需要尋找第n小的數據,並且和array[n-1]發生交換
(2)等到n個數據都排序好,那麼選擇排序結束。
b)排序代碼
void select_sort(int array[], int length)
{
int inner, outer, index, value, median;
if(NULL == array || 0 == length)
return;
for(outer = 0; outer < length - 1; outer ++)
{
value = array[outer];
index = outer;
for(inner = outer +1; inner < length; inner ++){
if(array[inner] < value){
value = array[inner];
index = inner;
}
}
if(index == outer)
continue;
median = array[index];
array[index] = array[outer];
array[outer] = median;
}
}
void select_sort(int array[], int length)
{
int inner, outer, index, value, median;
if(NULL == array || 0 == length)
return;
for(outer = 0; outer < length - 1; outer ++)
{
value = array[outer];
index = outer;
for(inner = outer +1; inner < length; inner ++){
if(array[inner] < value){
value = array[inner];
index = inner;
}
}
if(index == outer)
continue;
median = array[index];
array[index] = array[outer];
array[outer] = median;
}
}
c) 測試用例
void print(int array[], int length)
{
int index;
if(NULL == array || 0 == length)
return;
for(index = 0; index < length; index++)
printf("%d", array[index]);
}
void test()
{
int data[] = {2, 1, 5, 4, 9};
int size = sizeof(data)/sizeof(int);
select_sort(data, size);
print(data, size);
}
void print(int array[], int length)
{
int index;
if(NULL == array || 0 == length)
return;
for(index = 0; index < length; index++)
printf("%d", array[index]);
}
void test()
{
int data[] = {2, 1, 5, 4, 9};
int size = sizeof(data)/sizeof(int);
select_sort(data, size);
print(data, size);
}
總結:
1)其實測試的方法很多,打印就是比較不錯的方式,不過只適合測試用例比較少的情形
2)算法可以先在草稿紙上驗證一遍,然後開始編程