代码随想录--排序算法

912.排序数组

快速排序

思路：

		1.  设置一个pivot
		2. 将小于nums[pivot]的值 放在左边
		3. 将 大于nums[pivot]的值  放在 右边
		4. 递归调用
1
2
3
4

注意：必须先比较nums[high] 与pivot

代码：

class Solution {

    int partition(vector<int>&nums, int low, int high){
        int pivot = nums[low];
        while(low<high){
            while(low <high && nums[high]>=pivot){
                high--;
            }nums[low] = nums[high];

            while(low<high && nums[low]<=pivot){
                low++;
            }nums[high] = nums[low];

        }
        nums[low] = pivot;
        return low;
    }

    void quiksort(vector<int>&nums, int low, int high){
        if(low<high){
            int pos = partition(nums, low, high);
            quiksort(nums, low, pos-1);
            quiksort(nums, pos+1, high);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        quiksort(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

堆排序

思路：

1.构造大顶堆   
2. 取出堆顶元素
3. 构造大顶堆
4. 取出堆顶元素	

将堆顶元素放入末尾，下次构造大顶堆时不考虑
1
2
3
4
5
6

注意：
代码：

class Solution {
    void buildMaxHeap(vector<int>& nums) {
        int n = nums.size();
        for (int i = (n - 1) / 2; i >= 0; --i) {
            maxHeapify(nums, i, n);
        }
    }

    void maxHeapify(vector<int>& nums, int i, int n) {
        while (i * 2 + 1 < n) {
            // 代表当前 i 节点的左右儿子；
            // 超出数组大小则代表当前 i 节点为叶子节点，不需要移位
            int lSon = 2 * i + 1;
            int rSon = 2 * i + 2;
            int large = i;
            if (lSon < n && nums[lSon] > nums[i]) large = lSon;
            if (rSon < n && nums[rSon] > nums[large]) large = rSon;

            if (large != i) {
                swap(nums[i], nums[large]);
                // 迭代判断对应子节点及其儿子节点的大小关系
                i = large;
            } else {
                break;
            }
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        // heapSort 堆排序
        int n = nums.size();
        // 将数组整理成大根堆
        buildMaxHeap(nums);
        for (int i = n - 1; i >= 1; --i) {
            // 依次弹出最大元素，放到数组最后，当前排序对应数组大小 - 1
            swap(nums[0], nums[i]);
            --n;
            maxHeapify(nums, 0, n);
        }
        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
43
44

归并排序

思路： 将有序序列 合并成一个
注意：
代码：

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
29
30
31
32
33
34