MOOC学习----数据结构 第一讲

算法概念:

   # 一个有限指令集

   #接受一些输入（有些情况下不需要输入）

   #产生输出

   #一定在有限步骤之后终止

   #每一条指令必须

      #有充分明确的目标，不可以有歧义

      #计算机能处理的范围之内

      #描述应不依赖于任何一种计算机语言以及具体的实现手段

如下选择排顺序描述：

     

void SelectionSort (int List[], int N )
{
      /*将N个整数List[0]。。。List[N-1]进行非递减排序 */
      for (i=0; i<N; i++) {
      Minposition = ScanForMin(List, i ,N-1);
      /*从List[]到L实体【n-1]中找最小元，并将其位置赋值给MiniPosition*/
      Swap( List[i],List[MinPosition] );
      /*将未排序部分最小值换到有序部分的最后位置*/

      }
}

 

 

前面讲述的是算法的基础，下面将解决最大子列和问题：

问题描述：给定N个整数的序列{A1,A2,A3,....,An},求函数 f( i , j ) = max{第 i 到 j 的序列和} 的最大值。

#include<stdio.h>
#include<stdlib.h>
/*-----------------------------
---------最大子列和问题--------
--- 给定N个整数的序列{A1,A2,A3,....,An},
--- 求函数 f( i , j ) = max{第 i 到 j 的序列和} 
--- 的最大值。


如:[1,2,4,5,-2,4,5,2,1,9,0,3]

-------------------------------*/

//算法一书暴力算法，每次需要重头算起,时间复杂度O(N^3)
int MaxSubseqSum1(int A[],int N) 
{
	int ThisSum,MaxSum=0;
	int i, j, k;
	for( i = 0; i < N; i++ ) {/*i是子列左端位置*/
		for( j = i; j < N; j++ ){/* j 是子右端的位置*/
			ThisSum=0;	/* ThisSum是从A[i]到A[j]的子列和*/
			for( k = i; k <= j; k++ ) {
				ThisSum += A[k];
				if( ThisSum > MaxSum )	/*如果当前子列和大于已记录的最大子列和则更新记录*/
					MaxSum = ThisSum;
			}
		}
	}
	return MaxSum;
}
//利用上次算出的i到j的值，直接加上当前值即可，时间复杂度O(N^2)
int MaxSubseqSum2(int A[],int N) 
{
	int ThisSum,MaxSum=0;
	int i,j;
	for( i = 0; i < N; i++ ) {/*i是子列左端位置*/
		ThisSum=0;	/* ThisSum是从A[i]到A[j]的子列和*/
		for( j = i; j < N; j++ ){/* j 是子右端的位置*/
			ThisSum += A[j];
			if( ThisSum > MaxSum )	/*如果当前子列和大于已记录的最大子列和则更新记录*/
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}


//分而治之
int MaxSubseqSum3(int A[],int N) {
	int ThisSum=0,MaxSum=0;
	int i;
	for( i = 0; i < N; i++) {
		ThisSum += A[i];
		if( ThisSum > MaxSum ) 
			MaxSum = ThisSum;
		else if( ThisSum < 0 ) 
			ThisSum = 0;
	}
	return MaxSum;
}

int main(){
	int N,A[100000];
	int i,t;
	//输入数组长度
	scanf("%d",&N);
	//输入数据
	if( N <= 0 || N > 100000) {
		printf("Input Array Length Invalid \n ");
		exit(0);
	}
	for(i = 0; i < N ; i++ ){
		scanf("%d",&A[i]);
	}
	printf("%d",MaxSubseqSum3(A,N));
	return 0;
}