排序算法——一篇文章搞懂常用的排序算法

海盗船长

发布于 2020-08-27 16:58:29

3880

发布于 2020-08-27 16:58:29

1.排序的概念及应用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

1.2常见的排序算法

2常见排序算法的实现

2.1插入排序

2.1.1直接插入排序

基本思想

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

代码实现：

#include<iostream>
using namespace std;
int main()
{
	int a[] = { 43, 2, 3, 5, 76, 87, 45, 345, 5 };
	int k = sizeof(a) / sizeof(a[0]);
	int i = 0, j = 0;
	for (i = 1; i < k; i++)
	{
		if (a[i] < a[i - 1])
		{
			int tmp = a[i];
			for (j = i - 1; j>=0 && a[j] > tmp; j--){
				a[j+1] = a[j];
			}
			a[j + 1] = tmp;
		}
	}
	for (int i = 0; i < k; i++)
		cout << a[i] << endl;
	system("pause");
	return 0;
}

结果：

直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

2.1.2希尔排序（缩小增量排序）

基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void shellsort(vector<int> &res,int len)
{
	int d = len;
	while (d > 1)
	{
		d = (d + 1) / 2;
		for (int i = 0; i < len - d; i++)
		{
			if (res[i + d] < res[i])
			{
				int tmp = res[i];
				res[i] = res[i + d];
				res[i + d] = tmp;
			}
		}
	}
}
int main()
{
	vector<int> res;
	int tmp = 0;
	cout << "请输入要排序的数字并以任意字符作为结尾" << endl;
	while (cin>>tmp)
	{
		res.push_back(tmp);
	}
	shellsort(res, res.size());
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << endl;
	system("pause");
	return 0;
}

运行结果：

希尔排序的特性总结： 1. 希尔排序是对直接插入排序的优化。 2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N1.3—N2） 4. 稳定性：不稳定

2.2选择排序

2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2.2直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void selectsort(vector<int> &res, int len)
{
	int i=0, j=0, m = 0;
	for (int i = 0; i < len - 1; i++)
	{
		m = i;
		for (j = i + 1; j < len;j++)
		if (res[j]<res[m]) m = j;
		if (m != i){
			int tmp = res[i];
			res[i] = res[m];
			res[m] = tmp;
		}
	}
}
int main()
{
	vector<int> res;
	int tmp = 0;
	cout << "请输入要排序的数字并以任意字符作为结尾" << endl;
	while (cin >> tmp)
	{
		res.push_back(tmp);
	}
	selectsort(res, res.size());
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << endl;
	system("pause");
	return 0;
}

运行结果：

直接选择排序的特性总结：

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

2.2.3堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

代码实现：

#include<iostream>
#include<vector>
using namespace std;
void max_heapify(vector<int>& arr, int start, int end)
{
	//建立父节点指标和子节点指标
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end)  //若子节点指标在范围内才做比较
	{
		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
			son++;
		if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
			return;
		else  //否则交换父子内容再继续子节点和孙节点比较
		{
			swap(arr[dad], arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(vector<int> &arr, int len)
{
	//初始化，i从最後一个父节点开始调整
	for (int i = len / 2 - 1; i >= 0; i--)
		max_heapify(arr, i, len - 1);
	//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
	for (int i = len - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}

int main()
{
	vector<int> res;
	int tmp = 0;
	cout << "请输入要排序的数字并以任意字符作为结尾" << endl;
	while (cin >> tmp)
	{
		res.push_back(tmp);
	}
	heap_sort(res, res.size());
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << endl;
	system("pause");
	return 0;
}

运行结果：

堆排序的特性总结：

堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

2.3交换排序

基本思想： 所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

代码实现：

#include<iostream>
#include<vector>
using namespace std;


void bubble_sort(vector<int>& arr, int len)
{
	int i, j;  int temp;
	for (i = 0; i < len - 1; i++)
	for (j = 0; j < len - 1 - i; j++)
	if (arr[j] > arr[j + 1])
	{
		temp = arr[j];
		arr[j] = arr[j + 1];
		arr[j + 1] = temp;
	}
}

int main()
{
	vector<int> res;
	int tmp = 0;
	cout << "请输入要排序的数字并以任意字符作为结尾" << endl;
	while (cin >> tmp)
	{
		res.push_back(tmp);
	}
	bubble_sort(res, res.size());
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << endl;
	system("pause");
	return 0;
}

冒泡排序的特性总结：

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

2.3.2快速排序

是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。将区间按照基准值划分为左右两半部分的常见方式有：

hoare版本
挖坑法
前后指针版本代码实现（递归）：

#include<iostream>
#include<vector>
using namespace std;
void Qsort(vector<int>& arr, int low, int high){
	if (high <= low) return;
	int i = low;
	int j = high + 1;
	int key = arr[low];
	while (true)
	{
		/*从左向右找比key大的值*/
		while (arr[++i] < key)
		{
			if (i == high){
				break;
			}
		}
		/*从右向左找比key小的值*/
		while (arr[--j] > key)
		{
			if (j == low){
				break;
			}
		}
		if (i >= j) break;
		/*交换i,j对应的值*/
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	/*中枢值与j对应值交换*/
	int temp = arr[low];
	arr[low] = arr[j];
	arr[j] = temp;
	Qsort(arr, low, j - 1);
	Qsort(arr, j + 1, high);
}
int main()
{
	vector<int> res;
	int tmp = 0;
	cout << "请输入要排序的数字并以任意字符作为结尾" << endl;
	while (cin >> tmp)
	{
		res.push_back(tmp);
	}
	Qsort(res,0, res.size()-1);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << endl;
	system("pause");
	return 0;
}

运行结果：

快速排序的特性总结：

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定

2.4归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

代码实现：

#include<iostream>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
/**将a开头的长为length的数组和b开头长为right的数组合并n为数组长度，用于最后一组*/
void　Merge(int*　data,int　a,int　b,int　length,int　n){
　int　right;
　if(b+length-1 >= n-1)　right = n-b;
　else　right = length;
　int*　temp = new　int[length+right];
　int　i=0, j=0;
　while(i<=length-1 && j<=right-1){
    　if(data[a+i] <= data[b+j]){
    　    temp[i+j] = data[a+i];i++;
      }
    　else{
        temp[i+j] = data[b+j];
        j++;
      }
　}
　if(j == right){//a中还有元素，且全都比b中的大,a[i]还未使用
　  memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int));
　}
  else if(i == length){
      memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int));
  }
　memcpy(data+a, temp, (right + length) * sizeof(int));
　delete [] temp;
}
void　MergeSort(int*　data, int　n){
　int　step = 1;
　while(step < n){
    　for(int　i=0; i<=n-step-1; i+=2*step)
    　    Merge(data, i, i+step, step, n);
    //将i和i+step这两个有序序列进行合并
    //序列长度为step
    //当i以后的长度小于或者等于step时，退出
    　step*=2;//在按某一步长归并序列之后，步长加倍
　}
}
int　main(){
　int　n;
　cin>>n;
　int*　data = new　int[n];
　if(!data)　exit(1);
　int　k = n;
　while(k--){
　    cin>>data[n-k-1];
　}
　clock_t　s = clock();
　MergeSort(data, n);
　clock_t　e = clock();
　k=n;
　while(k--){
　    cout<<data[n-k-1]<<' ';
　}
　cout<<endl;
　cout<<"the algorithm used"<<e-s<<"miliseconds."<<endl;
　delete　data;
　return　0;
}
 
递归算法：
#include<iostream>
using namespace std;
void merge(int *data, int start, int mid, int end, int *result)
{
    int i, j, k;
    i = start;
    j = mid + 1;                        //避免重复比较data[mid]
    k = 0;
    while (i <= mid && j <= end)        //数组data[start,mid]与数组(mid,end]均没有全部归入数组result中去
    {
        if (data[i] <= data[j])         //如果data[i]小于等于data[j]
            result[k++] = data[i++];    //则将data[i]的值赋给result[k]，之后i,k各加一，表示后移一位
        else
            result[k++] = data[j++];    //否则，将data[j]的值赋给result[k]，j,k各加一
    }
    while (i <= mid)                    //表示数组data(mid,end]已经全部归入result数组中去了，而数组data[start,mid]还有剩余
        result[k++] = data[i++];        //将数组data[start,mid]剩下的值，逐一归入数组result
    while (j <= end)                    //表示数组data[start,mid]已经全部归入到result数组中去了，而数组(mid,high]还有剩余
        result[k++] = data[j++];        //将数组a[mid,high]剩下的值，逐一归入数组result
 
    for (i = 0; i < k; i++)             //将归并后的数组的值逐一赋给数组data[start,end]
        data[start + i] = result[i];    //注意，应从data[start+i]开始赋值
}
void merge_sort(int *data, int start, int end, int *result)
{
    if (start < end)
    {
        int mid = start + (end-start) / 2;//避免溢出int
        merge_sort(data, start, mid, result);                    //对左边进行排序
        merge_sort(data, mid + 1, end, result);                  //对右边进行排序
        merge(data, start, mid, end, result);                    //把排序好的数据合并
    }
}
void amalgamation(int *data1, int *data2, int *result)
{
    for (int i = 0; i < 10; i++)
        result[i] = data1[i];
    for (int i = 0; i < 10; i++)
        result[i + 10] = data2[i];
}
int main()
{
    int data1[10] = { 1,7,6,4,9,14,19,100,55,10 };
    int data2[10] = { 2,6,8,99,45,63,102,556,10,41 };
    int *result = new int[20];                              
    int *result1 = new int[20];
    amalgamation(data1, data2, result);
    for (int i = 0; i < 20; ++i)
        cout << result[i] << "  ";
    cout << endl;
    merge_sort(result, 0, 19, result1);
    for (int i = 0; i < 20; ++i)
        cout << result[i] << "  ";
    delete[]result;
    delete[]result1;
    return 0;
}

归并排序特性总结：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

2.5计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中代码实现：

#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range(范围)
int a[MAXN], c[MAXN], ranked[MAXN];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; 
        ++c[a[i]];
    }
    for (int i = 1; i < k; ++i)
        c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i)
        ranked[--c[a[i]]] = a[i];//如果是i表达的是原数标号，a[i]就是排序后的正确序列
    for (int i = 0; i < n; ++i)
        cout << ranked[i] << endl;
    return 0;
}

运行结果：

计数排序的特性总结：计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。时间复杂度：O(MAX(N,范围)) 空间复杂度：O(范围) 稳定性：稳定

排序算法复杂度与稳定性分析

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度