acewzj

���ҽ�

0%

DS-SORT

Posted on Edited on In ,

这篇文章记述了关于排序的知识点。

https://blog.csdn.net/v_july_v/article/details/7382693

image-20210305143716121

冒泡排序

冒泡排序是由两个for循环构成，第一个for循环的变量 i 表示总共需要多少轮比较，第二个for循环的变量 j 表示每轮参与比较的元素下标【0,1，……，length-i】，因为每轮比较都会出现一个最大值放在最右边，所以每轮比较后的元素个数都会少一个，这也是为什么 j 的范围是逐渐减小的。

1
2
3
4
5
6
7
void bubble_sort(int arr[], int len) {
	int i, j;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

归并排序

Now that we’ve understood this trick, here is my pseudocode of the merge sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if
 
   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);
 
   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

image-20201202111638424

一直以来困惑于个数和长度的计算，比如 start = 71, end = 253,问你中间有多少个元素啊？

补充：注意求的是区间个数还是元素个数，如果是元素个数的话最后还要加1。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void Merge(int arr[], int reg[], int start, int end) {
    if (start >= end)return;
    int len = end - start, mid = (len >> 1) + start;

    //分成两部分
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    //然后合并
    Merge(arr, reg, start1, end1);
    Merge(arr, reg, start2, end2);


    int k = start;
    //两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较
    //如此反复,可以把两个有序的序列合并成一个有序的序列
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];

    //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环
    //那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放
    while (start1 <= end1)
        reg[k++] = arr[start1++];

    //这一步和上面一样
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    //把已经有序的reg序列放回arr序列中 这步千万不能忘
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void MergeSort(int arr[], const int len) {
    //创建一个同样长度的序列,用于临时存放
    int  reg[len];
    Merge(arr, reg, 0, len - 1);
}

void mergeSort(vector<int>& arr, vector<int>& reg, int start, int end) {
	if (start >= end) return;
	int mid = start + (end - start) / 2;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	mergeSort(arr, reg, start1, end1);
	mergeSort(arr, reg, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2) {
		reg[k++] = arr[start1] <= arr[start2] ? arr[start1++] : arr[start2++];
	}

	while (start2 <= end2) {
		reg[k++] = arr[start2++];
	}


	while (start1 <= end1) {
		reg[k++] = arr[start1++];
	}

	for (k = start; k <= end; ++k) {
		arr[k] = reg[k];
	}
}
int main() {
	vector<int> arr{ 2, 4, 1, 9, 4, 7, 5, 6, 0 };
	vector<int> reg(arr.size());
	mergeSort(arr, reg, 0, arr.size() - 1);
	for (auto& i : reg) cout << i << " ";
	return 0;
}

快速排序 从数组里面找出K大的数

快排是这样解决的，假设做正序排序：

在数组的头部和尾部分别设置一个哨兵，同时向对方走去。尾部的哨兵如发现有比基准数小的数，停下。头部的哨兵如发现有比基准数大的数，停下。交换两个数。再重新走重复前面的交换过程。直到两个哨兵相遇，交换基准数和尾哨兵。

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
45
46
47
48
49
50
51
52
class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1; // 注意这里的顺序控制着下面swap要不要加一
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }

    // 基于随机的划分
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

    void randomized_selected(vector<int>& arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomized_partition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomized_selected(arr, l, pos - 1, k);
        } else {
            randomized_selected(arr, pos + 1, r, k - num);
        }
    }

public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        srand((unsigned)time(NULL));
        randomized_selected(arr, 0, (int)arr.size() - 1, k);
        vector<int> vec;
        for (int i = 0; i < k; ++i) {
            vec.push_back(arr[i]);
        }
        return vec;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：期望为 O(n) ，由于证明过程很繁琐，所以不再这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。

最坏情况下的时间复杂度为 O(n^2)。情况最差时，每次的划分点都是最大值或最小值，一共需要划分 n - 1 次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 O(n^2)。

空间复杂度：期望为 O(log n)，递归调用的期望深度为 O(logn)，每层需要的空间为 O(1)，只有常数个变量。

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
int partition(vector<int> &vi, int low, int up)
{
	int pivot = vi[up];
	int i = low-1;
	for (int j = low; j < up; j++)
	{
		if(vi[j] <= pivot)
		{
			i++;
			swap(vi[i], vi[j]);
		}
	}
	swap(vi[i+1], vi[up]);
	return i+1;
}
//C++'s array range should be [low, up], the same as [low, up+1)
void quickSort(vector<int> &vi, int low, int up)
{
	if(low < up)
	{
		int mid = partition(vi, low, up);
		//Watch out! The mid position is on the place, so we don't need to consider it again.
		//That's why below is mid-1, not mid! Otherwise it will occur overflow error!!!
		quickSort(vi, low, mid-1);
		quickSort(vi, mid+1, up);
	}
}
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
class Solution {
public:
    int quickSelect(vector<int>& nums, int left, int right, int target){
        //这个代码有缺陷，这里应该要限制一下left < right
        int q = randomPartition(nums, left, right);
        if(q == target){
            cout << q << endl;
            for(auto& i : nums)
                cout << i << "  ";
            return nums[q];
        }            
        else
            return q > target? quickSelect(nums, left, q-1, target):quickSelect(nums, q+1, right, target);
    }
    int randomPartition(vector<int>& nums, int left, int right){
        int i = rand() % (right - left + 1) + left;
        //cout << i << " ";
        swap(nums[i], nums[right]); 
        int k = left;
        for(int j = left; j <= right; ++j){
            if(nums[j] < nums[right]){
                swap(nums[k], nums[j]);
                k++;
            }
        }
        swap(nums[k], nums[right]); 
        return k;
    }
    int findKthLargest(vector<int>& nums, int k) {
        //srand(time(0));
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
    }
};
//补充关于rand（）：生成一个在 0 - RAND_MAX 之间的伪随机数； srand():种植随机数种子

//当我们任意选取一个随机索引 i ，将nums[i]（枢轴） 与 nums[right] 进行交换，然后从 left 开始遍历，碰到比枢轴 大 的元素 还好，因为我们最后的结果就是让枢轴左边的元素都小于枢轴，枢轴右边的元素都大于枢轴。所以当所有的元素都大于枢轴时最后只需要将枢轴和 [0] 元素进行交换就好了。但是碰到比枢轴 小 的元素时就要将它与前面比枢轴大的元素进行交换。k 所指的元素就是前面大的元素的下标，碰到第一个大的它就不走了。

快速排序非递归版

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 QuickSort(int *a, int left,int right)
{
    if (a == NULL || left < 0 || right <= 0 || left>right)
        return;
    stack<int>temp;
    int i, j;
    //（注意保存顺序）先将初始状态的左右指针压栈
    temp.push(right);//先存右指针
    temp.push(left);//再存左指针
    while (!temp.empty())
    {
        i = temp.top();//先弹出左指针
        temp.pop();
        j = temp.top();//再弹出右指针
        temp.pop();
        if (i < j)
        {
            int k = Pritation(a, i, j);
            if (k > i)
            {
                temp.push(k - 1);//保存中间变量
                temp.push(i);  //保存中间变量
            }
            if (j > k)
            {
                temp.push(j);
                temp.push(k + 1);
            }
        }

    }

}

快速排序双指针版

https://leetcode-cn.com/problems/sort-an-array/submissions/

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:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        int start = left;
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            swap(nums[left], nums[right]);
        }
        swap(nums[start], nums[right]);
        return right;
    }
    void quickSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int mid = partition(nums, left, right);
            quickSort(nums, left, mid - 1);
            quickSort(nums, mid + 1, right);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

这道题是面试高频题目，其实主要是考察堆排序的：

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

堆排序

https://zhuanlan.zhihu.com/p/45725214

堆排序分为三个步骤：1）建堆 2）调整堆 3）排序

image-20200818131550690

第一步该如何建堆呢？

建堆时要从第一个非叶子节点从下至上，从右至左调整，第一个非叶子节点就是数组长度的一半 - 1

heapSort() for(int i = arr.size() / 2 - 1; i >= 0; --i)

第二步如何进行调整堆？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
heapAdjust(data[], int parent, int length) 

首先取出当前元素 int temp = data[parent];

接着取其左孩子节点 int lc = 2*parent + 1;

while(lc < length){

//如果有右孩子且右孩子比较小的话就把lc 换成右孩子（毕竟是三者之间最小的那个当父亲

if(lc < length - 1 && data[lc] < data[lc + 1])
lc++;
}
//如果父节点的值已经小于最小孩子节点的值，则退出
if(temp <= data[lc]) break;
否则就把最小孩子节点的值赋给父亲
    data[parent] = data[lc];
	parent = lc;
	lc = 2 * lc + 1;//还要继续调整下去，因为怕刚换下去的这个孩子节点在成为别人的父亲之后会不会出现堆失衡的现象？直到尽头末尾

arr[parent] = temp;

堆排序递归版本

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
class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        
        
        
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

-------------------------------------------------------
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */
 
/*eclipse cdt, gcc 4.8.1*/
 
#include <iostream>
#include <stack>
#include <queue>
 
using namespace std;
 
void HeapAdjust (int data[], int length, int k)
{
	int tmp = data[k];
	int i=2*k+1;
	while (i<length) {
		if (i+1<length && data[i]>data[i+1]) //选取最小的结点位置
			++i;
		if (tmp < data[i]) //不用交换
			break;
		data[k] = data[i]; //交换值
		k = i; //继续查找
		i = 2*k+1;
	}
	data[k] = tmp;//之前取出的原始父亲此时要安排在这里
}
 
void HeapSort (int data[], int length)
{
	if (data == NULL || length <= 0)
		return;
	for (int i=length/2-1; i>=0; --i) {
		HeapAdjust(data, length, i); //从第二层开始建堆
	}
 
	for (int i=length-1; i>=0; --i) {
		std::swap(data[0], data[i]);
		HeapAdjust(data, i, 0); //从顶点开始建堆, 忽略最后一个
	}
 
	return;
}
 
int main (void)
{
	int data[] = {49, 38, 65, 97, 76, 13, 27, 49};
	int length = 8;
	HeapSort(data, length);
	for (int i=0; i<length; ++i) {
		std::cout << data[i] << " ";
	}
 
	std::cout << std::endl;
	return 0;
}


import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        heapSort(arr);
        for(int i = 0; i < m; i++){
            System.out.print(arr[i] + " ");
        }

    }

    /**
     * 堆排序
     */
    private static void heapSort(int[] arr) { 
        // 将待排序的序列构建成一个大顶堆 O(n)
        for (int i = arr.length / 2; i >= 0; i--){ 
            //从第一个非叶子结点从下至上，从右至左调整结构
            heapAdjust(arr, i, arr.length - 1); 
        }

        // 逐步将每个最小值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) { 
            swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
        }
    }

    /**
     * 构建堆的过程
     * @param arr 需要排序的数组
     * @param k 需要构建堆的根节点的序号
     * @param n 数组的长度
     */
    private static void heapAdjust(int[] arr, int parent, int length) {
        int temp = arr[parent];//先取出当前元素i
        int lc = 2*parent + 1;
        while(lc < length){
            // 如果有右孩子结点，并且左孩子结点的值 小于右孩子结点，则选取右孩子结点
            //如果左子结点小于右子结点，lc指向右子结点
            if(lc < length -1 && arr[lc] < arr[lc+1]){
                lc++;
            }
            // 如果父结点的值已经小于孩子结点的值，则直接结束
            if (temp >= arr[lc]){
                break;
            }else{
                // 把孩子结点的值赋给父结点
                arr[parent] = arr[lc];
                parent = lc;
                lc = 2*lc + 1;
            }
        }
        arr[parent] = temp;
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


}

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
//大顶堆
//非递归版本
    void maxHeapify_(vector<int>& a, int i, int heapSize){
        int temp = a[i];
        int lc = 2 * i + 1;
        while(lc < heapSize){
            if(lc + 1 < heapSize && a[lc] < a[lc + 1]){//找左右孩子中较大的那个
                ++lc;
            }
            if(temp > a[lc]) break;//如果父亲大于左右孩子就跳出去/,.,
            a[i] = a[lc];//否则进行交换
            i = lc;//继续找下去
            lc = 2 * i + 1;
        }
        a[i] = temp;
    }
//递归版本    
    void maxHeapify(vector<int>& a, int i, int heapSize){
        int l = 2 * i + 1, r = 2 * i + 2, largest = i;
        if(l < heapSize && a[l] > a[largest]){
            largest = l;
        }
        if(r < heapSize && a[r] > a[largest]){
            largest = r;
        }      
        if(largest != i){
            swap(a[largest], a[i]);
            maxHeapify(a, largest, heapSize);
        }  
    }
    void buildHeap(vector<int>& a, int heapSize){
        for(int i = a.size() / 2 - 1; i >= 0; --i){
            maxHeapify_(a, i, heapSize);
        }
    }
    void heapSort(vector<int>& stones){
        buildHeap(stones, stones.size());
        int num = stones.size();
        for(int i = stones.size() - 1; i >= 0; --i){
            swap(stones[0], stones[i]);
            num--;
            maxHeapify_(stones, 0, num);
        }
    }
    int lastStoneWeight(vector<int>& stones) {
        heapSort(stones);
        while(stones.size() >= 2){
            for(auto& i : stones){
                cout << i << " ";
            }             
            if(stones[stones.size() - 1] == stones[stones.size() - 2]){
                stones.pop_back();
                stones.pop_back();
            }else{
                stones[stones.size() - 1] = stones[stones.size() - 1] - stones[stones.size() - 2];
                stones.erase(stones.end() - 2);
            }      
            heapSort(stones);  
            cout << endl;           
        }   
        for(auto& i : stones){
            cout << i << "#";
        } 
        return stones.size() == 1? stones[0] : 0;
    }
};

Welcome to my other publishing channels