Problem Solving using C++

Algorithm Study using C++

排序算法总结(2)--选择排序和冒泡排序

前面给出了插入排序,其基于插入牌的机制
下面给出选择排序和冒泡排序的原理和实现

选择排序:
就是从后面的部分选择最小值(或者最大值)来代替前者,核心算法为:
for(int i=0;i<size;i++)
{
     //assume the smallest value is at size-1
      int temp = arr[size-1];
      int index = size-1;
 
      //compare the rest(from i--->size-1)
     for(j=i;j<size-1;j++)
     {
           if(arr[j]<temp)
          {
                temp = arr[j];
                index = j;
          }
     }

    //exchange the value
     if(index!=i)
    {
       arr[index]=arr[i];
       arr[i]=temp;
    }
}

具体代码实现为:
#include <iostream>
#include 
<algorithm>
#include 
<iterator>

using namespace std;

int main(int argc,char* argv[])
{
    
int arr[]={5,6,1,2,7,3,8,10,4,9};
    
int size = sizeof(arr)/sizeof(arr[0]);
    
    copy(arr,arr
+size,ostream_iterator<int>(cout," "));
    cout
<<endl;

    
for(int i=0;i<size;i++)
    {
        
int temp = arr[size-1];
        
int index = size-1;
        
        
for(int j=i;j<size-1;j++)
        {
            
if(arr[j]<temp)
            {
                temp 
= arr[j];
                index 
= j;
            }
        }
        
        
if(i!=index)
        {
            arr[index]
=arr[i];
            arr[i]
=temp;
        }
    }
    
    copy(arr,arr
+size,ostream_iterator<int>(cout," "));
    cout
<<endl;
    
    system(
"pause");

    
return 0;
}

冒泡算法主要是从后面开始往上面进行冒泡,需要冒泡的话,必须要相邻的元素之间进行比较,其实现代码如下:
#include <iostream>
#include 
<algorithm>
#include 
<iterator>

using namespace std;

int main(int argc,char* argv[])
{
    
int arr[]={5,6,1,2,7,3,8,10,4,9};
    
int size = sizeof(arr)/sizeof(arr[0]);
    
    copy(arr,arr
+size,ostream_iterator<int>(cout," "));
    cout
<<endl;

   
for(int i=0;i<size;i++)
    for(int j=size-1;j>i;j--)
    {
        if(arr[j]<arr[j-1])
        {
            int temp = arr[j];
            arr[j]=arr[j-1];
            arr[j-1]=temp;
        }
    }

    
    copy(arr,arr
+size,ostream_iterator<int>(cout," "));
    cout
<<endl;
    
    system(
"pause");

    
return 0;
}

posted on 2007-08-22 10:38 Kingoal Lee's Alogrithm Study using cplusplus 阅读(259) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜