常见的排序算法（插入、希尔、选择、堆、冒泡、快排、归并）

前言

排序在我们日常的生活中起到了非常大的作用，所以今天我们就来介绍一下常见的几种排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。

一、直接插入排序

1.1流程图演示

如图所示这里是要排升序，假设前【0~end】（这里指的是数组的下标）个数是有序的，插入排序就是将第end+1(这里指的是数组的下标)往前插入，如果end位置的这个数大于 end+1位置的这个数，那么就将end位置的值往后移（为了防止数据被覆盖的问题，所以要提前对end+1位置的值进行保存，具体代码实现等会会给），直到找到比我们刚开始end+1这个位置的值小的位置，然后我们就进行插入（这里看不懂的话可以结合下面的代码来看）。

代码实现：

//直接插入排序
void InsertSort(int* a, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];//提前保存end+1位置的数据
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;//将tmp的值赋给end+1的位置
	}
}

二、希尔排序

希尔排序这里我们分成两个步骤来进行排序：首先是预排序，其次是插入排序。预排序的目的就是让数据趋近于有序。

2.1流程图演示

希尔排序就是将数组分成几个组，每个数据之间相差gap个，上图所示的gap=3，因此分出了蓝、红、绿这几个组，然后分别对这几个组进行插入排序。（注意当gap=1时，就是插入排序），具体看下面的代码实现。

代码实现：

希尔排序
先预排序，再插入排序
void ShellSort(int* a, int size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
	}
	
	for (int j = 0; j < gap; j++)
	{
		for (int i = j; i < size - gap; i = i + gap)//防止越界，所以i
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

三、选择排序

3.1流程图演示

选择排序就是通过遍历这个数组去找最大值或最小值，如果你要排升序，那你每次就找最小值，降序每次就找最大值。
代码实现：

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//选择排序
void SelectSort(int* a, int size)
{
	for (int i = 0; i < size; i++)
	{
		int min = a[i];//假设一个最小值（这里排升序）
		int mini = i;//假设最小值的下标为i
		for (int j = i; j < size; j++)
		{
			if (a[j] < min)
			{
				min = a[j];
				mini=j;//这里记录比min小的值的下标
			}
		}
		Swap(&a[i], &a[mini]);//将最小值放在数组前面
	}
}

四、堆排序

堆排序就是利用堆的特性进行对数据的排序，对堆的知识点有点遗忘的可以翻看我前面的几篇的博客。
总体思路：就是首先堆数据进进行建堆处理，如果排升序，就建大堆；排降序，就建小堆。若对其不太理解，可以看（二叉树-堆）这篇博客。其次将堆顶的数据和堆低的数据进行交换（这样最大值或最小值就在最后一个位置了），交换后再进行一次向下调整算法；最后通过while循环就可以完成堆排序了。
代码实现：

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//堆排序
void HeapSort(int* a, int size)
{
	//首先进行建堆
	for (int i = (size - 1 - 1) / 2; i>=0; i--)
	{
		Adjustdown(a, size, i);
	}
	
	int end= size-1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);//交换数据
		Adjustdown(a, end, 0);//进行向下调算法
		end--;
	}
}

五、冒泡排序

5.1流程图演示

冒泡排序就是两两比较，只要不符合你的条件就交换，排完一趟之后最后一个值就是最大值或者最小值。
代码实现：

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

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

	}
}

六、快速排序

6.1 hoare版本流程图演示

大概的思路就是首先确定一个key,上图将下标为0的位置的值设置为key，然后右边找小（比key要小），找到之后，左边再找大（比key要大）；其次找到之后交换他们的位置，然后继续右边找小，左边找大。最后当他们相遇时就把key的值与他们交换的位置的值进行交换。最后得到的结果就是比key大的值在key右边，比key小的值在key左边。然后用递归的思路进行排序。

代码实现

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//三数取中函数
int Getmid(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[right] < a[left])
		{
			return right;
		}
		else
			return left;
	}
	else//a[left]> a[midi]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[right] > a[left])
		{
			return a[left];
		}
		else
			return right;
	}
}

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//三数取中
	int mid = Getmid(a, left, right);
	Swap(&a[left], &a[mid]);

	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		//右边找小
		while (begin<end && a[end]>=a[keyi])
		{
			end=end-1;
		}
		//左边找大
		while (begin < end && a[begin] <= a[keyi])
		{
			begin=begin+1;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], &a[end]);
	//[ left  keyi-1]  keyi  [ keyi+1  right ]
	
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

这里用了一个三数取中，这个三数取中的作用就是假如你要排升序，但是数据是降序，这就导致代码的运行效率非常低，运用这个三数取中可以不断的调整key，这样就有效避免了一些特殊情况。

6.2 前后指针法流程图演示

这个的方法和上面的hoare版本一样也是先确定一个key，然后定义一个prev指向key的位置，再定义一个cur指向prev的下一个位置。之后呢cur先去找比key位置小的值，找到之后prev往前+1，然年交换他们俩位置的值，如果他们指向的是一个同样的值，那就可以不用交换（其实交换也没事）。然后一直循环，cur找小；prev找大，直到cur指向的位置越界了，这时就交换key和prev位置的值。然后也是用递归的方法进行排序。

代码实现：

//交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//快速排序前后指针
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;


	int keyi =left;

	int prev =left;
	int cur =prev+1;
	while (cur <=right)
	{
		if (a[cur] < a[keyi]&&prev!=cur)
		{
			prev++;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
		
	}
	Swap(&a[keyi], &a[prev]);
	
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);

}

七、快速排序非递归法

快速排序非递归这里要借助栈来实现，每次入栈和出栈都是一个区间，然后借助前面的hoare版本或者前后指针版本进行排序。

代码实现：

/快速排序前后指针
int QuickSort(int* a, int left, int right)
{
	
	int keyi =left;

	int prev =left;
	int cur =prev+1;
	while (cur <=right)
	{
		if (a[cur] < a[keyi]&&prev!=cur)
		{
			prev++;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;

}


//快速排序非递归法
void QuickSortNoR(int *a,int left,int right)
{
	ST p;
	STInit(&p);
	//将右左区间入栈
	STpush(&p, right);
	STpush(&p, left);

	while (!IsEmpty(&p))
	{
		int begin = STtop(&p);
		STPop(&p);
		int end = STtop(&p);
		STPop(&p);

		int keyi = QuickSort(a, begin, end);//这里借助前后指针法来排序
		//begin  keyi-1 keyi keyi+1,end
		if (keyi +1 < end)
		{
			STpush(&p, end);
			STpush(&p, keyi+1);
		}
		if (begin<keyi-1)
		{
			STpush(&p, keyi-1);
			STpush(&p,begin);
		}
	}
}

八、归并排序

归并排序就是将一个数组进行不断的分成两组，分完之后依次对这两组的每个数据进行比较，小的值放在创建的另外的一个tmp数组里面。

8.1代码实现

void _MergeSort1(int* a, int* tmp, int begin, int end)
{
	if (begin>=end)//递归结束条件
	{
		return;
	}
	int mid = (begin + end) / 2;
	//这时分成了[begin  mid]和[mid+1  end]两组

	_MergeSort1(a, tmp, begin, mid);
	_MergeSort1(a, tmp, mid + 1, end);

	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] >= a[begin2])
		{
			tmp[i] = a[begin2];
			i++;
			begin2++;
		}
		if (a[begin1] < a[begin2])
		{
			tmp[i] = a[begin1];
			i++;
			begin1++;
		}
	}

	while(begin1<=end1)
	{
		tmp[i] = a[begin1];
		i++;
		begin1++;
	}
	while(begin2<=end2)
	{
		tmp[i] = a[begin2];
		i++;
		begin2++;
	}

	memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}

//归并排序
void MergeSort1(int *a,int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);//创建一个tmp数组
	
	_MergeSort1(a, tmp, 0, size - 1);
    free(tmp);
    tmp=NULL;


}

归并排序非递归：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	// gap每组归并数据的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 第二组都越界不存在，这一组就不需要归并
			if (begin2 >= n)
				break;

			// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
			if (end2 >= n)
				end2 = n - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}

		printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}