排序算法和二分查找

using namespace std;
#include "stdafx.h"
#include <iostream>
void myswap(int A[], int i, int j){
	int temp;
	temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}
//插入
void inssort(int A[], int n){
	for(int i = 1; i < n; i++)
		for(int j = i; j > 0; j--)
		{
			if(A[j] < A[j-1])
				myswap(A,j,j-1);

		}
}
void bubsort(int A[], int n){
	for(int i = 0; i < n-1; i++)
		for(int j = n-1; j > 0; j--){
			if(A[j] < A[j-1])
				myswap(A,j,j-1);
		}
}
void selsort(int A[], int n){
	for(int i=0; i<n-1; i++)
	{	
		int lowindex = i;
		for(int j = n-1; j > i; j--){
			if(A[j] < A[lowindex]){
				lowindex = j;
			}
		}
		myswap(A,i,lowindex);
	}
}

/////////////////
int find(char * a,char aim)
{
	int end = strlen(a) - 1;
	int start = 0;
	while( start <= end)//是<=,可能只有一个元素
	{
		int middle = (start + end)/2;
		if((a[middle] - aim) == 0)
		{
			return middle;
		}
		else if((a[middle] - aim) > 0)
		{
			end = middle - 1;//必须减1，否则可能死循环
		}
		else
		{
			start = middle + 1;//必须减1
		}
	}
	return -1;
}
二分查找，
//////////////////////
void print(int A[],int n){
	for(int i = 0 ; i < n; i++){
	
		printf("%d\n",A[i]);
	//	p++;
	//	count++;
	}
	//printf("count is %d\n",count);
}
//增量为incr的插入排序
void inssort2(int A[],int n, int incr){
	for(int i = incr; i < n; i += incr)
		for(int j = i; j >= incr; j-= incr)
		{
			if(A[j] < A[j-incr])
				myswap(A,j,j-incr);
		}
}
//
void shellsort(int A[], int n){
	for(int i = n/2; i > 2; i/=2)
		for(int j = 0; j < i; j++)
			inssort2(&A[j],n-j,i);
	inssort2(A,n,1);
}
//
void mergesort(int A[], int temp[], int left, int right){
	int mid = (left + right)/2;
	if(left == right) return;
	mergesort(A,temp,left,mid);
	mergesort(A,temp,mid+1,right);
	for(int i=left; i <= right; i++)
		temp[i] = A[i];
	//do the merge operation back to A
	int i1 = left; int i2 = mid +1;
	for(int curr=left; curr<=right; curr++){
		if(i1 == mid + 1)//left sublist exhausted
			A[curr] = temp[i2++];
		else if(i2 > right)		//right sublist exhausted
			A[curr] = temp[i1++];
		else if(temp[i1] < temp[i2])
			A[curr] = temp[i1++];
		else A[curr] = temp[i2++];
	}

}

int main(int argc, char* argv[])
{
	int a[5] = {3,2,1,4,5};
	int b[5] = {3,2,1,4,5};
	int c[5] = {3,2,1,4,5};
	int temp[5];
	inssort(a,5);
	printf("Hello World!\n");
	print(a,5);
	printf("bubsort:\n");
	bubsort(b,5);
	print(b,5);
	printf("shellsort:\n");
	//shellsort(c,5);
	mergesort(c,temp,0,4);
	print(c,5);
	//

	return 0;
}