常用排序算法

目录

1.快速排序
2.归并排序
3.堆排序

一、快速排序 1.原理

Partition（切分）：以第一个元素大小为标准元素，提前缓存，第一个元素位置用作“坑”，标定两个指针一右一左，右指针向中间遍历，如果右指针指向的元素比标准元素大，不做任何处理，指针左移，继续判断直到元素比标准元素大，将其覆盖到左指针指向的元素（即坑），这时候“坑”便转移到右指针的位置；左指针开始判断指向元素与标准元素的大小，如果小，指针右移，若更大，同样将元素扔到右指针指向的“坑”里。

接下来继续右指针动作，循环往复，直到两指针相遇，说明所有元素已经都处理完成，此时的效果是指针左边都是值小于标准元素 的元素，右边都是值大于标准元素的元素。只剩下标准元素还未插入，直接覆盖到左右指针指向的位置。

递归：一轮排序完成后，标准元素两边的子列依旧是无序的，于是可对两个子列进行递归方式的排序，递归结束条件自然是数组元素只有一个时。

2.代码

void QuickSort(vector<int>& list,int left,int right)
{
	if(left<right)
	{
		int mid = Partition(list,left,right);
		QuickSort(list,left,mid-1);
		QuickSort(list,mid+1,right);
	}
}


int Partition(vector<int>& list,int left,int right)
{
	int tmp=list[left];
	while(left<right)
	{
		while(left<right&&list[right]>=tmp)
		{
			right--;
		}
		list[left]=list[right];
		
		while(left<right&&list[left]<=tmp)
		{
			left++;
		}
		list[right]=list[left];
	}
	list[left]=tmp;
	return left;
}

二、归并排序 1.原理

将数组分成两两一组，组内排序，排序完成之后在对两个有序数组进行合并排序，直到所有组合并为一个有序数组。

2.代码

//序列合并函数
void merge(int A[],int L1,int R1,int L2,int R2)
{
	int i=L1,j=L2;
	int temp[R2-L2+R1-L1+2],index=0;
	while(i<=R1&&j<=R2)
	{
		if(A[i]<=A[j])
			temp[index++]=A[i++];
		else
			temp[index++]=A[j++];
	}
	while(i<=R1) temp[index++]=A[i++];
	while(j<=R2) temp[index++]=A[j++];
	for(int i=0;i<index;i++)
	{
		A[L1+i]=temp[i];
	}
}

void mergeSort(int A[],int left,int right)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		mergeSort(A,left,mid);
		mergeSort(A,mid+1,right);
		merge(A,left,mid,mid+1,right);
	}
}

三、堆排序 1.原理

建堆：基于堆的数据结构进行排序，属于选择排序的一种，堆是所有父节点都不大于（或不小于）子节点的完全二叉树。由于是完全二叉树，所以使用顺序存储即可，直接在原数组上进行 *** 作。
构建堆的过程是自下而上，自右而左的。以大根堆为例，需要遍历所有非叶节点，将节点与其子节点进行比较，如果子节点中有值比该节点值大的，则将两节点的值进行交换，完成了这一步，并没有结束，此时并不确定原节点的值在下沉到子节点后是否在其子树中构成大根堆，需要继续以上判断，直至它不小于其所有子节点。等到所有非叶节点遍历完成后就是一个大根堆了，因为所有值不配位的节点都进行了下沉。

排序：在堆建好了之后，以大根堆为例，其堆顶值为最大，取出根节点值，将堆尾节点取代堆顶，重新恢复为大根堆，再取出堆顶，如此循环，直至元素取完。那么如何恢复为大根堆呢？可以发现，除堆顶以外所有结构依旧还是大根堆，相当于只剩堆顶未下沉的建堆过程，所以只需要执行建堆的最后一步，对堆顶进行下沉即可。

2.代码

//向下调整函数 
//target是欲调整的节点下标,end为堆最后一个节点的下标
//注意数组是从下标1开始存储的
void DownAdjust(vector<int>& heap,int target,int end)
{
	int i=low,j=i*2;
	while(j<=end)
	{
	//如果右孩子存在，使j等于值更大节点下标
		if(j+1<=end&&heap[j+1]>heap[j])
		{
			j=j+1;
		}
		//子节点较大者大于父节点则进行交换，并向下进行下一轮循环
		if(heap[j]>heap[i])
		{
			swap(heap[i],heap[j]);
			i=j;
			j=2*i;
		}
		else
		{
			break;
		}
	}
}

//建堆
void CreateHeap(vector<int>& heap)
{
	for(int i=arr/2;i>0;i--)
	{
		DownAdjust(heap,i,heap.size()-1);
	}
}

//排序
void HeapSort(vector<int>& heap)
{
	CreateHeap(heap);
	for(int i=heap.size()-1; i>1 ;i--)
	{
		swap(heap[i],heap[1]);
		DownAdjust(heap,1,i-1);
	}
}

其他常用 *** 作

//删除堆顶元素并维持堆结构
void DeleteTop(vector<int>& heap)
{
	heap[1]=heap.back();
	heap.pop_back();
	DownAdjust(heap,1,heap.size()-1);
}