[数据结构与算法]八大排序详述

带你深入理解八大排序思想，代码以及思路，我们要做的不是背代码，而是理解思路，从而用代码实现思路；

一、冒泡排序

这个排序算法的时间复杂的是O(N^2)，效率是比较低的，只不过好理解就是了；思路就是前面一个数据跟后面一个数据比较，要是排升序的话，前面的数大于后面，就交换，等排完一遍后，就把最大的数排到最后了，然后最大的数也就是最后一个数就不参与排了，因为排好了，就这样一个一个排，直到排到最后剩下一个数就不用排了，全部就排好了；

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

二、直接选择排序

思路也很简单，，时间复杂度也是O(N^2)；这个排序可以说是八大排序最差的排序了，除了计数排序要特定条件，计数排序是挺牛的，不过要指定条件下才好发挥；遍历一遍，选出最大或者最小的数放到最右或者最左边，一个一个排；

// 选择排序
void SelectSort(int* a, int n) {
	assert(a);
	int left=0,right=n-1;
	while (left < right) {
		int mini = left, maxi = left;
		int i = 0;
		for (i = left; i <= right; ++i) {
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > maxi)
				maxi = i;
		}
		Swap(&a[left], &a[mini]);
		if (maxi == left)//要是最大数就是最左边的情况
			maxi = mini;
		Swap(&a[maxi], &a[right]);
		--right;
		++left;
	}
	SortPrint(a, n);
}

三. 插入排序

思路也比较简单，最坏情况时间复杂度是O(N^2)，最好情况时间复杂度是O(N)；思路是：最后一个数，和前面的数一一比较，要是前面的数比要排的数大，就把这个数往后移一位，直到遇到相等的，放到这个数后面就行了，前提是前面的数都要已经排好了，所以我们要从第二个开始用插入排序开始排；还有就是前面的数都比要排的数小（大），那么这里一定要设置好，不要越界了；

// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; ++i) {
		int end = i;
		int temp = a[end + 1];
		while (end >= 0) {
			if (a[end] > temp) {
				a[end + 1] = a[end];
				--end;
			}
			else
				break;
		}
		a[end + 1] = temp;
	}
	
	//SortPrint(a, n);
}

四. 希尔排序

1. 这个排序是基于插入排序上该的排序；首先进行预排序，预排序的作用是将数据先排得有序些，就能提高最后用插入排序的效率；
2. 预排序的思想是分成gap组，每组数据大小是n/gap个左右，然后每个数据相隔gap大小，而插入排序就是gap等于1的预排序；gap根据数据的量而变化，数据越多gap越大，最后gap等于1的时候就是插入排序了，这个时候的数据已经接近有序了，所以最后的插入排序应该看成最好的情况来看；
3. 时间复杂度没有固定的说法，大家比较接受的是O(N^1.3)，因为gap是变化的，然后每一遍排序的时候因为预排序的原因让数据一次次变好，所以不能把每一遍排序按照最坏情况计算；

// 希尔排序
void ShellSort(int* a, int n) {
	assert(a);
	int gap=n;
	while (gap > 1) {
		//gap /= 2;
		gap = gap / 3 + 1;//要让最后一次gap等于1，就是插入排序了，省得还要再写插入排序；
		int i = 0;
		for (i = 0; i < n - gap; ++i) {//
			int end = i;
			int temp = a[end + gap];
			while (end >= 0) {
				if (a[end] > temp) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
	
}

五. 堆排序

1. 堆排序先要了解堆，这里小小的介绍一下，是用数组来存数据的，具体怎么存我们不用管，只需要排序就行了；我们的堆是一个二叉树，父亲的节点和孩子的节点的下标有如下特点：parents=(child-1)/2; child=parents*2+1;
2. 然后有大堆和小堆的概念，大堆就是二叉树所有节点都满足父节点的值都大于或者等于子节点的数值；记得是所有节点都满足；小堆则相反；
3. 好了，需要堆详细的知识点的还请自行查阅，我这里就不多介绍了，堆排序首先要进行建堆，建堆要先了解一下向下调整算法；就是将给定的下标订为最大根节点，也就是父节点，要开始向下和子树进行比较，要是排小堆和话，最上面的不应该就是最小的数吗？所以从最上面开始与子树比较，和较小的子树比较，要是父节点数值比较小的子树的数值大，就进行交换，然后再让交换后到子树位置的节点和它自身的子树再次比较，直到比子树都小或者相等停止调整；
4. 建堆就是从最后一个非叶子节点开始进行向下调整算法，然后进行倒数第二个非叶子节点又进行向下调整算法，直到最上面的祖节点搞完向下调整算法后，建堆就完成了，就建成大堆或者小堆了；
5. 要是排升序，就要建大堆，因为祖节点的值就是最大数了，和最后一个数交换后，不管最后一个数（现在是最大的数了），然后除了祖节点，其它节点都还保持了大堆的特性，只需要向下调整算法又找到次大的数了，重复如此，就可以排好数了，要是建小堆，只能得到最小值，要找次小的值就会打乱建好的堆，要找次小的数就要再次建堆，效率低；建堆消耗O(N),再向下调整就要消耗O(logN)；所以总的时间复杂度是O(NlogN)；

void Swap(int* e1, int* e2) {
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
// 堆排序
void AdjustDown(int* a, int n, int root) {
	assert(a);//建的现在是大堆
	int child = root * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[child] > a[root]) {
			Swap(&a[child], &a[root]);
			root = child;
			child = root * 2 + 1;
		}
		else
			break;
	}
}
void HeapSort(int* a, int n) {
	assert(a);
	//建堆
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; --i) {
		AdjustDown(a, n, i);
	}
	//排序
	int j = 0;
	for (j = 1; j < n; ++j) {
		Swap(&a[0], &a[n - j]);
		AdjustDown(a, n - j, 0);
	}
	//SortPrint(a, n);
}

六. 快排序

敢叫快排，那么一定效率高了，不然也不好意思叫快排了；时间复杂度是O(NlogN)；首先快排的思想是找最左边或者最右边的下标做keyi，然后有三种方法；

1. hoare法（左右下标法）
   两个指针，左下标是最左边，右下标是最右边，然后右边开始走（最左边做keyi），直到找到比key还小的数停下来，然后左下标向右走，找比数组下标为keyi的数值大的数，注意两个下标找的时候都要控制不要让左边下标大于右边下标了，所以一定要注意！！！找到两个数后，就交换，把小的换到左边，大的换到右边了；
   直到两个下标相等，然后和下标是keyi的数位置交换，然后原来是最左边的数就排到指定位置了，因为前面的数全部比它小，后面全部比它大，所以它的位置就排好了；
2. 挖坑法
   取最左边做坑，先用一个变量temp保存最左边的值，然后从最右边开始找比temp小的数，然后往坑里填，直接让下标为坑的数等于这个找到的小的数，然后找到的小的位置下标变成新的坑，然后再从左边开始找，重复，直到左右下标相等，相等位置也肯定是坑，因为一次只能走一边，然后把temp和坑的值交换，然后最后坑的数值已经排好了；
3. 前后下标法；
   这个也是用临时变量temp保存最左值下标，两个变量记录走的下标，prev从最左边开始，cur从第二个开始，cur下标一直向右走，直到找到比最左边数小的值，就让prev走一步，然后两个下标位置进行交换，要是prev走一步和cur相等可以跳过不交换哦；就这样重复，直到cur走出右边界停止，然后prev位置就和最左边的值交换位置，然后最左边的值就排好位置了；

上面三个方法只是排好一个位置的方法，然后我们利用递归，排好一个位置，左边，右边不是两段区间吗？再将这两段区间又开始排最右边的值，然后再分割区间，直到只剩下一个值的区间，或者不存在的区间（左边界大于右边界），就不用再分割了，一个或者没有区间说明排好了的区间；
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}

这里有点问题，因为当要排的数据是顺序或者很接近顺序，则排出来的时间复杂度是O(N^2)，因为顺序的时候，最左边的数排一下还在原位置，然后分割出来的左区间是没有的，有区间是N-1个数据，然后这样一直分割一直排，每次左区间没有，右区间少一个，要排N个，所以是 N ^2的时间复杂度；这样效率就低了下来，这个时候我们就采取了三数取中的方法；
就是把每次要排的区间传过来，然后取左右区间下标的中间值，看数组中最左边，最右边，和中间值下标所代表的三个值（不是比较下标的值，而是数组元素值）中间元素，找到中间值后返回对应下标作为key进行排；
第二个问题就是递归的最后三层函数栈帧占全部栈帧的85%左右，非常大，所以我们可以将递归到最后三层左右的递归排可以直接自己用插入排序排比较合适；

// 快速排序递归实现
// 三数取中

int Getmid(int* a,int left,int right) {
	assert(a);
	int mid = left + (right - left) / 2;
	if (a[left] > a[mid]) {
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
	else {//a[left]<=a[mid]
		if (a[mid] < a[right])
			return mid;
		else if (a[right] < a[left])
			return left;
		else
			return right;

	}
}
// 快速排序hoare版本
int PartSort1(int* a, int left, int right) {
	assert(a);
	int mid = Getmid(a, left, right);
	Swap(&a[mid], &a[left]);
	int keyi = left;
	while (left < right) {
		while (left<right && a[right]>=a[keyi])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		if (left < right)
			Swap(&a[right], &a[left]);
	}
	int meeti = right;
	Swap(&a[keyi], &a[meeti]);
	return meeti;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right) {
	assert(a);
	int mid = Getmid(a, left, right);
	Swap(&a[mid], &a[left]);
	int key = a[left];
	int hole = left;
	while (left<right) {
		while (left<right && a[right]>=key)
			right--;
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
			left++;
		a[hole] = a[left];
		hole = left;

	}
	a[hole] = key;
	return hole;

}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right) {
	assert(a);
	int mid = Getmid(a, left, right);
	Swap(&a[mid], &a[left]);
	int keyi = left;
	int prev = left, next = left + 1;
	while (next <= right) {
		if (a[next] < a[keyi] && ++prev != next) {
			Swap(&a[prev], &a[next]);
		}
		++next;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSort(int* a, int left, int right) {
	assert(a);
	if (left >= right)
		return;
	if (right-left<=10) {
		InsertSort(a + left, right - left + 1);
	}
	else {
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	

}

快排的非递归：校招的话是要求掌握非递归的，而且非递归没有栈溢出的风险；
递归变非递归有两种方法，第一个是用循环模拟，当然，只有比较简单的递归才能用循环模拟，复杂一点的要用数据结构的栈或者队列去模拟了；这里就要用栈来模拟；
思路：
用栈模拟的时候看递归用什么参数，用什么变量进行递归的，观察好了再考虑非递归怎么用，我们知道递归是把区间一直分然后排一个数据，然后再分，反复如此，利用的就是区间，所以我们用非递归也用区间进行；栈的特点是先进后出，开始压最大的区间，然后取出left和right分别保存，然后都pop一下，把left和right这个区间随便用三种方法排序中的一种方法排，得到两个区间，然后再入两个区间，再去一个区间，pop，再排，得到两个区间…这里要注意的是，先压的是右区间，后压左区间，取出来的先是左区间，后才是右区间，然后是先压右边的一个区间（排序一遍后得到两段区间），然后把左边的一段区间再压，这样就保证了先排左边，再排右边，和递归一样；直到left>=right就不压区间或者continue，只是用continue更像递归；

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {
	assert(a);
	Stack st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st)) {
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		if (begin >= end)
			continue;
		int keyi = PartSort1(a, begin,end);
		StackPush(&st, end);
		StackPush(&st, keyi+1);
		StackPush(&st, keyi-1);
		StackPush(&st, begin);

	}
	StackDestroy(&st);
	
}

七. 归并排序

思想：
开一个一样大的临时数组，把原数组数据分成两部分区间，前提是两部分区间数据都是排好序的，然后比较两个区间的数据大小然后放到临时数组里，使临时数组里的数都有序，将两个区间里的数都放进去后，把临时数组里排好了的数都拷贝会原数组里，原数组里的数值就都排好了；要左右两部分区间里的数都排好，这样把其中左部分区间先排好，也是用这样的方法，一直分，直到只有一个数或者没有区间就排好了，然后放进临时数组，再拷回去；这就要用递归分治了；

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void _MergeSort(int* a, int left, int right, int* temp) {
	assert(a && temp);
	if (left >= right)
		return;
	int mid = left + (right - left)/2;
	_MergeSort(a, left, mid, temp);
	_MergeSort(a, mid+1, right, temp);
	int falg = left;//开始归并排序
	int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			temp[falg++] = a[begin1++];
		}
		else {
			temp[falg++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		temp[falg++] = a[begin1++];
	}
	while (begin2 <= end2) {
		temp[falg++] = a[begin2++];
	}
	//拷贝回去
	int i = 0;
	for (i = left; i <= right; ++i) {
		a[i] = temp[i];
	}
}
void MergeSort(int* a, int n) {
	assert(a);
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, temp);
	free(temp);
	temp = NULL;
}
int main() {
	int arr[] = { 3,0,8,11,5,33,10,8,18,39,-3,19 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

归并排序非递归思想：
这里的话用循环的话更简单点；利用一个gap，当作一个区间的大小，两个区间大小就是2*gap了，把两个区间进行排序，放入临时数组排序，拷贝回去，然后继续下一个两个区间的同样做法，意思是把大的区间分成多个两个区间进行排序，一开始是分成一个数为一个区间，因为一个数已经排好了，两个区间就是两个数嘛，然后排后面的两个数，一直排到最后；然后gap变成2，两个数为一个区间，4个数两个区间进行排，然后gap是4…
但是这里最重要的是边界问题；万一右区间不存在，我们就不放进临时数组进行排了，然后万一右区间不完整，这个时候就要调整有区间至n-1;

#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
void MergeNonR(int* a, int n) {
	assert(a);
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;
	while(gap<n){

	
	for (int i = 0; i < n; i += 2 * gap) {
		//[i,i+gap-1],[i+gap,i+2*gap-1]
		int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1;
		int falg = i;
		//右区间不存在的情况
		if (begin2 >= n)
			break;
		//右区间不满需要调整
		if (end2 >= n)
			end2 = n - 1;
		while (begin1 <= end1 && begin2 <= end2) {
			if (a[begin1] < a[begin2])
				temp[falg++] = a[begin1++];
			else
				temp[falg++] = a[begin2++];
		}
		while (begin1 <= end1) {
			temp[falg++] = a[begin1++];
		}
		while (begin2 <= end2) {
			temp[falg++] = a[begin2++];
		}
		//拷贝回去
		int j = 0;
		for (j = i; j <= end2; ++j) {
			a[j] = temp[j];
		}
	}
	gap *= 2;

}
}
int main() {
	int arr[] = { 2,55,10,39,1,0,-3,33,10,348,38,19,39,40,49,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	MergeNonR(arr, sz);
	int i = 0;
	for (i = 0; i < sz; ++i) {
		printf("%d ", arr[i]);
	}
	return 0;
}

八. 计数排序

这个比较简单；但是运用场景需要条件，用在比较集中的一些数据上，要是比较分散，还是得用其它排序；
就是把数据当成重新开的数组的下标，然后计数每个数据的个数放进对应下标的数组上，然后从下标0开始遍历新数组，看数据大于0的下标就是原数组的数据，而新数组下标不就是排好了的数据吗？

总结