排序

#include  

using namespace std;

//划分函数
int Partition(int A[],int low,int high){
    int pivot = A[low];
    while(low
        while(low=pivot) --high;
        A[low]=A[high];
        while(low
    if(low
        int pivotpos = Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);//递归划分左子表
        QuickSort(A,pivotpos+1,high);//递归划分右子表
    }
}

int main()
{
    int array[] = {49,38,65,97,76,13,27,49};
    int num = sizeof(array)/sizeof(array[0]);//求数组中元素的个数。数组总长度10个int/一个数据的长度,1个int
    QuickSort(array,0,num-1);//第一个元素下标为0。元素个数-1，否则内存越界
    for(int i=0;i
        cout< 
2.冒泡排序 

 

 

 

 

 

 

 

 
10.leetcode排序题 
(1)912 排序数组 
网址：https://leetcode.cn/problems/sort-an-array
 问题：用快速排序显示测试用例超时
 分析：但是我们都知道快速排序是平均性能最好的排序算法，时间复杂度为O(n*log₂n)
 原因：第11个测试用例，是1到50000有序排列。因为快排每次都是选取第一个元素作为枢轴元素，对于已经有序的数组，快速排序的性能退化为O(n²)。在元素数量n又较大的情况下，超出了题目限制的时间。
 
class Solution {
public:
    vector sortArray(vector& nums) {
    QuickSort(nums,0,nums.size()-1);
    return nums;
    }

    //划分函数
    int Partition(vector&nums,int low,int high){
        int pivot = nums[low];
        while(low
            while(low=pivot) --high;
            nums[low]=nums[high];
            while(low&nums ,int low,int high){
        if(low
            int pivotpos = Partition(nums,low,high);
            QuickSort(nums,low,pivotpos-1);//递归划分左子表
            QuickSort(nums,pivotpos+1,high);//递归划分右子表
        }
    }
};
 

 
无语，偷个懒，用接口吧！
 ①sort() 函数
 sort函数介绍：
 头文件：sort函数包含在头文件为#include的c++标准库中
 时间复杂度：O(n*log₂n)。和快排平均性能一样，但是优化了快排在最坏情况(全部有序)时的性能。
 语法：sort(start,end,cmp)
 参数：
 （1）start表示要排序数组的起始地址；
 （2）end表示数组结束地址的下一位；
 （3）cmp用于规定排序的方法，可不填，默认升序。
 
//sort()函数
class Solution {
public:
    vector sortArray(vector& nums) {
            sort(nums.begin(),nums.end());
            return nums;
    }
};
 
②多重集合multiset   [性能慢于sort()]
 STL排序容器：set和map只允许唯一key值，且按升序排序。multiset和multimap可以存多个相同的key值。【将关键字与值成对关联】，元素位置取决于特定的排序准则以及元素值，和插入次序无关。以关键字为索引，对其中元素进行排序。
 底层实现：红黑树。
 头文件 #include
 命名空间 using std::multiset;
 
class Solution {
public:
    vector sortArray(vector& nums) {//前三行都是官方给的,数组名为nums
        multiset ms(nums.begin(),nums.end());
        return vector(ms.begin(),ms.end());
    }
};