算法——常用排序算法（下）（C++实现）

深碍√TFBOYSˉ_ 2021-12-09 18:41 224阅读 0赞

# 归并排序 #

## 思路 ##

归并排序是分治思想，涉及到。其时间复杂度为 O ( N l o g N ) O(Nlog^\{N\}) O(NlogN)，具有稳定性。

## 代码 ##

#include <iostream>
    using namespace std;
    
    //对已排好的两个数组进行合并
    void merge(int arr[], int low, int mid, int high)
    {
    	int i = low, j = mid + 1;
    	int count = 0;
    	int *temp = new int[high - low + 1];//辅助数组，长度与原数组相同
    	//谁小填谁
    	for (i = low, j = mid + 1; i <= mid && j <= high;)
    	{
    		if (arr[i] <= arr[j])
    		{
    			temp[count++] = arr[i++];
    		}
    		else
    		{
    			temp[count++] = arr[j++];
    		}
    	}
    	//判断i,j越界情况，将不越界的数组里的数直接补到temp中
    	if (i <= mid)
    	{
    		for (; i <= mid; i++)
    		{
    			temp[count++] = arr[i];
    		}
    	}
    	else
    	{
    		for (; j <= high; j++)
    		{
    			temp[count++] = arr[j];
    		}
    	}
    	//将temp拷贝会原数组
    	i = low;
    	for (int k = 0; k < count&&i <= high; k++, i++)
    	{
    		arr[i] = temp[k];
    	}
    	delete[] temp;
    }
    //分而治之，将长数组一直进行二等分，当分到只剩一个时返回
    void Msort(int* arr, int low, int high)
    {
    	if (low >= high) return;
    	int mid = (low + high) / 2;
    	Msort(arr, low, mid);
    	Msort(arr, mid + 1, high);
    	merge(arr, low, mid, high);
    }
    
    int main()
    {
    	int len;
    	cout << "Please enter the length of array you want to sort : ";
    	cin >> len;
    	int *arr = new int[len];
    	cout << "The data is : ";
    	for (int i = 0; i < len; i++)
    	{
    		cin >> arr[i];
    	}
    	Msort(arr, 0, len - 1);
    	cout << "After sort : ";
    	for (int i = 0; i < len; i++)
    	{
    		cout << arr[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }

# 快排 #

## 思路 ##

其时间复杂度为 O ( N l o g N ) O(Nlog^\{N\}) O(NlogN)，不具有稳定性，其常数项较少，在样本数量较少时使用。最常用的是随机快排，即分大小区间时的基准数值随机选择。

## 代码 ##

#include<iostream>
    using namespace std;
    void quickSort(int array[], int left, int right)
    {
    	//划分大小两个区间，设置一个temp装需要判断的值
    	int less = left;
    	int more = right;
    	int temp = array[less];//将最左值设定为基数
    	//在非越界条件下开始快排
    	if (less < more)
    	{
    		while (less < more)
    		{
    			while (less < more &&  array[more] >= temp)
    				more--;
    			if (less < more)
    			{
    				array[less] = array[more];
    				less++;
    			}
    			while (less < more && temp > array[less])
    				less++;
    			if (less < more)
    			{
    				array[more] = array[less];
    				more--;
    			}
    		}
    		//把基准数放到less位置
    		array[less] = temp;
    		//递归方法
    		quickSort(array, left, less - 1);
    		quickSort(array, less + 1, right);
    	}
    }
    int main()
    {
    	int len;
    	cout << "键入快排数组长度 : ";
    	cin >> len;
    	int *arr = new int[len];
    	cout << "键入快排数组 : ";
    	for (int i = 0; i < len; i++)
    	{
    		cin >> arr[i];
    	}
    	quickSort(arr, 0, len - 1);
    	cout << "快排结果 : ";
    	for (int i = 0; i < len; i++)
    	{
    		cout << arr[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }

# 堆排 #

## 思路 ##

概念：完全二叉树（可以不满，但必须是从左到右）可用数组表示。节点i（i为节点值而不是该位置的数）的左孩子2i+1,右孩子2i+2.其父节点为(i-1)/2。只要满足上面的公式，就可以将数脑补为一颗完全二叉树。堆就是一颗完全二叉树。大跟堆，任何一颗子树的最大值就是这个子树的头部，小跟堆同理。  
堆排序的时间复杂度为 O ( N l o g N ) O(Nlog^\{N\}) O(NlogN)，不具有稳定性。  
大根堆建立过程：大根堆未必有序！  
1)数组变大根堆  
2)堆顶弹出（将堆顶与最后一个数字交换，然后堆的长度–即可减去堆顶）  
3)剩下的堆继续heapify,形成新的大根堆  
循环如此，最后的数组就形成了有序数组（从小到大）

## 代码 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    //实现大跟堆，较大数值上升的过程
    void heapify(vector<int> &arr, int len, int index)
    {
    	//将输入数组定义为一个完全二叉树，设定左右孩子节点与父节点
    	int left = 2 * index + 1;
    	int right = 2 * index + 2;
    	int maxindex = index;
    	//左孩子大于父节点的值时，将左孩子赋值给maxindex
    	if (left<len&&arr[left]>arr[maxindex])
    		maxindex = left;
    	//右孩子大于父节点的值时，将右孩子赋值给maxindex
    	if (right<len&&arr[right]>arr[maxindex]) 
    		maxindex = right;
    	//将maxindex上的值即最大值与父节点的值交换
    	if (maxindex != index)
    	{
    		swap(arr[maxindex], arr[index]);
    		heapify(arr, len, maxindex);
    	}
    }
    //堆排序
    void heapsort(vector<int> &arr, int size)//size 数组长度，i
    {
    	//先构建大跟堆，从最后一个非叶子节点向上
    	for (int i = size / 2 - 1; i >= 0; i--)
    	{
    		heapify(arr, size, i);
    	}
    	//调整大根堆
    	for (int i = size  - 1; i >= 1; i--)
    	{
    		swap(arr[0], arr[i]);
    		heapify(arr, i, 0);
    	}
    }
    int main()
    {
    	vector<int> arr = { 2,6,3,5,1,7 };
    	heapsort(arr, arr.size());
    	for (int i = 0; i < arr.size(); i++)
    	{
    		cout << arr[i] <<"";
    	}
    	cout << endl;
    	return 0;
    }

# 总结 #

工程中的综合排序算法考虑项：数据量、常数项、时间复杂度、稳定性  
先判断数据状况，数据量小时（<=60）直接使用插排（因为其常数项低，即使时间复杂度高，但依然不影响其速度快）；,数据量大时，基础类型时用快排（因为基础类型的相同值无差别不用考虑稳定性），若是自己定义的则用归并排序（此时稳定性有意义）。  
不是基于比较的排序，与实际数据状况有关，所以实际不常用；时间复杂度和空间复杂度均为O(N)；具有稳定性。例如桶排序：是一种排序概念（一个萝卜一个坑），其中包括计数排序和基数排序。