学习数据结构基础，如有错误，请指正。

/***********************************************
【查找和排序】 几种常见的查找和排序算法
***********************************************/
#include <iostream>

// 顺序查找
int squ_search(int array[],int count,int elem)
{
	for (int i=0;i<count;++i)
	{
		if (array[i] == elem)
		{
			return i;
		}
	}
	return -1;
}

// 折半查找（array已经基本有序数据）
int bin_search(int array[],int elem)
{
	int low = 0;
	int high = count -1;
	int mid = count/2;

	while(low <= high)
	{
		mid = (high+low)/2;
		if (array[mid] == elem)
		{
			return mid;
		}
		else if (array[mid]>elem)
		{
			high = mid-1;
		}
		else
		{
			low = mid+1;
		}
	}
	return -1;
}

//直接插入排序  小->大
void insert_sort(int *array,int count)
{
	int i,j,tmp_elem;
	for (int i=1;i<count;++i)
	{
		tmp_elem = array[i];
		j = i-1;
		while(j>0 && tmp_elem<array[j])
		{
			array[j+1] = array[j];
			--j;
		}
	}
}

// 选择排序 小->大
void select_sort(int *array,int count)
{
	int tmp_index;
	for (int i=0;i<count;++i)
	{
		tmp_index = i;
		for (int j=i+1;j<count;++j)
		{
			if (array[j]<array[tmp_index])
			{
				tmp_index = j;
			}
		}
		if (tmp_index != i)
		{
			int tmp_elem = array[i];
			array[i] = array[tmp_index];
			array[tmp_index] = tmp_elem;
		}
	}
}

// 冒泡排序 小->大
void bubble_sort(int *array,int count)
{
	int tmp_elem;
	for(int i=1;i<count;++i)
	{
		for (int j=0;j<=count-i;++j)
		{
			if(array[j]>array[j+1])
			{
				tmp_elem = array[j];
				array[j] = array[j+1];
				array[j+1] = tmp_elem;	
			}
		}
	}
}

// 希尔排序 小->大
void shell_sort(int *array,int count)
{
	int gap = count;
	int j;
	int tmp_elem;

	while(gap>1)
	{
		gap = gap/2;

		//bubble sort
		for (int i=0;i<count-gap;++i)
		{
			j = i + gap;
			if (array[j]>array[i])
			{
				tmp_elem = array[i];
				array[i] = array[j];
				array[j] = tmp_elem;
			}
		}
	}
}

// 快速排序 小->大
void quick_sort(int *array,int s,int t)
{
	int i,j;
	if (s<t)
	{
		i = s;
		j = t +1;
		while (true)
		{
			do 
			{
				++i;
			} while ( !(array[s]<=array[i] || i==t) );
			do 
			{
				--j;
			} while ( !(array[s]>=array[j] || j==s) );

			if (i<j)
			{
				int tmp_elem = array[i];
				array[i] = array[j];
				array[j] = tmp_elem;
			}
			else
			{
				break;
			}
		}

		int tmp_elem = array[s];
		array[s] = array[j];
		array[j] = tmp_elem;

		quick_sort(array,s,j-1);
		quick_sort(array,j+1,t);
	}

}