安全和实用密码学等

void SelectSort(int* arr, int n){	//保存参与单趟排序的第一个数和最后一个数的下标	int begin = 0, end = n - 1;	while (begin < end)	{		//保存最大值的下标		int maxi = begin;		//保存最小值的下标		int mini = begin;		//找出最大值和最小值的下标		for (int i = begin; i <= end; ++i)		{			if (arr[i] < arr[mini])			{				mini = i;			}			if (arr[i] > arr[maxi])			{				maxi = i;			}		}		//最小值放在序列开头		Swap(&arr[mini], &arr[begin]);		//防止最大的数在begin位置被换走		if (begin == maxi)		{			maxi = mini;		}		//最大值放在序列结尾		Swap(&arr[maxi], &arr[end]);		++begin;		--end;	}}

//交换函数void Swap(int* p1, int* p2) {	int tmp = *p1;	*p1 = *p2;	*p2 = tmp;}//三数取中int GetMidIndex(int* arr, int left, int right) {	int mid = (right - left) / 2 + left;	if (arr[left] < arr[mid]) {		if (arr[mid] < arr[right]) {			return mid;		}		else if (arr[left] > arr[right]) {			return left;		}		else {			return right;		}	}	else {			//arr[left]>=arr[mid]		if (arr[mid] > arr[right]) {			return mid;		}		else if (arr[left] < arr[right]) {			return left;		}		else {			return right;		}	}} //前后指针法int PartSort(int* arr, int left, int right) {	int mid = GetMidIndex(arr, left, right);	Swap(&arr[left], &arr[mid]);	int keyi = left;	//基准值下标放在最左侧	int prev = left;	int cur = left + 1;	while (cur<=right) {		if (arr[cur] < arr[keyi] && ++prev != cur) {			Swap(&arr[prev], &arr[cur]);		}		++cur;	}	Swap(&arr[keyi], &arr[prev]);		return prev;}

        冒泡排序

                算法思想:

                从左到右依次进行比较，升序时：如果左边大于右边则交换，从到到尾，全部进行交

换，挑选出最大的元素，放到最后，这是一次单趟排序，再进行循环选出第二大的，再循环选出第

三大的

                代码实现：

//交换void Swap(int* a,int* b){	int tmp = *a;	*a = *b;	*b = tmp;}//冒泡实现void BubbleSort(int* a,int n){	for (int j =0; j<n; j++)	{		for (int i = 1; i < n-j; i++)		{			if (a[i - 1] > a[i])			{				Swap(&a[i - 1], &a[i]);			}		}	}}

        1. 冒泡排序是一种非常容易理解的排序

        2. 时间复杂度：O(N^2)

        3. 空间复杂度：O(1)

        4. 稳定性：稳定

        快速排序

                1962年由Hoare提出的一种二叉树结构的交换排序的方法，其基本思想:任取待排序

元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中

所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过

程，直到所有元素都排列在相应位置上为止。需要注意的是排升序要建大堆，排降序建小堆。在计算机出现之前，算法就已经存在了。软件工程、本书用通俗易懂的语言来描绘算法世界，穿插有趣的文化历史故事和简单易懂的例子，不涉及艰深的数学知识，即使非专业人士也能轻松读懂。

作者简介:

        帕诺斯·卢里达斯（Panos Louridas）

        曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授，研究兴趣包括算法应用、这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。

                选出一个关键值key，把他放到正确的位置,我们在学习任何排序前，都应该先弄明白单

趟排序，然后再清楚整体思想即可

         Hoare版本

                         左边做Key右边先走，如果右边做Key左边先走，将小的往左边换，把大的往右边

        换，到相遇位置，停下，此时左边全是比中间位置小的，右边全是比中间位置大的，相遇位

        一定比Key小

                 Hoare一次排序其实本质是在排一个数据             

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

        注：但其有个致命特点，如果keyi在最左边时，而数组为有序，这样排序时，需要不断

创建新的栈帧，其时间复杂度，直接为n*logn，我们可以将Keyi的位置进行随机排放

        随机选Keyi      

                我们将keyi进行随机处理，就可以解决上面的问题

void QuickSort(int* a, int left, int right){	//  ... 返回条件	if (left >= right)	{		return;	}	int begin = left, end = right;	int randi = left + (rand() % (right - left));	Swap(&a[left],&a[randi]);	int keyi = left;	while (left < right)	{		// 右边找小		while (left < right && a[right] >= a[keyi])			--right;		// 左边找大		while (left < right && a[left] <= a[keyi])			++left;		Swap(&a[left], &a[right]);	}	Swap(&a[keyi], &a[left]);	keyi = left;	// [begin, keyi-1] keyi [keyi+1, end] 	// 递归	QuickSort(a,begin,keyi-1);	QuickSort(a,keyi+1,end);}

        三数取中

                有序情况下，三数取中对时间复杂度的优化，其极其明显

void QuickSort(int* a, int left, int right){	//  ... 返回条件	if (left >= right)	{		return;	}	int begin = left, end = right;	int midi = GetMidNumi(a,left,right);	Swap(&a[midi],&a[left]);	/*int randi = left + (rand() % (right - left));	Swap(&a[left],&a[randi]);*/	int keyi = left;	while (left < right)	{		// 右边找小		while (left < right && a[right] >= a[keyi])			--right;		// 左边找大		while (left < right && a[left] <= a[keyi])			++left;		Swap(&a[left], &a[right]);	}	Swap(&a[keyi], &a[left]);	keyi = left;	// [begin, keyi-1] keyi [keyi+1, end] 	// 递归	QuickSort(a,begin,keyi-1);	QuickSort(a,keyi+1,end);}

        挖坑法

int QuickSort(int* a, int left, int right){	//  ... 返回条件	if (left >= right)	{		return;	}	int begin = left, end = right;	int midi = GetMidNumi(a,left,right);	if(midi != left)		Swap(&a[midi],&a[left]);		int key = a[left];	int hole = key;	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;	// [begin, keyi-1] keyi [keyi+1, end] 	// 递归}void QuickSort1(int* a, int left, int right){	if (left >= right)	{		return;	}	int keyi = QuickSort(a,left,right);	QuickSort1(a,left,keyi-1);	QuickSort1(a,keyi+1,right);}

        前后指针版本

                1.cur找到比key小的值，++prev，cur和prev位置的值交换,++cur

                2.cur找到比key大的值，++cur

                 说明

                        1.prev要么紧跟着cur

                         2.prev跟cur中间间隔着比key大的一段值区间

        思路：

        通过创建两个指针，prev指针指向数组序列首元素位置，cur指向prev的下一个位置，cur通过遍历去寻找比key基准值小的，若找到了，还得看prev的下一个位置是否为cur所处的位置，若prev的下一个位置确实为cur所处位置，则将cur指向的值与prev指向的值进行互换，若prev的下一个位置不是cur所处位置，则cur继续往后遍历，直到cur遍历结束，最后要将key基准值与prev指向的值进行互换，最终确认基准值处于数组序列的中间位置。了解经典算法的起源，不仅是因为我们身处信息时代，更是因为算法的底层逻辑和应用可以为我们的工作、我们实现后可以进行性能测试的对比。著有《真实世界的算法：初学者指南》。它是通过堆来进行选择数据。
 

                图片演示：

       

                

// 堆排序void AdjustDown(int* a, int n, int root)//向下调整{	assert(a);	int parent = root;	int child = parent * 2 + 1;	while (child < n)	{		if (child + 1 < n && a[child + 1] > a[child])		{			child++;		}		if (a[child] > a[parent])		{			Swap(&a[child], &a[parent]);			parent = child;			child = parent * 2 + 1;		}		else		{			break;		}	}} void HeapSort(int* a, int n){	assert(a);     //建堆	for (int i = (n - 1 - 1) / 2; i >= 0; i--)	{		AdjustDown(a, n, i);	}     //交换	for (int i = n - 1; i > 0; i--)	{		Swap(&a[i], &a[0]);		AdjustDown(a, i, 0);	}}

       

        选择排序

        思路(升序)：

                第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完 。