常见的排序算法

小灰灰 2021-11-10 10:06 340阅读 0赞

## 冒泡排序 ##

*思路：需要用n-1个循环，每个循环都从第1个数开始向后遍历，遇到无序的一对数则交换这两个数，第1次遍历完成后，第n个数有序，下次只需要遍历到第n-1个数。以此类推，第n-1次遍历完成后，从第2个数到第n个数有序，只剩一个数一定是有序的，所以整个数组有序。*

**代码：**

void BubbleSort(int *arr, int len)
    {
    	for(int i=1;i<len;i++)//外循环，控制遍历次数
    	{
    		for(int j=0;j<len-i;j++)//内循环，用来排序
    		{
    			if(arr[j]>arr[j+1])
    				Swap(arr[j],arr[j+1]);
    		}
    	}
    }

## 选择排序 ##

*思路：第一次遍历先选出最小的数，把它和第一个数交换，那么第一个数就有序了，第二次遍历从第二个数开始，此时选出的最小值和第二个位置的数交换，则前两个数有序。以此类推，直到倒数第二个数有序，则整个数组有序。*  
**代码：**

void SelectSort(int *arr, int len)
    {
    	for(int i=0;i<len-1;i++)
    	{
    		int min_pos=i;
    		for(int j=i;j<len;j++)
    		{
    			if(arr[min_pos]>arr[j])
    				min_pos=j;
    		}
    		Swap(arr[i],arr[min_pos]);
    	}
    }

## 插入排序 ##

*思路：总的来说，就是在前k个数里，把第k个数放到它正确的位置。  
那么，前一个数的位置一定是对的，从第二个数开始，在前两个数里找到第二个数正确的位置，以此类推。实现时，需要先把第k个数记录下来，然后从后往前寻找，在找到正确位置之前经过的所有数都应该向后移一位，找到后进行赋值。每次遍历都使得前k个数有序，遍历完成时整个数组就有序了。*  
**代码：**

void InsertSort(int *arr, int len)
    {
    	for(int i=1;i<len-1;i++)
    	{
    		int tmp=arr[i];
    		int j=i-1;
    		for(;j>=0;j--)
    		{
    			if(arr[j]>tmp)
    				arr[j+1]=arr[j];
    			else
    				break;
    		}
    		arr[j+1]=tmp;
    	}
    }

## 希尔排序 ##

*思路：希尔排序实际上就是插入排序的一种优化，由于插入排序中，原数组越有序，排序效率越高，所以希尔排序通过分组的方式，使得原数组更加有序之后再进行插入排序。  
希尔排序会用到分组的增量数组，也就是分组时的依据，比如数组中第一个数是5，那么第一次分组时，就会将下标为0、5、10、…的数分为一组，1、6、11、…的数分为第二组，以此类推，所以要保证数组最后一个元素是1，使得最后一次分组是整个数组在一起，那么最后一次插入排序就可以使整个数组有序。（这里的数组有书上说最好是质数数组，我还不知道原因，如果有人看到可以告诉我。蟹蟹辣。）*  
**代码：**

void Shell(int *arr, int len, int p)
    {
    	for (int i = p; i < len; i++) //控制对哪一组进行插入排序
     	{
      		int j = i - p;
    		int tmp = arr[i];
      
      		for (; j >= 0 && arr[j] > tmp; j -= p) //对下标为i±p的元素进行插入排序
      		{
       			arr[j + p] = arr[j];
      		}
      	arr[j + p] = tmp;
     	}
    }
    void ShellSort(int *arr, int len)
    {
     	int Part_len[] = { 7,5,3,1 };//增量数组，具体可以根据原数组元素个数来确定
    	for(int i=0;Part_len[i]>=1;i++)
     	{
      		Shell(arr, len, Part_len[i]);//由于通常排序我们只传递数组的首地址和长度
            				     //所以这里做了一次封装
     	}
    }

## 快速排序 ##

*思路：快速排序的思想可以概括为“ 将每一个数字放在它正确的位置上 ”，那么所谓正确的位置，就是保证它前面的所有数字都比它小，后面的数字都比它大。  
实现起来就是先将第一个数字记下来，从后向前找到第一个比它小的数字放在它原本的位置，再从前往后找到第一个比它大的数字放在刚才空出来的位置，然后再重复前面的操作，直至将整个数组遍历完，最后一个空出来的位置用一开始记下来的值填上。（这里所谓空出来的位置，就是将值赋给过其他位置的地方，由于值不会丢失，所以可以当作空位。）第一次遍历完后，可以得到一个已经找到正确位置的值假设为第k个数，那么使k的左右两部分（两个数以上做这个操作）分别递归再次执行上述过程。递归结束时整个数组就是有序的。*  
**代码：**

void Quick(int *arr, int low, int high)
    {
    	int i=low;
    	int j=high;
    	int tmp=arr[i];//把处于下标low的数据记录下来
    	while(i<j)
    	{
    		while(i<j&&arr[j]>=tmp)j--;//从右向左找
    		arr[i]=arr[j];
    		while(i<j&&arr[i]<=tmp)i++;//从左向右找
    		arr[j]=arr[i];
    	}
    	arr[i]=tmp;//把刚开始记下来的值放在找到的位置上
    	
    	if(i-low>1)//左侧递归
    		Quick(arr,low,i-1);
    	if(high-i>1)//右侧递归
    		Quick(arr,i+1,high);
    }
    void QuickSort(int *arr, int len)
    {
    	Quick(arr,0,len-1);
    }

## 堆排序 ##

*思路：堆排序使用了数据结构中的最大堆结构，即一个二叉树中每个树的根节点都是这个树里的最大值，那么我们要做的第一件事就是把原本按照下标排成的二叉树修改为最大堆。修改的实现，是从最下面的最右边第一颗二叉树向左向上依次遍历，在每个二叉树中将最大值换到根节点上，遍历完成后这棵树就是最大堆。然后我们将整棵树的根节点，也就是这个数组中的最大值，和最后一个节点交换位置，然后最后一个节点不动，对其他节点再次进行修改，变成一颗最大堆，以此类推。*  
**代码：**

void HeapOnce(int *arr, int i, int len)
    {
    	int j=2*i+1;
    	int tmp=arr[i];
    	while(j<len)
    	{
    		if(arr[j+1]>arr[j]&&j+1<len)
    			j++;
    		if(arr[j]>tmp)
    			{
    				arr[i]=arr[j];
    				i=j;
    				j=2*i+1;
    			}
    		else
    			break;
    	}
    	arr[i]=tmp;
    }
    void CreateHeap(int *arr, int len)
    {
    	int i=len/2-1;
    	for(;i>=0;i--)
    	{
    		HeapOnce(arr, i, len);
    	}
    }
    void HeapSort(int *arr, int len)
    {
    	CreateHeap(arr, len);
    	for(int i=len-1; i>=0; i--)
    	{
    		Swap(arr[i], arr[0]);
    		HeapOnce(arr,0,i);
    	}
    }

## 二路归并排序 ##

*思路：归并排序还是将数组分为小组排序。第一次排序先对下标0和1排，然后2和3排，直到结尾，完成之后数组变为len/2个有序的数组，每个数组内最多只有两个元素。第二次就对第一、二小组进行排序，以此类推。那么最后一次排序就是对整个数组的前半部分和后半部分就行排序，完成后整个数组有序。*  
**代码：**

void Merge(int *arr, int len, int width, int *tmp)//一次排序
    {
    	int l1=0;//队列一的左界
    	int h1=l1+width-1;//队列一的右界
    	int l2=h1+1;//队列二的左界
    	int h2=l2+width-1<len?l2+width-1:len-1;//队列二的右界
    	int pos=0;//数组遍历的下标
    	
    	while(l1<len&&l2<len)//大循环
    	{
    		while(l1<h1&&l2<h2)//小循环
    		{
    			if(arr[l1]<arr[l2])
    				arr[pos++]=arr[l1++];
    			else
    				arr[pos++]=arr[l2++]
    		}//结束是因为其中一个小队列左界越过右界
    		//处理剩下的元素
    		if(l1<=h1)arr[pos++]=arr[l1++];
    		if(l2<=h2)arr[pos++]=arr[l2++];
    		
    		//准备排下一组的两个小队列
    		l1=h2+1;
    		h1=l1+width-1<len?l1+width-1:len-1;
    		l2=h1+1;
    		h2=l2+width-1<len:l2+width-1:len-1;
    	}//大循环结束时一定是l2越界，l1可能越界也可能还没有越界
    
    	while(l1<len)//如果l1还没有越界，处理该队列剩余元素
    		tmp[pos++]=arr[l1++];
    			
    	for(int i=0;i<len;i++)//将存在tmp中的排好的元素还给arr
    		arr[i]=tmp[i];
    }
    void MergeSort(int *arr, int len)
    {
    	int *tmp=new int[len];
    	for(int i=1;i<len;i*=2)//从宽度为1排到宽度为len-1
    	{
    		Merge(arr,len,i,tmp);
    	}
    	delete[]tmp;
    }