C++ 排序算法

今日打卡题目如下:

  1. 排序数组

各种排序算法

  1. 冒泡排序
  2. 插入排序t
  3. 快速排序
  4. 堆排序
  5. 桶排序

C++中的自定义排序算法

912. 排序数组

给定一个整数数组 nums,将该数组升序排列。

示例 1

1
2
输入:[5,2,3,1]
输出:[1,2,3,5]

示例 2

1
2
输入:[5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

  1. 1 <= A.length <= 10000
  2. -50000 <= A[i] <= 50000

我的解法

快速排序

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
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quicksort(nums,0,nums.size()-1);
return nums;
}
void quicksort(vector<int>& nums,int low ,int high)
{
if(low >= high) return;
int num = nums[low];
int left = low+1;
int right = high;
while(true)
{
while(left<=right && nums[left]<=num) left++;
while(left<=right && nums[right]>=num) right--;
if(left>right)
break;
swap(nums[left],nums[right]);
}
nums[low] = nums[right];
nums[right] = num;
quicksort(nums,low,right-1);
quicksort(nums,right+1,high);
}
};

十种常见排序算法

分类

  • 比较类排序

通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

  • 非比较类排序

不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

各算法复杂度

img

相关概念

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机

1. 冒泡排序

思想:从左往右遍历,比较相邻两个元素的大小,将大的一个放在后面,每遍历一趟,可找到一个最大值放置在最后,经过n-1趟遍历即可。

性能:时间复杂度为O(n2),元素比较次数与初始状态无关,性能略低于插入排序。

1
2
3
4
5
6
7
8
9
10
11
void Bubble_Sort(int* A,int len){
for(int i=1;i<len;i++){
for(int j=0;j<len-i;j++){
if(A[j]>A[j+1]){
int t = A[j+1];
A[j+1] = A[j];
A[j] = t;
}
}
}
}

2. 插入排序

思想: 将当前元素与它前面已排好序的元素依次进行比较,最后放置在合适的位置,初始时可从第二个元素开始,认为第一个元素已排好序。

性能: 算法时间复杂度为$O(n^2)$,在序列规模较小时,性能比较好,且元素比较次数与初始序列杂乱程度相关,最优复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
void Insert_Sort(int* A, int len){
for(int i=1;i<len;i++){
int key = A[i];
int j = i - 1;
while(j >= 0 && key < A[j]){
A[j+1] = A[j];
j--;
}
A[j+1] = key;
}
}

3. 选择排序

思想:遍历数组,每次遍历都在未排序的部分找到最小元素的下标,在此次遍历结束后将最小元素放到遍历开始的位置。

性能:时间复杂度为$O(n^2)$,算法比较次数与初始序列状态无关,性能在所有排序算法中最差。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Violence_Sort(int* A, int len){
for(int i=0;i<len;i++){
int k = i;
for(int j=i;j<len;j++)
if(A[j]<A[k])
k = j;
if(k != i){
int t = A[i];
A[i] = A[k];
A[k] = t;
}
}
}

4. 快速排序

思想:与归并排序类似,也使用分治思想,选择一个元素值(一般选择最后一个元素),将比它小的放在左边部分,比它大的放在右边,然后对两部分分别进行上述操作知道递归结束,关键步骤在于元素的分类,且只占用O(1)的额外存储空间。

性能:时间复杂度为$O(n \lg n)$,与归并排序不同,该算法占用常数级额外存储,在大规模序列排序应用中性能较好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int patition(int* p, int left, int right){
int key = p[left];
while(left < right){
while(left<right && key <= p[right]) right--;
if(left<right) p[left++] = p[right];
while(left<right && key >= p[left]) left++;
if(left<right) p[right--] = p[left];
}
p[left] = key;
return left;
}

void quick_sort(int* p, int left, int right){
if(left >= right) return;
int mid = patition(p, left, right);
quick_sort(p, left, mid-1);
quick_sort(p, mid+1, right);
}

5. 归并排序

思想:使用分治思想,将原始序列分为两部分分别排序,然后合并,重点在于合并过程。

性能:时间复杂度为$O(n\lg n)$,不过合并过程会使用额外的存储空间,占用内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Merge(int A[], int low, int mid, int high){
int cp[high-low+1];
for(int i = low; i <= high; i++)
cp[i-low] = A[i];
int l = low, r = mid+1;
for(int i = low; i <= high; i++){
if(l > mid) {A[i] = cp[r - low]; r++;}
else if(r > high) {A[i] = cp[l - low]; l++;}
else if(cp[l-low] <= cp[r-low]) {A[i] = cp[l -low]; l++;}
else {A[i] = cp[r -low]; r++;}
}
}

void Merge_Sort(int A[], int low, int high){
if(high > low){
int mid = (low+high)/2;
Merge_Sort(A, low, mid);
Merge_Sort(A, mid+1, high);
Merge(A, low, mid, high);
}
}

6. 堆排序

思想:使用堆数据结构进行排序,堆是一种用数组存储的二叉树,根据父节点和子节点的大小关系分为最大堆和最小堆,这里使用最大堆进行排序。

性能:时间复杂度为$O(n\lg n)$,在实际使用中,堆排序的排序性能通常逊与快速排序。

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
void Max_Heapify(int* A, int i,int size){
int l = 2*i;
int r = 2*i + 1;
int large = i;
if(l <= size && A[l] > A[i])
large = l;
else
large = i;
if(r <= size && A[r] > A[large])
large = r;
if(large != i){
int t = A[large];
A[large] = A[i];
A[i] = t;
Max_Heapify(A, large, size);
}
}

void Build_Max_Heap(int* A, int size){
for(int i=size/2;i>0;i--)
Max_Heapify(A,i,size);
}

void Heap_Sort(int* A, int len){
Build_Max_Heap(A, len);
while(len-1){
int t = A[1];
A[1] = A[i];
A[i] = t;
len--;
Max_Heapify(A,1,len);
}
}

7. 希尔排序

思想:利用插入排序的思想,考虑到插入排序在序列基本有序且数量较少时性能较高,因此先对序列进行逻辑上的分组然后插入排序,如:设定初始增量为x,则0,0+x,0+x+x …为一组,1,1+x,1+x+x …为第二组,共有x组,分别进行排序。那个随后减少增量,增加分组,直到增量为1。

性能:算法时间复杂度为$O(n^{1.3}) -O(n2)$,性能取决于增量序列。

1
2
3
4
5
6
7
8
9
10
11
void shellSort(int A[], int len){
for(int gap = len/2; gap > 0; gap /= 2){
for(int i = gap; i < len; i++){
int key = A[i];
int j;
for(j = i-gap; j>=0 && A[j] > key; j-= gap)
A[j+gap] = A[j];
A[j+gap] = key;
}
}
}

8. 基数排序

基本思想:
BinSort想法非常简单,首先创建数组A[MaxValue];然后将每个数放到相应的位置上(例如17放在下标17的数组位置);最后遍历数组,即为排序后的结果。

图示:

img

BinSort

  • 问题: 当序列中存在较大值时,BinSort 的排序方法会浪费大量的空间开销。

RadixSort

  • 基本思想: 基数排序是在BinSort的基础上,通过基数的限制来减少空间的开销。

  • 过程:

    10101001

    过程1

    9990

    过程2

(1)首先确定基数为10,数组的长度也就是10.每个数34都会在这10个数中寻找自己的位置。
(2)不同于BinSort会直接将数34放在数组的下标34处,基数排序是将34分开为3和4,第一轮排序根据最末位放在数组的下标4处,第二轮排序根据倒数第二位放在数组的下标3处,然后遍历数组即可。

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
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
//A:原数组
//temp:临时数组
//n:序列的数字个数
//k:最大的位数2
//r:基数10
//cnt:存储bin[i]的个数
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
//初始化
for(int j=0;j<r;j++){
cnt[j] = 0;
}
//计算每个箱子的数字个数
for(int j=0;j<n;j++){
cnt[(A[j]/rtok)%r]++;
}
//cnt[j]的个数修改为前j个箱子一共有几个数字
for(int j=1;j<r;j++){
cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1;j>=0;j--){ //重点理解
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}

自定义排序

仿函数

1
2
3
4
5
6
struct Com {
bool operator() (string a, string b) {
return a + b < b + a;
}
};
sort(str.begin(), str.end(), Com()); // Com()为临时对象

lambda表达式

1
2
3
4
5
6
7
8
9
// 1. 匿名lambda表达式
sort(str.begin(), str.end(), [](string a, string b) {
return a + b < b + a;
});
// 2.具名lambda表达式
auto lam = [](string a, string b) {
return a + b < b + a;
};
sort(str.begin(), str.end(), lam);;

函数指针

1
2
3
4
5
bool static com(string a, string b) {
return a + b < b + a;
}
//加static的原因:类成员函数有隐藏的this指针,static 可以去this指针
sort(str.begin(), str.end(), com);

STL标准库中包含几个可供关联式容器使用的排序规则,如表 1 表示。

排序规则 功能
std::less 底层采用 < 运算符实现升序排序,各关联式容器默认采用的排序规则。
std::greater 底层采用 > 运算符实现降序排序,同样适用于各个关联式容器。
std::less_equal 底层采用 <= 运算符实现升序排序,多用于 multimap 和 multiset 容器。
std::greater_equal 底层采用 >= 运算符实现降序排序,多用于 multimap 和 multiset 容器。

值得一提的是,表 1 中的这些排序规则,其底层也是采用函数对象的方式实现的。以 std::less 为例,其底层实现为:

1
2
3
4
5
6
7

template <typename T>
struct less { //定义新的排序规则
bool operator()(const T &_lhs, const T &_rhs) const {
return _lhs < _rhs;
}
}
  • © 2019-2022 guoben
  • PV: UV:

微信