数据结构与算法笔记 | 查找与排序

数据结构与算法 11 minutes read (About 1699 words)

如果只考一道最基本的数据结构与算法题, 那他一定是道排序题. — 鲁迅

一、交换排序

交换排序是一种借助记录交换进行排序的方法。
比较著名的有冒泡排序和快速排序。

1.1 冒泡排序

i 从 0 开始遍历到 n，相邻两个元素 r[i] 和 r[i+1] 进行比较, 将较大的元素交换到后面, 这样经过一次 i 的遍历之后, 最大的元素就会沉底. 然后 i 从 0 开始遍历到 n-1, 同样的方法, 第二大的元素就会沉底. 依次类推. 时间复杂度 O(n^2)

1.2 快速排序

经典的快速排序方法首先选定某个数 (如第一个元素) 作为基准(Pivot), 接下来通过 key 的逆序比较(用 j 遍历)和正序比较 (用 i 遍历) 找出倒着数比基准小的和正着数比基准大的数, 然后把比基准小放到 i 的位置, 比基准大的放到 j 的位置, 当 i == j 时, 就找到了基准所在的位置。
partition函数中，数组arr从下标l到下标r进行一次遍历，返回pivot所插入的位置。
双指针遍历的代码描述有如下两种方式(assert arr.length >= r+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 交换法
int partition(int[] arr, int l, int r)
{
    int pivot = arr[l];
    int i = l, j = r;
    while(l < r) {
        while(i < r && arr[i] <= pivot) {++i;}
        while(j > l && arr[j] >= pivot) {--j;}
        if(i >= j) { break;}
        swap(arr, i, j);
    }
    swap(arr, l, j);
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
// 填坑法
int partition2(int* arr, int l, int r) {
    int pivot = arr[l];
    while(l < r) {
        while(r > l && arr[r] >= pivot) --r;
        arr[l] = arr[r];
        while(l < r && arr[l] <= pivot) ++l;
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;
}

注意，这里的参数r是闭区间。partion函数分成了基准位置前和基准位置后两块, 再对其递归排序. 时间复杂度 O(nlog n)

1
2
3
4
5
6
7
void quicksort(int[] arr, int l, int r) {
    if(l <= r) {
        int pos = partition(arr, l, r);
        quicksort(arr, l, pos-1);
        quicksort(arr, pos+1, r);
    }
}

利用快速排序的性质，可以解决一些问题，比如：利用双指针遍历一次后，pivot插入了i的位置，在pivot之前有i个数比pivot小。可以通过这个特性找最小的K个数： 牛客网 最小的K个数

二、选择排序

选择排序是最符合人们思维习惯的一种排序方法. 也是考试中的常见出题范围.
选择排序的基本思想是先选出最小 (或最大) 的元素, 然后在剩余的元素中选出最小 (或大) 的元素作为第二个排序好的元素, 以此类推. 选择排序目前主要分为两大类, 即直接选择排序和堆排序.

2.1 直接选择排序

先从头开始遍历, 记录最小元素对应的序号 j, 遍历结束后边将第一个元素和j对应元素互换, 这样就将最小的元素放到了第一个位置. 然后从第二个元素开始遍历, 类似地就能找出第二小的元素. 这样经过 n-1 次遍历, 排序结束, 时间复杂度 O(n^2), 属于稳定排序.

2.2 堆排序

如果一棵完全二叉树的每个子树, 根节点都是最大的, 那么称为大根堆, 如果根节点都是最小的, 那么称为小根堆。
完全二叉树可以用数组表示，所以堆排序虽然输入的是数组，但其逻辑结构是完全二叉树。
大根堆用于升序排列，小根堆用于降序排列。

例题：牛客网: 最小的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
import java.util.*;

public class Solution {
    // 对含有n个节点的完全二叉树中的第i个节点及其子节点构造堆
    void heapify(int[] tree, int n, int i) {
        if(i >= n) { return ; }
        int min = i;
        if(2*i+1<n && tree[2*i+1] < tree[i]) {
            min = 2*i+1;
        }
        if(2*i+2<n && tree[2*i+2] < tree[min]) {
            min = 2*i+2;
        }
        if(min != i) {//swap
            int temp=tree[i];tree[i]=tree[min];tree[min]=temp;
        }
        if(min==2*i+1) heapify(tree, n, 2*i+1);
        else if(min==2*i+2) heapify(tree, n, 2*i+2);
    }
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        int n = input.length;
        if(k > n) return res;
        for(int i=n/2-1; i>=0; --i) {
            heapify(input, n, i);
        }
        for(int i=0; i<k; ++i) {
            res.add(input[0]);
            input[0] = input[n-1-i];
            heapify(input, n-1-i, 0);
        }
        return res;
    }
}

另解：由于Java的PriorityQueue实现了堆结构，所以可以利用该数据结构解题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (o1, o2) -> o1-o2);
        if(k > input.length) { return res; }
        for(int i=0; i<input.length; ++i) {
            pq.add(input[i]);
            if(i+k>=input.length) {
                res.add(pq.poll());
            }
        }
        return res;
    }
}

2.3 归并排序

算法复杂度 O(NlogN)

利用归并排序解决数组逆序对问题

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
public class Solution {
    long P = 0;
    public int InversePairs(int [] array) {
        if(null==array || array.length<=1) return 0;
        mergeSort(array, 0, array.length/2);
        mergeSort(array, array.length/2, array.length);
        merge(array, 0, array.length/2, array.length);
        return (int)(P % 1000000007);
    }
    
    void mergeSort(int[] array, int l, int r) {
        if(l>=r-1) { return ;}
        int mid = l + (r-l)/2;
        mergeSort(array, l, mid);
        mergeSort(array, mid, r);
        merge(array, l, mid, r);
    }
    
    void merge(int[] arr, int l, int m, int r) {
        if(l >= r-1) { return ;}
        int[] temp = new int[r-l];
        int temp_i = 0;
        int i = l, j = m;
        while(i<m && j<r) {
            if(arr[i] < arr[j]) {
                temp[temp_i] = arr[i];
                ++i;
            } else {//arr[i] > arr[j]
                temp[temp_i] = arr[j];
                P += m-i;
                ++j;
            }
            ++temp_i;
        }
        if(i == m) {
            while(j<r) {
                temp[temp_i] = arr[j];
                ++j;
                ++temp_i;
            }
        } else {//i<m, j==m
            while(i<m) {
                temp[temp_i] = arr[i];
                ++i;
                ++temp_i;
            }
        }
        // 赋值
        for(temp_i = 0; temp_i < temp.length; ++temp_i) {
            arr[l+temp_i] = temp[temp_i];
        }
    }
}

2.5 排序算法的稳定性

稳定排序通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

2.6 部分有序数组的排序

这属于归并排序的一个变种。
对于部分有序数组，在一个part内部是完全有序的，如果判断该部分part数量numOfParts为1，则说明是完全有序，可以直接return跳过。
归并的过程只对不同part进行merge

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
public class PartMergeSort {
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low];
        int i = low;// 左指针
        int j = mid;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i < mid && j < high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i < mid) {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j < high) {
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            a[k2 + low] = temp[k2];
        }
    }

    public static void mergeSort(int[] a, int low, int high, int partLength, int numOfParts) {
        if(numOfParts <= 1) {
            return ;
        }
        int mid = low + partLength*(numOfParts/2);
        if (low < high) {
            // 左边
            mergeSort(a, low, mid, partLength, numOfParts/2);
            // 右边
            mergeSort(a, mid, high, partLength, numOfParts-numOfParts/2);
            // 左右归并
            merge(a, low, mid, high);
            System.out.println(Arrays.toString(a));
        }
    }

    public static void partlyMergeSort(int[] arr) {
        int partLength = 0;
        while(arr[partLength] < arr[partLength+1]) {
            partLength++;
        }
        partLength++;
        int numOfParts = arr.length / partLength;
        mergeSort(arr, 0, arr.length, partLength, numOfParts);
    }

    public static void main(String[] args) {
        int a[] = { 18, 46, 51, 20, 65, 97, 30, 77, 82 };
        partlyMergeSort(a);
        System.out.println("部分有序数组排序结果：" + Arrays.toString(a));
    }
}

三、二分查找

给一个有序数组和目标元素，找出元素在数组中的位置，如果找不到，则返回-1
比如 数组 arr=[2,3,5,6,7,9] 目标元素 5
执行二分查找之前，首先要保证数组是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int* arr, int len, int tar) {
    int l = 0, r = len-1, m;
    while(l <= r) {
	m = l + (r-l)/2;
	if(arr[m] == tar) {
	    return m;
	} else if(arr[m] > tar) {
	    r = m - 1;
	} else {
	    l = m + 1;
	}
    }
    return -1;
}

二分查找有如下几种常见的变形：

  1. 返回小于这个目标的最大元素位置 lower_bound
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int lower_binarySearch(int* arr, int len, int tar) {
        int l = 0, r = len-1, m;
        while(l <= r) {
    	m = l + (r-l)/2;
    	if(arr[m] >= tar) {
    	    r = m - 1;
    	} else {
    	    l = m + 1;
    	}
        }
        return r;
    }

在C++ STL中，提供了对应的库函数

1
2
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
  1. 返回大于这个目标的最小元素位置 upper_bound
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int upper_binarySearch(int* arr, int len, int tar) {
        int l=0, r=len-1, m;
        while(l <= r) {
    	m = l + (r-l)/2;
    	if(arr[m] > tar) {
    	    r = m - 1;
    	} else {
    	    l = m + 1;
    	}
        }
        return l;
    }

在C++ STL中，提供了对应的库函数

1
2
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
  1. 对于存在重复元素的数组，要求返回重复元素的范围。
    有了前面两个函数之后，重复元素的范围就是 [lower_bound + 1, upper_bound - 1]
    1
    2
    3
    4
    5
    6
    7
    int low = lower_binarySearch(arr, N, T);
    int high = upper_binarySearch(arr, N, T);
    if(low+1 >= high) {
        printf("target %d not found!\n", T);
    } else {
        printf("arr[%d]~arr[%d]=%d.\n", low+1, high-1, T);
    }

例题 Leetcode 33

四、哈希查找

哈希查找是通过哈希函数将任意可能的元素映射到一个固定范围的整数值（哈希值），并将改元素储存到整数值对应的地址上，理论查找的时间复杂度是 O(1)。

实际情况中，如果需要映射的元素过大或者映射整数范围过小，会导致两个不同元素计算得到相同哈希值的情况，称为哈希冲突。
哈希冲突常见有以下几种解决方法：

  1. 链地址法
  2. 开放定址法
  3. 再哈希法
#算法 #数据结构 #排序 #sorting #algorithm #data structure #交换排序 #选择排序 #冒泡排序 #快速排序 #直接选择排序 #堆排序 #归并排序 #二分查找
PAT 真题 | 1038 Recover the Smallest Number 数据结构与算法笔记 | 图

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×