Tong's Blog

Welcome to my Blog

0%

刷题随笔01

发表于 更新于
本文字数： 18k 阅读时长 ≈ 16 分钟

01 复杂度、排序与二分法

十大排序

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

十大排序一图总览

img

稳定排序

  • 冒泡排序（bubble sort） — O(n2)
  • 插入排序 （insertion sort）— O(n2)
  • 归并排序 （merge sort）— O(n log n)

非稳定性排序

  • 选择排序 （selection sort）— O(n2)
  • 希尔排序 （shell sort）— O(n log n)
  • 堆排序 （heapsort）— O(n log n)
  • 快速排序 （quicksort）— O(n log n)

选择排序

数组索引0 ~ N-1，找到最小值，放到0位置上；

依次向后遍历，在i ~ N-1中，找到最小值，放到i位置上。

1
2
3
4
5
6
7
8
9
10
11
void selectionSort(vector<int>& arr) {
	if (arr.size() < 2) return;
    for (int i = 0; i < arr.size() - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            //在i ~ n-1上找到最小值的下标
            minIndex = arr[j] < arr[minIdex] ? j : minIdex;
        }
        swap(arr[i], arr[minIndex]);
    }
}

冒泡排序

0-1，1-2，2-3…依次两两交换，大的交换到后边，每一轮的最大值到最后。

[3 2 5 1 6 4] ==> [2 3 1 5 4 6] ==> [2 1 3 4 5 6] ==> [1 2 3 4 5 6]

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(vector<int>& arr) {
    if (arr.size() < 2) return;
    // 0 ~ N-1
    // 0 ~ N-2
    // 0 ~ N-3
    for (int e = arr.size() - 1; e > 0; e--) {
        for (int i = 0; i < e; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
            }
        }
    }
}

插入排序

0 ~ 0，0 ~ 1 , 0 ~ 2, … 0 ~ n -1，依次变得有序。第i轮，若第i个数小于前一个数，二者交换，直到i大于等于前一个数。

类似与摸牌后，每次进行插入排序。

初始数据状况会影响时间复杂度。最差O(n ^ 2)

1
2
3
4
5
6
7
8
9
10
void insertSort(vector<int>& arr) {
    if (arr.size() < 2) return;
    //0~0 有序的
    //0~i 变为有序
    for (int i = 1; i < arr.size(); i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr[j], arr[j + 1]);
        }
    }
}

二分法

经常在有序数组上，使用二分搜索，但是有序不是必要条件。

只要能正确构建左右两侧的逻辑，就可以使用二分。

  • 一个有序数组，找某个数是否存在
  • 一个有序数组，找 >= 某个数的最左侧位置
  • 一个有序数组，找 <= 某个数的最右侧位置
  • 局部最小值问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool exist(vector<int> sortArr, int num) {
    if (sortArr.size() == 0) return false;
    int L = 0, R = sortArr.size() - 1;
    int mid = 0;
    //L...R
    while (L < R) { //L..R 至少两个数
        mid = L + ((R - L) >> 1); //mid = (L + R) / 2
        if (sortArr[mid] == num) {
            return true;
        } else if (sortArr[mid] > num) {
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return sortArr[L] == num;
}

搜索>= 某个数的最左侧位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int nearestIndex(vector<int>& arr, int value) {
    int L = 0, R = arr.size() - 1;
    int index = -1;//记录最左的对号
    while (L <= R) { //至少一个数的时候
        int mid = L + ((R - L) >> 1);
        if (arr[mid] >= value) {
            index = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return index;
}

无序数组，任意两个相邻的数不相等，返回任意一个局部最小值（比左右相邻的数小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getLessIndex(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return -1;
    if (n == 1 || arr[0] < arr[1]) return 0;
    if (arr[n - 1] < arr[n - 2]) return n - 1;
    int L = 1;
    int R = n - 1;
    int mid = 0;
    while (L < R) {
        mid = L + ((R - L) >> 1);
        if (arr[mid] > arr[mid - 1]) {
            R = mid - 1;
        } else if (arr[mid] > arr[mid - 1]) {
            L = mid + 1;
        } else {
            return mid;
        }
    }
    return L:
}

02 异或运算

异或运算：相同为0，不同为1，二进制无进位相加（不进位）

同或运算：相同为1，不同为0

异或运算 (^) 性质：

  • 0 ^ N = N
  • N ^ N = 0
  • a ^ b = b ^ a （交换律）
  • (a ^ b) ^ c = a ^ (b ^ c) （结合律）
  • a ^ b = c ==> a = c ^ b ==> b = c ^ a

题目1

不使用额外空间变量交换两个数

利用异或运算的性质，注意：交换的两个数不能是同一块内存空间，否则二者变为0.

1
2
3
4
5
void swap(int& a, int& b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

题目2

一个数组中有一个数出现了奇数次，其他数出现了偶数次，找到并打印这个数（O(1) 额外空间复杂度完成）

解析：设置变量eor，顺序遍历异或所有的值，返回最后的eor

1
2
3
4
5
6
7
void printOddTimesNum1(vector<int>& arr) {
    int eor = 0;
    for (int i = 0; i < arr.size(); i++) {
        eor ^= arr[i];
    }
    cout << eor << endl;
}

题目3

把一个int类型的数，提取出最右侧的1

a = 0xb 00110110 ==> ans = 0xb 00000010

解析：a & (-a) 等价于 a & (~a + 1)

题目4

一个数组中有两种数出现了奇数次，其他数出现了偶数次，找到并打印这两种数（O(1) 额外空间复杂度完成）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void printOddTimesNum2(vector<int>& arr) {
    int eor = 0;
    for (int i = 0; i < arr.size(); i++) {
        eor ^= arr[i];
    }
    
    int rightOne = eor & (-eor); //提取出最右的1, eor != 0
    int onlyOne = 0; //eor'
    for (int i = 0; i < arr.size(); i++) {
        // arr[1] = 11100010
        //rightOne= 00000010
        if ((arr[i] & rightOne) != 0) {
            onlyOne ^= arr[i]
        }
    }
    cout << onlyOne << endl;
    cout << (eor ^ onlyOne) << endl;
}

题目5

一个数组中只有一种数出现K次，其他数都出现了M次，已知M > 1，K < M，找到出现了K次的数
要求额外空间复杂度O(1)，时间复杂度O(N)

解析：设置一个int数组长度为32，累加每个数的二进制位置的1的数量。每一位是否为M的整数倍判断出现K次的数的二进制最后一个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
int onlyKtimes(vector<int>& arr, int k, int m) {
    vector<int> help(32, 0);
    //help[i]位置的1出现的次数
    for (int num : arr) {
        for (int i = 0; i < 32; i++) {
            if (((num >> i) & 1) != 0)
            	help[i]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        /*返回只出现k次的数，如果不是k次，返回-1；
        if (help[i] % m == 0) continue;
        if (help[i] % m == k) {
        	ans |= 1 << i;
        } else {
        	return -1;
        }*/
        
        if (help[i] % m != 0) { //在第i位上有1
            ans |= 1 << i;
        }
    }
    return ans;
}

03 归并排序

左半部分有序 + 右半部分有序 + merge

merge过程双指针，顺序copy结果到新有序数组

总体时间复杂度为 O(n * log(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
34
35
36
37
void mergeSort(vector<int>& arr) {
    if (arr.size() < 1) return;
    process(arr, 0, arr.size() - 1);
}

//arr[L...R]排有序
// T(N) = 2 * T(N / 2) + O(N)
// O(N * logN)
void process(vector<int>& arr, int L, int R) {
    if (L == R) { //base case
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

void merge(vector<int>& arr, int L, int M, int R) {
    vector<int> help(R - L + 1);
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 要么p1越界了，要么p2越界了
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.size(); i++) {
        arr[L + i] = help[i];
    }
}

迭代写法：

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
void mergesort2(vector<int> arr) {
	if (arr.size() < 1) return;
    int N = arr.size();
    // 步长
    int mergeSize = 1;
    while (mergeSize < N) { // log N
        // 当前左组的，第一个位置
        int L = 0;
        while (L < N) {
            if (mergeSize >= N - L) {
                break;
            }
            int M = L + mergeSize - 1;
            int R = min(mergeSize + M, N - 1);
            merge(arr, L, M, R);
            L = R + 1;
        }
        // 防止溢出
        if (mergeSize > N / 2) {
            break;
        }
        mergeSize <<= 1;
    }
}

void merge(vector<int>& arr, int L, int M, int R) {
    vector<int> help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 要么p1越界了，要么p2越界了
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }
}

题目1：小和问题

在一个数组中，一个数左边比它小的数的总和，叫该数的小和
所有数的小和累加起来，叫数组小和

给定一个数组，求最小和，到第i个数，若第j （j < i）个数的值小于第i个数，累加上第j个数。

例子： [1,3,4,2,5]
1左边比1小的数：没有
3左边比3小的数：1
4左边比4小的数：1、3
2左边比2小的数：1
5左边比5小的数：1、3、4、 2
所以数组的小和为1+1+3+1+1+3+4+2=16

[6 3 2 1 6 7] ==> i = 0, sum = 0; i = 1, sum = 0; i = 2, sum = 0; i = 3, sum = 0; i = 4, sum = 4, sum = 0;

i = 5, sum = 3 +2 + 1 = 6; i = 6, sum = 18; 返回 res = 6 + 18 = 24;

每个位置，之前比自己小的数累加起来，各个位置累加和再求和。

暴力法：

1
2
3
4
5
6
7
8
9
10
int comparator(vector<int>& arr) {
    if (arr.size() < 2) return 0;
    int res = 0;
    for (int i = 1; i < arr.size(); i++) {
        for (int j = 0; j < i; j++) {
            res += arr[j] < arr[i] ? arr[j] : 0;
        }
    }
    return res;
}

归并排序法：

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
int smallSum(vector<int>& arr) {
    if (arr.size() < 2) return 0;
    return process(arr, 0, arr.size() - 1);
}

// arr[L..R]既要排好序，也要求小和返回
// 所有merge时，产生的小和，累加
// 左 排序   merge
// 右 排序  merge
// merge
int process(vector<int>& arr, int l, int r) {
    if (l == r) {
        return 0;
    }
    // l < r
    int mid = l + ((r - l) >> 1);
    return 
        process(arr, l, mid) 
        + 
        process(arr, mid + 1, r) 
        + 
        merge(arr, l, mid, r);
}

int merge(vector<int>& arr, int L, int m, int r) {
    vector<int> help(r - L + 1);
    int i = 0;
    int p1 = L;
    int p2 = m + 1;
    int res = 0;
    while (p1 <= m && p2 <= r) {
        res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.size(); i++) {
        arr[L + i] = help[i];
    }
    return res;
}

题目2：逆序对总数

在一个数组中，任何一个前面的数a，和任何一个后面的数b，如果(a,b)是降序的，就称为逆序对
给定一个数组arr，求数组的逆序对总数量

[3 1 0 4 3 1] ==> 6

每一个数右边有多少个数比他小，从右向左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
int reverPairNumber(vector<int>& arr) {
    if (arr.size() < 2) return 0;
    return process(arr, 0, arr.size() - 1);
}

// arr[L..R]既要排好序，也要求逆序对数量返回
// 所有merge时，产生的逆序对数量，累加，返回
// 左 排序 merge并产生逆序对数量
// 右 排序 merge并产生逆序对数量
int process(vector<int>& arr, int l, int r) {
    if (l == r) return 0;
    //l < r
	int mid = l + ((r - l) >> 1);
    return  process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
int merge(vector<int>& arr, int l, int m, int r) {
    vector<int> help(r - l + 1);
    int i = help.size() - 1;
    int p1 = m, p2 = r;
    int res = 0;
    while (p1 >= L && p2 > m) {
        res += arr[p1] > arr[p2] ? (p2 - m) : 0;
        help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
    }
    while (p1 >= L) {
        help[i--] = arr[p1--];
    }
    while (p2 > m) {
        help[i--] = arr[p2--];
    }
    for (i = 0; i < help.size(); i++) {
        arr[L + i] = help[i];
    }
    return res;
}

题目3：Bigger than right twice

在一个数组中，对于任何一个数num，求有多少个(后面的数*2)依然<num，返回总个数
比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0，2
0的后面没有
2的后面没有
所以总共有5个

解析：左组有序+有组有序+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
int reverPairs(vector<int>& arr) {
    if (arr.size() < 2) return 0;
    return process(arr, 0, arr.size() - 1);
}

int process(vector<int>& arr, int l, int r) {
    if (l == r) return 0;
    //l < r
	int mid = l + ((r - l) >> 1);
    return  process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
int merge(vector<int>& arr, int l, int m, int r) {
    // [L....M] [M+1....R]
    int ans = 0;
    // 目前囊括进来的数，是从[M+1, windowR)
    int windowR = m + 1;
    for (int i = l; i <= m; i++) {
        while (windowR <= r && (long) arr[i] > (long) arr[windowR] * 2) {
            windowR++;
        }
        ans += windowR - m - 1;
    }
    vector<int> help(r - l + 1);
    int i = 0;
    int p1 = l, p2 = m + 1;
    while (p1 <= m && p2 <= r) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= L) {
        help[i++] = arr[p1++];
    }
    while (p2 <= m) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.size(); i++) {
        arr[l + i] = help[i];
    }
    return ans;
}

04 快速排序

快速排序是基于分治策略的，其算法思想如下。
（1）分解：先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
（2）治理：对两个子序列进行快速排序。

（3）合并：将排好序的两个子序列合并在一起，得到原问题的解。

代码实现：

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
//划分函数，对原序列进行分解，将其分解为两个子序列，以基准元素pivot为界，
//左侧子序列都比pivot小，右侧子序列都比pivot大。
int partition(vector<int>& arr, int low, int high) {
    int i = low, j = high, pivot = arr[low];	//基准元素
    while (i < j) {
        while (i < j && arr[j] > pivot) j--;	//向左扫描
        while (i < j && arr[i] <= pivot) i++;	//向右扫描
        if (i < j) {
            swap(arr[i++], arr[j--]);	//交换arr[i]和arr[j]
        }
    }
    if (arr[i] > pivot) {
        swap(arr[low], arr[i - 1]);	//交换arr[i - 1]和arr[low]，并返回基准元素位置i - 1
        return i - 1;
    }
    swap(arr[i], arr[low]);	//交换arr[i]和arr[low]，并返回基准元素位置i
    return i;
}

//快速排序函数。首先对原序列划分，得到划分的中间位置mid；然后以中间位置为界，
//分别对左半部分(low,mid-1)执行快速排序，对右半部分(mid+1,high)执行快速排序。
//递归结束的条件是low≥high
void qsort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);	//划分
        qsort(arr, low, p - 1);		//左区间递归快排
        qsort(arr, p + 1, high);	//右区间递归快排	
    }
}

int main() {
    vector<int> arr{1, 1, 4, 5, 1, 4};
    qsort(arr, 0, arr.size() - 1);
}

最好情况时间复杂度为O(nlogn)

最坏情况下的时间复杂度为O(n^2)

平均情况下的空间复杂度为O(nlogn)

05 希尔排序

希尔排序：插入排序的改进版，实现简单，对于中等规模数据的性能表现还不错。对较大规模并且无序的数据也非常有效率

无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要n - 1次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为h的元素有序，刚开始h的大小可以是h = n / 2，接着让 h = n / 4，让h一直缩小，当h = 1 时，也就是此时数组中任意间隔为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
// 将nums[i]插入到所在分组的正确位置上， nums[i]所在分组为：
// …nums[i-2*gap], nums[i-gap], nums[i], nums[i+gap], nums[i+2*gap]…
void shellSortCore(vector<int>& nums, int gap, int i) {
    int inserted = nums[i];
    int j;
    // 插入的时候按组进行插入（组内元素两两相隔gap）
    for (j = i - gap; j>= 0 && inserted < nums[j]; j -= gap) {
        nums[j + gap] = nums[j];
    }
    nums[j + gap] = inserted;
    
}
// 主函数
void shellSort(vector<int>& nums) {
    int len = nums.size();
    // 进行分组，最开始的时候，gap为数组长度一半
    for (int gap = len / 2; gap > 0; gap /= 2) {
        // 对各个分组进行插入分组
        for (int i = gap; i < len; i++) {
            // 将nums[i]插入到所在分组正确的位置上
            shellSortCore(nums, gap, i);
        }
    }
    // 打印希尔排序后的数组
    for (auto a : nums) {
		cout << a << " ";
	}
}

06 堆排序

大顶堆：父节点的值大于子节点，堆排序中为升序排列

小顶堆：父节点的值小于子节点，堆排序中为降序排列

先把数组构造成一个大顶堆，然后把堆顶（数组最大值，数组的第一个元素）和数组的最后一个元素交换，把最大值放到了最后边。数组长度n-1，再进行构造堆，把剩余的第二大值放到堆顶，输出堆顶（放到数组最后）。依此类推，直到数组排序完成。

堆符合两个特点：

  • 是一个完全二叉树
  • 所有父节点的值都大于（或小于）子节点的值

平均时间复杂度：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
// 对有一定顺序的堆，当前第i个结点取根左右的最大值（这个操作称heapfiy）
void heapify(vector<int>& nums, int n, int i) {
    int l = i * 2 + 1, r = i * 2 + 2;// 左右节点索引, left=2*i+1  right=2*i+2  
    int maxid = i;
    if (l < n && nums[l] > nums[maxid]) {
        maxid = l;
    }
    if (r < n && nums[r] > nums[maxid]) {
        maxid = r;
    }
    if (maxid != i) {
        swap(nums[i], nums[maxid]);
        heapify(nums, n, maxid);
    }
}
// 建立大根堆，从树的倒数第二层第一个结点开始，对每个结点进行heapify操作，然后向上走
void heapify_build(vector<int>& nums, int n) {
    int temp = (n - 2) / 2;
    for (int i = temp; i >= 0; i--) {
        heapify(nums, n, i);
    }
    // 打印当前数组
    for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}
// 建立大根堆之后，每次交换最后一个结点和根节点（最大值），
// 对交换后的根节点继续进行heapify（此时堆的最后一位是最大值，因此不用管他，n变为n-1）
void heapify_sort(vector<int>& nums, int n) {
    heapify_build(nums, n);
    for (int i = 0; i < n; i++) {
        swap(nums.front(), nums[n - i - 1]);
		heapify(nums, n - i - 1, 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
#include<iostream>
#include<vector>
using namespace std;

// 辅助函数，构造大根堆
void adjust(vector<int>& arr, int len, int index) {
    int maxid = index;
    int left = 2 * index + 1, right = 2 * index + 2;
    // 计算第i个节点的左右子节点的下标   left=2*i+1  right=2*i+2  parent=(i-1)/2
    if (left < len && arr[left] > arr[maxid]) maxid = left;
    if (right < len && arr[right] > arr[maxid]) maxid = right;
    
    if (maxid != index) {
        swap(arr[maxid], arr[index]);
        adjust(arr, len, maxid); // 递归调整其他不满足堆性质的部分
    }
 }

void heapSortCore(vector<int>& arr, int len) {
    // 初次构建堆，i从第一个非叶子节点开始进行堆调整，i节点的父节点为parent=(i-1)/2，即(len-1-1)/2
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjust(arr, len, i);
    }
    
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);// 将当前最大的放置到数组末尾，将未完成排序的部分继续进行堆排序
        adjust(arr, i, 0);
    }
}

void heapSort(vector<int>& arr) {
    heapSortCore(arr, arr.size());
}

07 计数排序

统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

  • 计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
  • 如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
  • 计数排序不是比较排序，排序的速度快于任何比较排序算法。

算法思想：

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  • 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
  • 向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去 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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序, 输入原始数组与目标数组（初始化与原数组相同）
void countSort(vector<int>& vecRaw, vector<int>& vecObj) {
    // 确保待排序容器非空
    if(vecRaw.size() == 0) return;
    
    // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
    int vecCountLen = (*max_element(vecRaw.begin(), vecRaw.end())) + 1;
    vector<int> vecCount(vecCountLen, 0);
    
    // 统计每个键值出现的次数
    for (int i = 0; i < vecRaw.size(); i++) {
        vecCount[vecRaw[i]]++;
    }
    
    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < vecCountLen; i++) {
        vecCount[i] += vecCount[i - 1];
    }
    
    // 将键值放到目标位置
    for (int i = vecRaw.size() - 1; i >= 0; i--) { // 此处逆序是为了保持相同键值的稳定性
        vecObj[--vecCount[vecRaw[i]]] = vecRaw[i];
    }
}

int main()
{
	vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
	vector<int> vecObj(vecRaw.size(), 0);

	countSort(vecRaw, vecObj);

	for (int i = 0; i < vecObj.size(); ++i)
		cout << vecObj[i] << "  ";
	cout << endl;

	return 0;
}

08 桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。是计数排序的变种，利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

算法思想：

  • 设置一个定量的数组当作空桶子。
  • 寻访序列，并且把项目一个一个放到对应的桶子去。
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的序列中。

平均时间复杂度：O(n + k)

空间复杂度：O(n * k)

稳定性：稳定

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>

using namespace std;

// 桶排序，输入原始数组和桶的数量（默认可为5）
void bucketSort(vector<int>& arr, int bucketSize) {
    if (arr.size() == 0) return;
    // 确定数组的最大值与最小值
    int maxVal = arr[0];
    int minVal = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < minVal) {
            minVal = arr[i];
        } else if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    // 设置每个桶的容量大小
    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    vector<vector<int>> buckets(bucketCount);
    
    // 利用映射函数将数据分配到各个桶中
    for (int i = 0; i < arr.size(); i++) {
        int index = (arr[i] - minVal) / bucketSize; // 第index个桶
        buckets[index].push_back(arr[i]);
    }
    int arrIndex = 0;
    for (auto bucket : buckets) {
        if (bucket.size() <= 0) {
            continue;
        }
        // 对每个桶进行排序，这里使用了插入排序
        insertSort(bucket);
        for (int value : bucket) {
            arr[arrIndex++] = value;
        }
    }
}
// 插入排序
void insertSort(vector<int>& arr) {
    if (arr.size() < 2) return;
    //0~0 有序的
    //0~i 变为有序
    for (int i = 1; i < arr.size(); i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr[j], arr[j + 1]);
        }
    }
}

09 基数排序

一种多关键字的排序算法，可用桶排序实现。

算法思想：

  • 取得数组中的最大数，并取得位数；

  • arr为原始数组，从最低位开始取每个位组成radix数组；

  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）

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
//辅助函数，求数据的最大位数
int maxbit(vector<int>& arr, int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (maxVal < arr[i]) {
            maxVal = arr[i];
        }
    }
    int d = 1;// 位数
    int p = 10;//尾数0-9，10进制
    while (maxVal >= p) {
        maxVal /= 10;
        d++;
    }
    return d;
}
// 基数排序 
void radixSort(vector<int>& arr, int n) {
    int d = maxbit(arr, n);
    vector<int> tmp(n, 0);
    vector<int> count(10, 0);// 计数器
    int i, j, k;
    int radix = 1;
    for (int i = 1; i <= d; i++) {// 进行d次排序
        for (int j = 0; j < 10; j++) {
            count[j] = 0;// 每次分配前清空计数器
        }
        for (int j = 0; j < n; j++) {
            int k = (arr[j] / radix) % 10;// 统计每个桶中的记录数     
            count[k]++;
        }
        for (int j = 1; j < 10; j++) {
            count[j] = count[j - 1] + count[j];// 将tmp中的位置依次分配给每个桶
        }
        for (int j = n - 1; j >= 0; j--) {
            int k = (arr[j] / radix) % 10;
            tmp[count[k] - 1] = arr[j];
            count[k]--;
        }
        for (int j = 0; j < n; j++) {// 将临时数组的内容复制到arr中
            arr[j] = tmp[j];
        }
        radix *= 10;
    }
}