学步园

#include "sort.h"
/*-----------------交换类排序------------------------------*/
//冒泡排序
bool BubbleSort(int arr[],int len)
{
	if (arr == NULL)
	{
		return false;
	}
	bool bDone = true;
	//一个标记，只有当元素交换进行后，bDone= true,如果遍历一遍，元素没有交换证明原数组已有序，则不用再进行下去
	for (int i = len-1; i > 0&& bDone; --i)
	{
		bDone = false;
		for (int j = 0; j < i; ++j)
		{
			if (arr[j] > arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				bDone = true;
			}
		}
	}
	return true;
}
//冒泡排序的改进版
/*
上面算法中，变量i只往前进一步
但有时候，这个序列后面部分连续几个已经都是有序的了，那么我们就不用在一个一个往前进了
EX：数组 arr[] = {1,3,2,6,7}只有3,2是无序的，当j = 1时进入交换，交换完毕后，至少从j到最后都是有序的了
所以只要我们记住交换位置j就可以省去一些过程
*/
bool BubbleSort2(int arr[],int len)
{
	if (arr == NULL)
	{
		return false;
	}
	bool bDone = true;
	int last = len;
	int i = len-1;
	while(i>0 && bDone)
	{ 
		bDone = false;
		for (int j = 0;j <i; ++j)
		{
			if (arr[j] >arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				bDone = true;
				last = j;//记住交换位置
			}
		}
		i = last;
	}
	return true;
}


//快速排序
/*
快速排序的思想就是通过选择一个关键字介于“中间”的元素快速将数组分成两部分，然后分别对这两部分进行排序
快排的事件复杂度为O(nlogn),当所选关键字介于数组最中间时效率最高
*/
int Sort(int arr[],int left,int right)
{
	if (arr == NULL)
	{
		return -1;
	}
	int temp = arr[left];
	int low = left,high = right;
	while (low < high)
	{
		while(low <high && arr[high]>= temp)
			high--;
		arr[low] = arr[high];
		while (low <high && arr[low] <= temp)
			low ++;
		arr[high] = arr[low];
	}
	arr[low] = temp;
	return low;
}
bool QSort(int arr[],int start,int end)
{
	if (arr == NULL)
	{
		return false;
	}
	int mid = 0;
	if(start <end)
	{
		mid = Sort(arr,start,end);
		if (mid == -1)
		{
			return false;
		}
		QSort(arr,0,mid-1);
		QSort(arr,mid+1,end);
	}
	return false;
}
/*------------------------------------选择类排序--------------------------------*/
//简单选择排序
/*如果前i-1都是有序的，在后面的元素中找到最小的元素与第i个进行交换，那么前i个都是有序的了*/
bool SelectSort(int arr[],int len)
{
	if (arr == NULL)
	{
		return false;
	}
	for (int i = 0; i<len-1; ++i)
	{
		int k = i;
		for (int j = i+1; j<len; ++j)
		{
			if (arr[j] <arr[k])
			{
				k = j;
			}
		}
		if (k!= i)
		{
			int temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
	return true;
}
//堆排

void AdjustHeap(int arr[],int root,int end)
{
	//调整为大根堆
	if (arr == NULL)
	{
		return;
	}
	int t=arr[root];
	int  i = root*2+1;
	while( i <= end)
	{
		if (i<end && arr[i]<arr[i+1])
		{
			i++;
		}
		if (arr[i] <= t)
		{//原根节点是最大元素不用调整
			break;
		}
		else
		{
			arr[(i-1)/2] = arr[i];//将元素上调
			i = i*2+1;//继续寻找原根元素的合适位置
		}
	}
	arr[(i-1)/2] = t;


}
bool HeapSort(int arr[],int len)
{
		if (arr == NULL)
		{
			return false;
		}

		for (int i = (len-1)/2; i>=0; --i)
		{
			AdjustHeap(arr,i,len);//建堆
		}
		for (int i = len; i>0; --i)
		{
			int temp = arr[0];//换元素
			arr[0] = arr[i];
			arr[i] = temp;
			AdjustHeap(arr,0,i-1);//重新调整堆
		}
		return true;

}
//归并排序
/*
先分而治之，然后再归并
*/
void Merge(int src[],int des[],int start,int mid,int end)
{
	int i = start,j = mid+1;
	int k = start;
	while(i <= mid && j<= end)
	{
		if (src[i]< src[j])
		{
			des[k++] = src[i++];
		}
		else
			des[k++] = src[j++];
	}
	while (i<= mid)
	{
		des[k++] = src[i++];
	}
	while( j <= end)
	{
		des[k++] = src[j++];
	}
}
void MergeSort(int src[],int des[],int start,int end)
{
	if (src == NULL || des == NULL)
	{
		return;
	}
		int len = (end-start)+1;
         int *p = new int[len];
		 memset(p,0,len);
		 if (start == end)
		 {
			 des[end] = src[end];
		 }
		 else
		 {
		        int mid = start + (end- start)/2;
				MergeSort(src,p,0,mid);
				MergeSort(src,p,mid+1,end);
				Merge(p,des,start,mid,end);
		 }
}
/*-----------------------------------插入排序-----------------------*/
//直接插入排序
/*
找到一个不合适（顺序不对）的数，然后往前寻找到他合适的位置，将前面的元素都往后挪直到找到他的位置，插入
正序效率最高，逆序效率最低  O(n^2)
*/
bool InsertSort(int arr[],int len)
{
	if (arr== NULL)
	{
		return false;
	}
      for(int i = 1; i<len; ++i)
	  {
		  if (arr[i] <arr[i-1])
		  {
			  int temp = arr[i];
			  int j = i-1;
			  for (; j>=0 && arr[j] >temp;--j)
			  {//寻找位置，并往后挪
				 arr[j+1] = arr[j];
			  }
			  arr[j+1] = temp;
		  }
	  }
	  return true;
}
//折半插入排序
/*
只有一点与直接插入不同：
直接插入排序在寻找合适位置时是一个一个查找，而折半插入在查找合适位置时使用二分查找的思想查找，所以在查找这里节省了时间
但是他只是在查找上节省时间，复杂度仍为O(n^2)
*/
bool HalfSort(int arr[],int len)
{
	if (arr == NULL)
	{
		return false;
	}

	for (int i = 1; i<len; ++i)
	{
		if (arr[i] <arr[i-1])
		{
			int temp = arr[i];
			int low = 0;
			int high = i;
			while(low <high)
			{
				int mid = low+ (high-low)/2;
			  if (arr[mid] <temp )
			  {
					low = mid+1;
			  }
			  else
				  high = mid-1;
			}
			int j = 0;
			for ( j= i-1; j>= low; --j)
			{
				arr[j+1] = arr[j];
			}
			arr[j+1] = temp;
		}
	}
	return true;
}
//希尔排序
/*
一次选取一个step,进行交换比较，每次缩短Step,直至Step=1，Step = 1的时候其实就是直接插入排序
Shell排序就是为了减小元素据其最终位置的距离，减小移动次数
*/
bool ShellSort(int arr[],int len,int step)
{
		if(arr == NULL)
		{
			return false;
		}
		while(step >=1)
		{
			for (int i = step; i<len;++i)
			{
				if (arr[i] <arr[i-step])
				{
					int temp = arr[i];
					int j = 0;
					for (j = i-step;j >=0 && arr[j] > temp; j-=step)
					{
						arr[j+step] = arr[j];
					}
					arr[j+step ] =temp;
				}

			}
			step /=2;
		}
	
}

以上排序，虽然简单，但是全是基础啊亲，笔试面试什么的一定要准备上

                                                                                                   【热爱工作，热爱生活】