Problem Solving using C++

Algorithm Study using C++

排序算法总结(1)---概述

常见的排序方式有6种:
---简单排序里面的有:插入排序、选择排序、冒泡排序,时间复杂度为O(n^2)
---线性对数阶的排序: 归并排序(merge sort),快速排序,堆排序,时间复杂度为O(nlogn)

在n<=50的情况下,最好使用插入排序或者选择排序,由于选择排序移动次数比插入排序少,在数据量比较多的情况,推荐使用选择排序。
如果序列基本上正序了,则使用插入排序、冒泡排序或者随机的快速排序
在n非常大的情况下,使用O(nlogn)的算法,即归并排序、快速排序、堆排序。后2者是不稳定的排序,而merge排序是稳定的排序方式,快速排序是基于比较的排序中的最好的排序方法。

实验条件下算法运行时间:(单位毫秒,10万随机数)
冒泡排序:    56953
选择排序:    20109
插入排序:    14547
归并排序:    134
堆排序:        67
快速排序:    28

三种O(nlogn)的排序时间比较为:
排序算法        10万   100万     1000万
归并排序       134       1309     13985
堆排序           67         865        14292
快速排序       28         513        9815

下面给出insertion sort的原理和实现
insertion sort是稳定排序,在数据量非常小的情况下,非常快速。其原理就如同打牌的时候按顺序插入牌一样(来自introdution to algorithm),从后面往前面找大于最新的牌的数,然后往后面替换,再将最新的牌插入进去完成了前面的牌是已经排序好的。核心算法如下:
for(int i=1;i<size;i++)
{
     //get the new card
    int temp = arr[i];
    int j=i-1;

    while((j>=0)&&(arr[j]>temp))//find the old card bigger than the new card
    {
        arr[j+1]=arr[j];
        j--;
    }

    //get the position of the new card
    arr[j+1]=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=1;i<size;i++)
    {
        
int temp = arr[i];
        
int j=i-1;
        
        
while((arr[j]>temp)&&(j>=0))
        {
            arr[j
+1]=arr[j];
            j
--;
        }
        
        arr[j
+1]=temp;
    }
    
    copy(arr,arr
+size,ostream_iterator<int>(cout," "));
    cout
<<endl;
    
    system(
"pause");

    
return 0;
}



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


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


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜