C++ 排序算法

刷题
字数统计: 2.6k字   |   阅读时长≈ 11分钟

今日打卡题目如下：

  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:

微信