七大排序算法

排序分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里的八大排序就是内部排序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

冒泡排序

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

//冒泡排序
void BubbleSort(int *array,int size)
{
	int flag = 1;
	for (int i = 0; i < size; i++)
	{
		flag = 0;
		for (int j = i+1; j < size; j++)
		{
			if (array[i]>array[j])
			{
				Swap(&array[i],&array[j]);
			}
		}

		if (flag == 1)
		{
			break;
		}
	}
}

选择排序

单向选择排序

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推…..

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

//选择排序
void SelectSort(int *array,int size)
{
	int min;
	for (int i = 0; i < size; i++)
	{
		min = i;
		for (int j = i; j < size; j++)
		{
			if (array[j] < array[min])
			{
				min = j;
			}
		}
		if (i != min)
		{
			Swap(&array[min],&array[i]);
		}
	}
}

双向选择排序

基本思路
与单向选择排序一样，在从头部开始排序的同时，我们让其从末端也进行排序，当前后前后两个下标索引相遇就停止，具体代码如下：

//双向选择排序
void SelectSort(int arr[],int size)
{
	int minSpace = 0; 
	int maxSpace = size - 1;

	while (minSpace < maxSpace)
	{
		int minPos = minSpace;
		int maxPos = minSpace;

		for (int i = minSpace +1; i <= maxSpace; i++)
		{
			if (arr[i] > arr[maxPos])
			{
				maxPos = i;
			}
			if (arr[i] < arr[minPos])
			{
				minPos = i;
			}

		}

		Swap(arr + minSpace,arr + minPos);

		if (minSpace == maxPos)
		{
			maxPos = minPos;
		}
		Swap(arr + maxSpace,arr + maxPos);
		minSpace++;
		maxSpace--;
	}
}

插入排序:

基本思想
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

//直接插入排序
void InsertSort(int *array, int size)
{
	int temp,i,j;
	for (i = 1; i < size; i++)
	{
		temp = array[i];//取出一个未排序的数
		for (j = i-1; j >= 0 ;j--) //在排序序列中查找位置
		{
			if(temp<array[j])
			{
				array[j + 1] = array[j]; // 向后移动数据
			}
			else
			{
				break;
			}
		}
		array[j+1] = temp;  //将数据插入
	}
}

//优化后的插入排序--折半插入排序
void BinaryInsertSort(int *array,int size)
{
	int i, j, left, right, mid;
	int key;
	for (i = 1; i<size;i++)
	{
		key = array[i];
		left = 0;
		right = i - 1;

		while (left <= right)
		{
			mid = left + (right - left);
			if (array[mid]<= key)
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}

		for (j = i; j>left; j--)
		{
			array[j] = array[j - 1];
		}
		array[left] = key;
	}
}

希尔排序

//希尔排序
void ShellSort(int *arr,int size)
{
	int d, i, j, x;
	d = size / 2;
	while(d>=1)  //循环至增量为1时结束
	{
		for ( i = d; i < size; i++)
		{
			x = arr[i];  //获取序列中的下一个数据
			j = i - d;	// 序列中前一个数据的序号
			while (j >= 0&&arr[j]>x) // 下一个数大于前一个数
			{
				arr[j + d] = arr[j];  //将后一个数向前移动
				j = j - d;			//修改序号，继续向前比较
			}
			arr[j + d] = x;  //保存数据
		}
		d /= 2;  //缩小增量
	}
}

堆排序

堆排序:树形选择排序，将带排序记录看成完整的二叉树，第一步：建立初堆，第二步：调整堆

方案一：降序排序，建立小堆

//第二步：调整堆
void HeapAdjust(int arr[], int s, int n)
{
	//调整为小根堆，从小到大
	int rc = arr[s];
	for (int j = 2 * s; j <= n; j *= 2)
	{
		if (j<n && arr[j]>arr[j + 1])//判断左右子数大小
			j++;
		if (rc <= arr[j])
			break;
		arr[s] = arr[j];
		s = j;
	}
	arr[s] = rc;
}
//第一步：建初堆
void CreatHeap(int arr[], int n)
{
	//小根堆
	for (int i = n / 2; i > 0; i--)
		HeapAdjust(arr, i, n);
}
//整合
void HeapSort(int arr[], int n)
{
	CreatHeap(arr, n);//第一步，建立初堆
	for (int i = n; i > 1; i--)
	{
		int x = arr[1];//堆顶与最后一个元素互换
		arr[1] = arr[i];
		arr[i] = x;
		HeapAdjust(arr, 1, i - 1);
	}
}

方案二：升序排序，建立大堆

void AdjustDown(int arr[], int size, int root)
{
	int left = 0;
	int	right = 0;;
	int maxChild = 0;

	while (1)
	{
		left = 2 * root + 1;
		right = 2 * root + 2;
		//判断左孩子是否越界
		if (left >= size)
		{
			return;
		}
		//判断左右孩子谁是最大的
		maxChild = left;   //假设是左孩子
		if (right <size && arr[right] > arr[left])
		{
			maxChild = right;
		}

		//判断最大的是不是在根处，不是的话进行交换
		if (arr[root] >= arr[maxChild])
		{  //判断是否满足大堆性质
			return;
		}
		Swap(&arr[root],&arr[maxChild]);

		root = maxChild;

	}
}

void HeapSort(int arr[],int size)
{
	//建立初堆
	for (int i = (size - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);
	}

	for (int j = 0; j < size - 1; j++)
	{
		Swap(&arr[0],&arr[size-j-1]);
		AdjustDown(arr,size-j-1,0);
	}
}

归并排序

思路：利用递归的方法递归划分一个无序数组，直到每个数组只有一个元素时，对相邻的两个数组进行归并。

递归写法

//归并排序

//第三步：合并两个有序数组为一个数组
void _MergeArray(int arr[], int begin, int mid, int end, int* tmp)
{
	int cur1 = begin;
	int cur2 = mid;
	int index = 0;

	while (cur1 < mid && cur2 < end)
	{
		if (arr[cur1] < arr[cur2])
		{
			tmp[index] = arr[cur1];
			index++;
			cur1++;
		}
		else
		{
			tmp[index] = arr[cur2];
			index++;
			cur2++;
		}
	}
	//当cur1指向的数组元素都比较完后，cur2指向的数组还有元素时，将cur2指向的全部元素拷贝到tmp中
	while (cur1 < mid)
	{
		tmp[index++] = arr[cur1++];
	}

	while (cur2 < end)
	{
		tmp[index++] = arr[cur2++];
	}
	
	//最后将tmp中的元素全部拷贝到原来的数组中
	memcpy(arr + begin, tmp, sizeof(int)*index);
}

//对无序数组进行划分为只有一个元素的数组后再对数组进行归并
void _MergeSort(int arr[],int begin,int end,int *tmp)
{
	if (end - begin <= 1)
	{
		return;
	}

	int mid = begin + (end - begin) / 2;

	_MergeSort(arr,begin,mid,tmp);
	_MergeSort(arr, mid, end, tmp);
	_MergeArray(arr,begin,mid,end,tmp);
}


void MergeSort(int arr[], int size)
{
	if (size <= 1)
	{
		return;
	}

	int *tmp = (int *)malloc(sizeof(int)*size);
	_MergeSort(arr, 0, size, tmp);
	free(tmp);

}

非递归写法

void MergeSort(int arr[],int size)
{
	if (size <= 1)
	{
		return;
	}

	int *tmp = (int*)malloc(sizeof(int)*size);

	int gap = 1;
	for (; gap < size; gap*=2)
	{
		int i = 0;
		for (;i < size; i +=2* gap)
		{
			int begin = i;
			int mid = gap + i;
			if (mid > size)
			{
				mid = size;
			}

			int end = i + 2 * gap;
			if (end > size)
			{
				end = size;
			}

			_MergeArray(arr,begin,mid,end,tmp);
		}
	}
}

快速排序

方法一：左右指针法

//左右指针法，选的基准值放在最右边
int Partion(int arr[],int left,int right)
{
	int pivot = arr[right];
	int begin = left;
	int end = right;

	while (begin < end)
	{

		while (begin < end &&arr[begin] <= pivot)
		{
			begin++;
		}
		while (begin < end &&arr[end] >= pivot)
		{ 
			end--;
		}

		if (begin == end)
		{
			break;
		}

		Swap(arr + begin,arr + end);
	}
	Swap(arr + begin, arr + right);

	return begin;
}

方法二：挖坑法

//挖坑法
int Partion2(int arr[], int left, int right)
{
	int pivot = arr[right];
	int begin = left;
	int end = right;

	while (begin < end)
	{

		while (begin < end && arr[begin] <= pivot)
		{
			begin++;
		}
		if (begin == end)
		{
			break;
		}
		arr[end] = arr[begin];
 
		while (begin < end && arr[end] >= pivot)
		{
			end--;
		}

		arr[begin] = arr[end];
	}
	arr[begin] = pivot;

	return begin;
}

方法三：前后指针法

//前后指针法
int Partion3(int arr[],int left,int right)
{
	int pivot = arr[right];
	int part = left;
	for (int cur = left; cur <= right; cur++)
	{
		if (arr[cur] < pivot)
		{
			Swap(arr + cur, arr + part);
			part++;
		}
	}

	Swap(arr + right, arr + part);

	return part;
}

快速排序

void _QuickSort(int arr[],int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int pivot = arr[right];  //选取最右边的一个作为基准值
	int part = Partion3(arr,left,right);
	_QuickSort(arr,left,part-1);
	_QuickSort(arr,part+1,right);
}

void QuickSort(int arr[],int size)
{
	_QuickSort(arr, 0, size - 1);
}