注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秋雨冬雪NO1

互联网资源收集

 
 
 

日志

 
 

c++编程各种内部排序方法  

2012-04-25 09:18:52|  分类: 代码大全 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先,从时间性能上说:
1. 按平均的时间性能来分,有三类排序方法:
时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;
时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤为如此;
时间复杂度为O(n)的排序方法只有,基数排序。
2. 当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应该尽量避免的情况。
3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
其次,从空间性能上说:
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1);
2. 快速排序为O(logn),为栈所需的辅助空间;
3. 归并排序所需辅助空间最多,其空间复杂度为O(n);
4. 链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)。
再次,从排序方法的稳定性能上说:
稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。对于不稳定的排序方法,只要能举出一个实例说明即可。我们需要指出的是:快速排序和堆排序是不稳定的排序方法。
int * ShellSort(int * array,int num)
{
    int d=num;
    while(d>1)
    {
        d=(d+1)/2;
        for(int i=d;i<num;i++)
        {
            if(array[i]<array[i-d])
            {
                int tmp=array[i];
                for(int j=i-d;j>=0&&tmp<array[j];j-=d)
                    array[j+d]=array[j];
                array[j+d]=tmp;
            }
        }
    }
    return array;
}
归并排序,不知道这样算不算 非递归 VS2008中编译运行,加上必要的头文件就行。 C/C++ codetypedef int dataType;

int arraySize = 0; //全局数组大小

int _tmain(int argc, _TCHAR* argv[])
{   
    void MergeSort(dataType *ptrArray);
    void MergePass(dataType *ptrA, dataType *ptrB, int s);
    void Merge(dataType *ptrA, dataType *ptrB, int begin, int mid, int end);
    //////////////////////////////////////////////////////////////////////////


    dataType intArray[7] = {3, 6, 4, 12, 8, 5, 14};

    arraySize = sizeof(intArray) / sizeof(dataType);

    MergeSort(intArray);

    for(int i = 0; i != 7; ++i){
        printf("%d ",intArray[i]);
    }
    printf("\n");


    return 0;
}

/********************************************************************/
/*如何合并?                                */
/*两手各指着(已排好的)左右两堆的最小数据,取出两者中较小的一个后,*/
/*随即指向那一堆的手移向下一层的数据,                    */
/*永远不必翻下面的数据,只需要盯着最上面的两个数据            */
/********************************************************************/

void Merge(dataType *ptrA, dataType *ptrB, int begin, int mid, int end)
{
    int i = begin, k = begin;
    int j = mid + 1;

    while(i <= mid && j <= end){
        if(ptrA[i] < ptrA[j])
            ptrB[k++] = ptrA[i++];
        else
            ptrB[k++] = ptrA[j++];
    }
    if (i > mid)
        while (j <= end)
            ptrB[k++] = ptrA[j++];
    else
        while (i <= mid)
            ptrB[k++] = ptrA[i++];
}

/********************************/
/*对相邻为s的一段序列排序    */
/*3  6  4  12  8   5   14    */
/* [3,6] [4,12] [5,8] [14]    */
/*[3,4,6,12][5,8,14]        */
/*[3,4,5,6,8,12,14]        */
/********************************/

void MergePass(dataType *ptrA, dataType *ptrB, int s)
{
    int i;
    for (i = 0; i <= arraySize - 2 * s; i += 2 * s){
        //合并大小为s 的相邻二段子数组
        Merge(ptrA, ptrB, i, i + s - 1, i + 2 * s - 1);
    }

    //剩下的元素个数小于2s
    if ((i + s) < arraySize)
        Merge(ptrA, ptrB, i, i + s - 1, arraySize - 1);
    else
        while(i != arraySize){
            ptrB[i] = ptrA[i];
            i++;
        }
}

void MergeSort(dataType *ptrA)
{
    dataType *ptrB = (dataType *)malloc(arraySize * sizeof(dataType));

    int i = 1;
    while(i < arraySize){
        MergePass(ptrA, ptrB, i); //合并到数组b
        i += i;
        MergePass(ptrB, ptrA, i); //合并到数组a
        i += i;
    }

    free(ptrB);
}
二分搜索的递归与非递归 C/C++ codebool binarySearch(vector<int>& a, int data, int low, int high, int& count){
    static bool flag=false;
    int middle=(low+high)/2;
    cout<<a[middle]<<" ";
    count++;
    if(low<=high){       
        if(data<a[middle])
            binarySearch(a, data, low,middle-1,count);
        else if(data>a[middle])
            binarySearch(a, data, middle+1,high, count);       
        else flag=true;
    }
    return flag;
}

bool binarySearch2(vector<int>& a, int data, int& count){
    int low=0, high=a.size()-1;
    int middle=(low+high)/2;
    while(low<=high){
        cout<<a[middle]<<" ";
        count++;
        if(data<a[middle])
            high=middle-1;
        else if(data>a[middle])
            low=middle+1;
        else return true;
        middle=(low+high)/2;
    }
    return false;
}

插入排序的递归与非递归 C/C++ codevoid insertionSort(vector<int>& a){
    for(int i=1;i<a.size();i++){
        int temp=a[i];
        int j;
        for(j=i-1; j>=0;j--){
            if(temp<a[j])
                a[j+1]=a[j];
            else break;
        }
        a[j+1]=temp;
    }
}
void insertionSort(int *a,int item,int size)
{
    if(size==0)
        a[0]=item;
    else
    {
        for(int i=size-1;i>=0;i--)
        {
            if(item<a[i])
                a[i+1]=a[i];
            else
                break;
        }
        a[i+1]=item;
        size--;
        insertionSort(a,a[size],size);
    }
}

问题】编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。斐波那契数列为:0、1、1、2、3、……,即:
              fib(0)=0;
              fib(1)=1;
              fib(n)=fib(n-1)+fib(n-2)        (当n>1时)。

# include <stdio.h>

long Fibonacci(long first, long second, long n );//递归的方法
long Fibonacci_(long first, long second, long n );//递推的方法

void main()
{    
    long a = 0, b = 1, c = 45;
    for(long i = 0; i <= c; i++)
    {
        printf("i=%ld.c=%ld,Fibonacci_=%ld\n", i,c, Fibonacci_(a, b, i));
    }
    for(long i = 0; i <= c; i++)
    {
        printf("i=%ld.c=%ld,Fibonacci=%ld\n", i,c, Fibonacci(a, b, i));
    }
    getchar();
}

long Fibonacci(long first, long second, long n)//递归的方法
{
    if(0 == n)
        return first;
    else if(1 == n)
        return second;
    else
    {
        return  Fibonacci(first,second,(n - 1))+Fibonacci(first,second,(n - 2));
    }
}

long Fibonacci_(long first, long second, long n )//递推的方法
{
    long a = 0, b = 1, c = 0;
    if(0 == n)
        return first;
    else if(1 == n)
        return second;
    else
    {
        for(long i = 0; i <= (n - 2); i++)
        {
            c = a +b;
            a = b;
            b = c;
        }
        return c;
    }
}

由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法 时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前 两项计算出下一项,直至计算出要求的第n项。 ==>你可以尝试运行一下查找一个数组中,相连元素(int型)之和最大的串 如:{6, 1, -9, 4, -3, 2, 8, -7, 5, 0}就是从4到8之和最大 三种算法O(N^3),O(N^2),O(N) C/C++ code#include<iostream>
#include<vector>
using namespace std;

int _sum(vector<int>& a, int& low, int& high){
    int conSum=0;
    for(int i=low; i<=high; i++){
        conSum+=a[i];
    }
    return conSum;
}

int maxContiguous1(vector<int>& a, int& low, int& high) {//O(N^3)
    int maxSum = 0;
    int sum=0;
    int _high=0;
    for (int i = 0; i < high ; i++) {
        for (int j = i + 1; j < high; j++) {
            if (_sum(a,i,j)> maxSum) {
                maxSum = _sum(a,i,j);
                low = i;
                _high = j;
            }
        }
    }
    high=_high;
    return maxSum;
}

int maxContiguous2(vector<int>& a, int& low, int& high) {//O(N^2)
    int maxSum = 0;
    int sum=0;
    int _high=0;
    for (int i = 0; i < high ; i++) {
        sum=a[i];
        for (int j = i + 1; j < high; j++) {
            sum+=a[j];
            if (sum> maxSum) {
                maxSum = sum;
                low = i;
                _high = j;
            }
        }
    }
    high=_high;
    return maxSum;
}

int maxContiguous3(vector<int>& a, int& low, int& high){//O(N)
    int maxSum = 0;
    int sum=0;
    int _high=0;
    for (int j=0,i = 0; i < high ; i++) {
        sum+=a[i];
        if (sum> maxSum) {
            maxSum = sum;
            low =j;
            _high = i;
        }
        else if(sum<0){
            j=i+1;
            sum=0;
        }
    }
    high=_high;
    return maxSum;
}

int main() {
    int b[] = {6, 1, -9, 4, -3, 2, 8, -7, 5, 0};
    vector<int> a(b, b + 10);
    int low = 0, high = a.size()-1;
    int maxSum = maxContiguous3(a, low, high);
    cout << "from a[" << low << "] to a[" << high << "] =" << maxSum;
    system("pause");

  评论这张
 
阅读(755)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017