Mute

个人技术博客

0%

常见排序算法汇总

发表于 分类于

大多数时候我们可以选择直接调用库函数来对序列进行排序，这里主要总结三种常见的复杂度较低的排序。

快速排序

思路：

在待排序的数列中，我们首先要找一个数字作为基准数。我们一般选择第 1 个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，基于准基数的左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

这是典型的分治思想，即分治法。

快速排序是【不稳定排序】

时间/空间复杂度：

理想情况的时间复杂度是 O(NlogN)，空间复杂度 O(logN)，极端情况下的最坏时间复杂度是 O(N^2)，空间复杂度是 O(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
class Solution {
public:
    int findPartition(vector<int>& nums,int left,int right){
        int partition = nums[left]; //第一个数作为partition
        int start = left; //记录初始位置，当一轮快排结束后，start指向partition位置，用于和最后的left交换
        while(left < right){ //约束条件，保证left不会越过right
            while(left < right && nums[right] > partition) right--;//取的左边的数作为partition
            while(left < right && nums[left] <= partition) left++; //所以先遍历右边
            if(left < right) swap(nums[left],nums[right]); // 交换左右位置
        }
        swap(nums[left],nums[start]); //交换partition和nums[left]值
        return left; //此时partition左边的数都小于partition，右边的数都大于partition
    }
    void quickSort(vector<int>& nums,int left,int right){
        if(left < right){ 
            int partition = findPartition(nums,left,right); //确定partition的位置
            quickSort(nums,left,partition - 1);  //对partition左边的数进行排序
            quickSort(nums,partition + 1,right); //对partition右边的数进行排序
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        std::random_shuffle(nums.begin(),nums.end()); //随机打乱，防止出现极端情况
        quickSort(nums,0,nums.size() - 1);
        return nums;
    }
};

堆排序

思路：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。反复执行，便能得到一个有序序列。

堆排序是一种选择排序，同样是【不稳定排序】

时间/空间复杂度：

时间复杂度是 O(NlogN)，空间复杂度 O(logN)

代码实现：
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
class Solution {
public:
    //构造初始堆，将给定无序序列构造成一个大顶堆
    void maxHeap(vector<int>& nums,int heapSize,int i){
        int left = 2 * i + 1, right = 2 * i + 2, largest = i;
        if(left < heapSize && nums[left] > nums[largest]) largest = left;
        if(right < heapSize && nums[right] > nums[largest]) largest = right;
        if(largest != i){
            swap(nums[largest],nums[i]);
            maxHeap(nums,heapSize,largest);
        }
    }
    //构造堆
    void buildHeap(vector<int>& nums,int heapSize){
        for(int i = heapSize / 2; i >= 0; i--){
            maxHeap(nums,heapSize,i);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        int heapSize = nums.size(); 
        buildHeap(nums,heapSize);
        for(int i = nums.size() - 1; i >=0; i--){ //将堆顶元素与末尾元素交换，将最大元素沉到数组末端
            swap(nums[i],nums[0]);	//重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素
            heapSize--;				//反复执行，直到整个序列有序
            maxHeap(nums,heapSize,0);
        }
        return nums;
    }
};

归并排序

思路：

归并排序利用了分治的思想来对序列进行排序。对一个长为 N的待排序的序列，我们将其分解成两个长度为N/2的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

归并排序是【稳定排序】

时间/空间复杂度：

时间复杂度是 O(NlogN)，空间复杂度 O(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
class Solution {
public:
    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];
        }
    }
    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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //冒泡排序
        int n=nums.size();
        for(int i=0;i<n-1;i++)
        {
            for(int j=1;j<n-i;j++)
            {
                if(nums[j]<nums[j-1])
                {
                    int temp=nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1]=temp;
                }
            }
        }
        return nums;
    }
};

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //选择排序 每次将当前元素替换为后面最小的元素
        int n=nums.size();
        for(int i=0;i<n-1;i++)
        {
            int min=i;
            for(int j=i+1;j<n;j++)
            {
                if(nums[min]>nums[j])
                    min=j;
            }
            if(min!=i)
                swap(nums[i],nums[min]);
        }
        return nums;
    }
};

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 假设一个数组，在其内部，数已经按照升序排列，此时有一个新的数a要加入数组，那么数组内大于a的数字需不断地向后腾出位置，直到a找到自己的位置，就可以将a插入该位置，此时原数组仍保持升序排列
        int n=nums.size();
        for(int i=1;i<n;i++)
        {
            int flag=nums[i];
            int j=i-1;
            while(j>=0&&flag<nums[j])
            {
                nums[j+1]=nums[j];
                j--;
            }
            nums[j+1]=flag;
        }
        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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        int max=nums[0],min=nums[0];
        for(int i=1;i<n;i++)
        {
            if(nums[i]>max)
                max=nums[i];
            if(nums[i]<min)
                min=nums[i];
        }
        vector<int> count(max-min+1,0);
        for(int i=0;i<n;i++)
            count[nums[i]-min]++;
        int k=0;
        for(int i=0;i<max-min+1;i++)
        {
            while(count[i]--)
            {
                nums[k++]=i+min;
            }
        }
        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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        int max=abs(nums[0]);
        for(int i=1;i<n;i++)
        {
            if(max<abs(nums[i]))
                max=abs(nums[i]);
        }
        int w=0;
        while(max>0)
        {
            max/=10;
            w++;
        }
        int flag=1;
        vector<int> ans(n);
        for(int i=0;i<w;i++)
        {
            vector<int> bucket(19,0);
            for(int j=0;j<n;j++)
            {
                int temp=nums[j]/flag%10+9;
                bucket[temp]++;
            }
            for(int j=1;j<19;j++)
                bucket[j]+=bucket[j-1];
            for(int j=n-1;j>=0;j--)
            {
                int temp=nums[j]/flag%10+9;
                ans[--bucket[temp]]=nums[j];
            }
            nums.swap(ans);
            flag*=10;
        }
        return nums;
    }
};