- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

【算法之美】不要再用冒泡、选择、插入排序了，丢不起这人！

AI 菌发表于 2021/08/05 00:12:44 2021/08/05

【摘要】文章目录 1. 冒泡排序2. 选择排序3. 插入排序4. 快速排序5. 堆排列6. 归并排列7. 希尔排序8. 优化后的快排函数sort() 前言排序算法在算法与数据结构中很常见，在学习排序算法的时候，会涉及到各种核心算法的概念。例如，分治法、随机算法、最佳、最差和平均情况分析，时空权衡等，还有数组、堆和二叉树之类的数据结构。通常对于一个问题，...

文章目录

前言
排序算法在算法与数据结构中很常见，在学习排序算法的时候，会涉及到各种核心算法的概念。例如，分治法、随机算法、最佳、最差和平均情况分析，时空权衡等，还有数组、堆和二叉树之类的数据结构。
通常对于一个问题，考察一个算法的好坏取决于它的 算法复杂度。而算法复杂度又分为时间复杂度和空间复杂度。时间复杂度是指：执行算法所需要的计算工作量。空间复杂度是指：执行这个算法所需要的内存空间。
如果一个排序算法不需要额外的存储空间，可以直接在原来的数组完成排序操作，这个算法可以被称之为 原地算法，空间复杂度是 $O (1)$ 。 $O (1)$ 表示只需要常数量级的空间，不会随着数组大小的变化而变化。

参考链接：https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-
来源：力扣（LeetCode）

1. 冒泡排序

核心思想：第一次，依次比较相邻的两个数，如果后面的数小，就交换位置，直到最大值冒泡到最后面；第二次，依次比较相邻的两个数（比到前N-1个数为止），如果后面数小，就交换位置，直到次大值冒泡到数列倒数第二的位置。依次类推，两个数比较大小，使得较大的数向后沉，较小的数向前冒。
时间复杂度： $O（n^2）$ ， 空间复杂度： $O (1)$
代码实现：

vector<int> sortArr(vector<int>& arr)
{
	for(int i=0;i<arr.size();i++)
		for(int j=0;j<arr.size()-i-1;j++)
		{ if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]);
		}
	return arr;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

2. 选择排序

核心思想：首先找到最大值，与最右边的数位置互换；再找前n-1项的最大值，与第n-1个元素的位置互换；依次类推，直到完成升序排列。
时间复杂度： $O（n^2）$ ， 空间复杂度： $O (1)$
代码实现：

vector<int> sortArr2(vector<int>& arr)
{
	for(int i=0;i<arr.size()-1;i++)
	{
		int max_index=0;
		for(int j=0;j<arr.size()-i;j++)
		{ if(arr[j]>arr[max_index]) max_index=j;
		}
		swap(arr[max_index],arr[arr.size()-1-i]);
	}
	return arr;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

3. 插入排序

核心思想：先把前 i-1 个元素按顺序排好，再插入第i个元素。
时间复杂度： $O（n^2）$ ， 空间复杂度： $O (1)$
代码实现：

vector<int> sortArr3(vector<int>& arr)
{
	for(int i=1;i<arr.size();i++)  //从二个元素开始遍历 
		for(int j=i;j>0&&arr[j]<arr[j-1];j--) swap(arr[j],arr[j-1]);
	return arr;	
} 

  
 
  1
  2
  3
  4
  5
  6
  7

4. 快速排序

核心思想：通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。
时间复杂度： $O （ n l o g n ）$ ， 空间复杂度：最差 $O (n)$ ，最优 $O (l o g n)$
代码实现：

class Solution { int partition(vector<int>& nums, int l, int r) { int pivot = nums[r]; int i = l - 1; for (int j = l; j <= r - 1; ++j) { if (nums[j] <= pivot) { i = i + 1; swap(nums[i], nums[j]); } } swap(nums[i + 1], nums[r]); return i + 1; } int randomized_partition(vector<int>& nums, int l, int r) { int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元 swap(nums[r], nums[i]); return partition(nums, l, r); } void randomized_quicksort(vector<int>& nums, int l, int r) { if (l < r){ int pos = randomized_partition(nums, l, r); randomized_quicksort(nums, l, pos - 1); randomized_quicksort(nums, pos + 1, r); } }
public: vector<int> sortArray(vector<int>& nums) { srand((unsigned)time(NULL)); randomized_quicksort(nums, 0, (int)nums.size() - 1); return nums; }
};

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32

5. 堆排列

核心思想：先将待排序的序列建成 大根堆，使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，然后再调整堆顶元素使得剩下的 n-1 个元素仍为大根堆，再重复执行以上操作我们即能得到一个有序的序列。
时间复杂度： $O (n l o g n)$ ， 空间复杂度： $O (1)$ ，只需要常数的空间存放若干变量
代码实现：

class Solution { void maxHeapify(vector<int>& nums, int i, int len) { for (; (i << 1) + 1 <= len;) { int lson = (i << 1) + 1; int rson = (i << 1) + 2; int large; if (lson <= len && nums[lson] > nums[i]) { large = lson; } else { large = i; } if (rson <= len && nums[rson] > nums[large]) { large = rson; } if (large != i) { swap(nums[i], nums[large]); i = large; } else break; } } void buildMaxHeap(vector<int>& nums, int len) { for (int i = len / 2; i >= 0; --i) { maxHeapify(nums, i, len); } } void heapSort(vector<int>& nums) { int len = (int)nums.size() - 1; buildMaxHeap(nums, len); for (int i = len; i >= 1; --i) { swap(nums[i], nums[0]); len -= 1; maxHeapify(nums, 0, len); } }
public: vector<int> sortArray(vector<int>& nums) { heapSort(nums); return nums; }
};

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42

6. 归并排列

核心思想：利用了分治的思想来对序列进行排序。对一个长为 n 的待排序的序列，我们将其分解成两个长度为 n/2 的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。
时间复杂度： $n l o n g (n)$ ， 空间复杂度： $O (n)$
程序实现：

class Solution { vector<int> tmp; void mergeSort(vector<int>& nums, int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); int i = l, j = mid + 1; int cnt = 0; while (i <= mid && j <= r) { if (nums[i] < nums[j]) { tmp[cnt++] = nums[i++]; } else { tmp[cnt++] = nums[j++]; } } while (i <= mid) tmp[cnt++] = nums[i++]; while (j <= r) tmp[cnt++] = nums[j++]; for (int i = 0; i < r - l + 1; ++i) nums[i + l] = tmp[i]; }
public: vector<int> sortArray(vector<int>& nums) { tmp.resize((int)nums.size(), 0); mergeSort(nums, 0, (int)nums.size() - 1); return nums; }
};

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28

7. 希尔排序

核心思想：希尔排序可以看作是一个冒泡排序或者插入排序的变形。希尔排序在每次的排序的时候都把数组拆分成若干个序列，一个序列的相邻的元素索引相隔固定的距离gap，每一轮对这些序列进行冒泡或者插入排序，然后再缩小gap得到新的序列一一排序，直到gap为1。
时间复杂度： $O(n^\frac{4}{3})$ ~ $O(n^2)$ ，空间复杂度： $O (1)$
代码实现：

vector<int> shellSor(vector<int>& arr) { int gap = arr.size() >> 1; while (gap > 0) { for (int i = 0; i < gap; i++) { // 对每个子序列进行排序 for (int j = i+gap; j < arr.size(); j+=gap) { // 插入排序的部分 int temp = j; while (temp > i && arr[temp] < arr[temp-gap]) { swap(arr[temp], arr[temp-gap]); temp -= gap; } } } gap >>= 1; } return arr;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

8. 优化后的快排函数sort()

当然，除了以上排序算法外。有时为了方便，我们还可以调用标准库algorithm中的排序函数sort()，该函数在原有快速排序算法上进行了改进，我们可以直接使用它进行排序，默认是升序。

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

bool compare(int a, int b){
	return a>b;
}
//使用自带排序功能sort(),compare决定升序还是降序。
vector<int> sortArr(vector<int>& arr){
	sort(arr.begin(),arr.end());  //升序
	//sort(arr.begin(),arr.end(),compare);  //降序
	return arr; 
} 

int main(){
	int n=0;
	cin>>n;  //输入序列元素的个数
	vector<int> arr_num(n);
	for(int i=0; i<n;i++)
		cin>>arr_num[i];  //输入元素
	arr_num=sortArr(arr_num);  //排序
	for(int i=0; i<n; i++){
		cout<<arr_num[i]<<" ";  //打印输出
	}
	return 0;
} 

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27

除此之外，还有计数排序、桶排序、基数排序、二叉树排序等。具体要选择哪一种排序算法，则要根据实际问题，权衡时间和空间复杂度，尽量选择综合性能更好的排序算法。

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/105370404

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入